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

← →
Kolan © (2004-12-09 00:32) [0]

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

← →
Nikolay M. © (2004-12-09 09:59) [1]

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

← →
TUser © (2004-12-09 10:24) [2]

Борланд использует
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;

← →
Гай © (2004-12-09 13:12) [3]

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

CryptAcquireContext
CryptCreateHash
CertOIDToAlgId
CryptHashData
CryptGetHashParam
CryptDestroyHash
CryptReleaseContext

← →
Dok_3D © (2004-12-09 14:35) [4]

2 Гай ©

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

CryptAcquireContext
CryptCreateHash
CryptHashData
CryptGetHashParam

← →
Гай © (2004-12-09 18:56) [5]

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

>>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" в примере выше.

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

Хеш функции для срок Найти похожие ветки