Скачать: CL | DM;

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

← →
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]
Я просто выдернул из своего исходника вызовы функций подряд. А ему всё равно про все почитать будет нужно...

---

← →
VMcL ©   (2004-12-09 22:54) [6]

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

---

← →
VMcL ©   (2004-12-09 22:55) [7]

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

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

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

---

← →
Kolan ©   (2004-12-10 00:34) [8]

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: 0.031 c