| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Хеш функции для срок

Kolan ©   (2004-12-09 00:32:00) 

Здравствуйте,
 Задали мне подобрать хеш функцию для хеширования строк. Нужна она для поиска в map(ассациативный массив). Поэтому вопросы:
1. Какие функции посмотреть и где. Сделал с функцией
Hash = (31 * Hash + *(StringToHash + I));
Хочу другие попробовать.
2. Может кто занет. Что будет быстрее хеширование и поиск. Или поиск по строке без всякого хеша.
3. Формула (1) взята с RSDN интересно откуда константа 31 взялась?

---

Kolan   (2004-12-10 00:34:00) [1]

Благодарю. Очень помогли.
:)))

---

VMcL   (2004-12-09 22:55:00) [2]

>> VMcL ©  (09.12.04 22:54) [6]

> где N - количество элементов вектора.

Массива, есессно.

---

VMcL   (2004-12-09 22:54:00) [3]

>> Kolan ©  (09.12.04 00:32)

> 1. Какие функции посмотреть и где

У Бакнелла в Фундаментальных алгоритмах есть немного.

Eg.
function TDSimpleHash(const AKey: String): Integer;
var
 i: Integer;
begin
 Result := 0;
 for i := 1 to Length(AKey) do
   Result := Result * 17 + Ord(AKey[i]);
end;

function TDPJWHash(const AKey: String): Integer;
var
 G: Longint;
 I: Integer;
begin
 Result := 0;
 for I := 1 to Length(AKey) do
 begin
   Result := (Result shl 4) + Ord(AKey[I]);
   G := Result and $F0000000;
   if G <> 0 then
     Result := (Result xor (G shr 24)) xor G;
 end;
end;

> 2. Может кто занет. Что будет быстрее хеширование и поиск. Или поиск по строке без всякого хеша.

AFAIR, смысл хеш-таблиц в том, чтобы свести операцию поиска объекта к операции порядка O(1) или близкой к ней величине. Один из известных методов поиска - бинарный в отсортированном массиве - имеет порядок O(log(N)), где N - количество элементов вектора.

> Формула (1) взята с RSDN интересно откуда константа 31 взялась?

Простое число. Так же, как и "17" в примере выше.

---

Гай   (2004-12-09 18:56:00) [4]

Dok_3D ©   (09.12.04 14:35) [4]
Я просто выдернул из своего исходника вызовы функций подряд. А ему всё равно про все почитать будет нужно...

---

Dok_3D   (2004-12-09 14:35:00) [5]

2 Гай ©

Ну, уж если через CryproApi, то список можно сократить:

CryptAcquireContext
CryptCreateHash
CryptHashData
CryptGetHashParam

---

Гай   (2004-12-09 13:12:00) [6]

Копай в MSDN по функциям

CryptAcquireContext
CryptCreateHash
CertOIDToAlgId
CryptHashData
CryptGetHashParam
CryptDestroyHash
CryptReleaseContext

---

TUser   (2004-12-09 10:24:00) [7]

Борланд использует
function TStringHash.HashOf(const Key: string): Cardinal;
var
 I: Integer;
begin
 Result := 0;
 for I := 1 to Length(Key) do
   Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
     Ord(Key[I]);
end;

---

Nikolay M.   (2004-12-09 09:59:00) [8]

MD5, CRC32.
Возьми 10^6 разных строк и захешируй их МД5, CRC32 и своей ф-ей. Сравни количество одинаковых хешей. У кого меньше - тот и лучше.

---

Наверх