Функция хеширования стринга.

← →
Ш-К (2007-02-28 16:20) [0]

Вот стандартная функция:
function TextHash(const S: string): cardinal; const cLongBits = 32; cOneEight = 4; cThreeFourths = 24; cHighBits = $F0000000; var I: integer; P: PChar; Temp: cardinal; begin { TODO : I should really be processing 4 bytes at once... } Result := 0; P := PChar(S); I := Length(S); while I > 0 do begin Result := (Result shl cOneEight) + Ord(UpCase(P^)); Temp := Result and cHighBits; if Temp <> 0 then Result := (Result xor (Temp shr cThreeFourths)) and (not cHighBits); Dec(I); Inc(P); end; end;

Могут ли подобные функции хешировать 11 символьный стринг уникально?

← →
Джо © (2007-02-28 16:26) [1]

> [0] Ш-К (28.02.07 16:20)
> Могут ли подобные функции хешировать 11 символьный стринг
> уникально?

Собственно, хэш-функция без коллизий — это уже не хэш-функция, а шифрование или компрессия.

← →
Джо © (2007-02-28 16:36) [2]

> [1] Джо © (28.02.07 16:26)

Сорри, так криво выразился, что лучше бы уже и не встревал. Все от спешки.

← →
Ш-К (2007-02-28 16:41) [3]

Джо © (28.02.07 16:26) [2]
Можно и так сказать. Без разницы.

Вообщем, возможно ли однозначно сопоставить строке < 11 символов 8-байтный идентификатор? Или 4- байтный?
И есть ли (какая) зависимость между длиной строки и размером хеш-индекса? Из известных.

← →
Rouse_ © (2007-02-28 16:46) [4]

Уникально даже MD5 не хеширует...

← →
Сергей М. © (2007-02-28 16:52) [5]

> возможно ли однозначно сопоставить строке < 11 символов
> 8-байтный идентификатор?

Невозможно. Но вероятность совпадений при неких заранее определенных условиях, накладываемых на содержание потенциально хэшируемых строк, может быть ничтожно мала.

> Или 4- байтный?

Вероятность возрастает.

Ш-К (28.02.07 16:41) [3]
Вообщем, возможно ли однозначно сопоставить строке < 11 символов 8-байтный идентификатор?

Мдя.. А если подумать??? Можно ли целому числу из диапазона 0..2^88 - 1 _однозначно_ сопоставить число из диапазона 0..2^64 - 1 ???

> Ш-К (28.02.2007 16:20:00) [0]

Нельзя, на 256^11 приходитс всего 256^8 комбинаций, на каждый хеш приходится по 256^3 значений.

← →
Ш-К (2007-03-01 19:24) [8]

Абсолютно согласен со всеми. Немного перемудрил.
Вообще-то я говорил не о произвольной последовательности байт, а строке с "валидными" символами. Например, только кириллица.

Функция хеширования стринга. Найти похожие ветки