| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Функция хеширования стринга.
Ш-К © (2007-02-28 16:20:00)Вот стандартная функция:
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-03-01 19:24:00) [1]Абсолютно согласен со всеми. Немного перемудрил.
Вообще-то я говорил не о произвольной последовательности байт, а строке с "валидными" символами. Например, только кириллица.
Anatoly Podgoretsky (2007-02-28 19:30:00) [2]> Ш-К (28.02.2007 16:20:00) [0]
Нельзя, на 256^11 приходитс всего 256^8 комбинаций, на каждый хеш приходится по 256^3 значений.
jack128 (2007-02-28 17:30:00) [3]Ш-К (28.02.07 16:41) [3]
Вообщем, возможно ли однозначно сопоставить строке < 11 символов 8-байтный идентификатор?
Мдя.. А если подумать??? Можно ли целому числу из диапазона 0..2^88 - 1 _однозначно_ сопоставить число из диапазона 0..2^64 - 1 ???
Сергей М. (2007-02-28 16:52:00) [4]
> возможно ли однозначно сопоставить строке < 11 символов
> 8-байтный идентификатор?
Невозможно. Но вероятность совпадений при неких заранее определенных условиях, накладываемых на содержание потенциально хэшируемых строк, может быть ничтожно мала.
> Или 4- байтный?
Вероятность возрастает.
Rouse_ (2007-02-28 16:46:00) [5]Уникально даже MD5 не хеширует...
Ш-К (2007-02-28 16:41:00) [6]Джо © (28.02.07 16:26) [2]
Можно и так сказать. Без разницы.
Вообщем, возможно ли однозначно сопоставить строке < 11 символов 8-байтный идентификатор? Или 4- байтный?
И есть ли (какая) зависимость между длиной строки и размером хеш-индекса? Из известных.
Джо (2007-02-28 16:36:00) [7]> [1] Джо © (28.02.07 16:26)
Сорри, так криво выразился, что лучше бы уже и не встревал. Все от спешки.
Джо (2007-02-28 16:26:00) [8]> [0] Ш-К (28.02.07 16:20)
> Могут ли подобные функции хешировать 11 символьный стринг
> уникально?
Собственно, хэш-функция без коллизий — это уже не хэш-функция, а шифрование или компрессия.
| |
