Хеш-функция.

← →
Владислав © (2006-01-24 11:44) [0]

Приветствую, Мастера.

Ситуация такая. Есть коллекции элементов, по которым производиться поиск элемента в коллекции по строке-идентификатору. Эти строки состоят из последовательностей символов с кодами #$30-#$39 (т.е. цифры).

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

P.S. До этого строка-идентификатор могла содержать любые символы латинского алфавита, цифры и некоторые другие символы. Простой xor всех символов в строке давал достаточно равномерное распределение хеш значений от 0 до 127. А как теперь поступить с цифрами?..

← →
Leonid Troyanovsky © (2006-01-24 11:57) [1]

> Владислав © (24.01.06 11:44)

> Ситуация такая. Есть коллекции элементов, по которым производиться
> поиск элемента в коллекции по строке-идентификатору. Эти
> строки состоят из последовательностей символов с кодами
> #$30-#$39 (т.е. цифры).

Я бы заменил такую строку на поле Longint, и искал бы по ней,
возможно, что даже без хеш-функции.

--
Regards, LVT.

← →
Владислав © (2006-01-24 12:22) [2]

> Leonid Troyanovsky © (24.01.06 11:57) [1]
>
> Я бы заменил такую строку на поле Longint, и искал бы по
> ней,
> возможно, что даже без хеш-функции.

Было бы замечательно, но эта строка - поле таблицы Oracle NUMBER(38). Не придумали такой тип целочисленный в Delphi, чтобы такие значения хранить.
Есть еще мысли?

← →
Reindeer Moss Eater © (2006-01-24 12:25) [3]

Double на клиенте для всех NUMBER Oracle.

Везде и всегда.

← →
Leonid Troyanovsky © (2006-01-24 13:07) [4]

213.234.193.250
> Владислав © (24.01.06 12:22) [2]

> Было бы замечательно, но эта строка - поле таблицы Oracle
> NUMBER(38).

И какой диапазон оно представляет? 2^38?
И как оно попадает в строку.

--
Regards, LVT.

← →
Владислав © (2006-01-24 13:19) [5]

> Leonid Troyanovsky © (24.01.06 13:07) [4]
>
> И какой диапазон оно представляет? 2^38?
> И как оно попадает в строку.

Диапазон NUMBER, в принципе, 1 x 10^-130 - 9.99 x10^125. Диапазон значений, которые теоретически могут встретиться в поле, с которым я работаю, от -10^38 + 1 до 10^38 - 1.
Строку возвращают компоненты DOA.

> Reindeer Moss Eater © (24.01.06 12:25) [3]
> Double на клиенте для всех NUMBER Oracle.
>
> Везде и всегда.

Сейчас подумаю...

← →
Владислав © (2006-01-24 13:37) [6]

> Reindeer Moss Eater © (24.01.06 12:25) [3]
> Double на клиенте для всех NUMBER Oracle.
>
> Везде и всегда.

Не годится.

procedure TfrmMain.Button4Click(Sender: TObject); var Val1: Double; Val2: Double; begin Val1 := -1E38; while Val1 < 1E38 do begin Val2 := Val1; Val1 := Val1 + 1; if Val1 = Val2 then begin ShowMessage("Приплыли"); Break; end; end; end;

← →
DiamondShark © (2006-01-24 13:50) [7]

> Простой xor всех символов в строке давал достаточно равномерное
> распределение хеш значений от 0 до 127. А как теперь поступить
> с цифрами?..

Преобразовать в целое число и сделать тот же побайтный xor.
Получится достаточно равномерное распределение от 0 до 255

> Было бы замечательно, но эта строка - поле таблицы Oracle
> NUMBER(38). Не придумали такой тип целочисленный в Delphi,
> чтобы такие значения хранить.

Как так не придумали?
array[0..N] of byte

← →
Leonid Troyanovsky © (2006-01-24 14:02) [8]

> Владислав © (24.01.06 13:19) [5]

> Диапазон NUMBER, в принципе, 1 x 10^-130 - 9.99 x10^125.
> Диапазон значений, которые теоретически могут встретиться
> в поле, с которым я работаю, от -10^38 + 1 до 10^38 - 1.

Т.е., 128 бит?
Тогда, лучше если компоненты возвращали б не строку, a GUID.
Во всяком случае, IsEqualGUID уже есть.

--
Regards, LVT.

← →
MBo © (2006-01-24 14:02) [9]

Elf-hash функция устроит?

← →
Leonid Troyanovsky © (2006-01-24 14:35) [10]

> Владислав © (24.01.06 11:44)

> Ситуация такая. Есть коллекции элементов, по которым производиться
> поиск элемента в коллекции по строке-идентификатору

Вообще-то, для быстрого поиска элемента можно воспользоваться
простой модификацией TList, содержащего индексы или идентификаторы
элементов. Этот список сортируется, а для поиска "ближайшего"
используется бинарный поиск Find:

http://groups.google.com/group/fido7.ru.delphi/msg/23b08e929a768df3

Однако, предварительное "хеширование" строкового представления
числа, например, в массив Longint должно ускорить процесс, бо
вместо строк длиной 38 символов сравниваться будут 16 байт(4х4).

--
Regards, LVT.

← →
Reindeer Moss Eater © (2006-01-24 14:49) [11]

Используй Double на клиенте.
И не сравнивай дабл на клиенте.
Зачем это надо?

Прочитав у записи number(38) в дабл на клиенте можно смело использовать его в параметрическом запросе. В оракле сравнение пройдет корректно и запись найдется.

← →
Reindeer Moss Eater © (2006-01-24 14:51) [12]

И уж тем более, зная, что у тебя только целочисленные значения в оракле, такого тупого сравнения как if Double1 = Double2 можно легко избежать.

← →
Leonid Troyanovsky © (2006-01-24 14:53) [13]

> Reindeer Moss Eater © (24.01.06 14:51) [12]
> И уж тем более, зная, что у тебя только целочисленные значения
> в оракле, такого тупого сравнения как if Double1 = Double2
> можно легко избежать.

Если оно б помещалось в 8 байт, то Int64 было б лучше Double.
Но, как выяснилось, там не менее 16 байт.

--
Regards, LVT.

← →
Reindeer Moss Eater © (2006-01-24 15:00) [14]

И что, разве диапазона Double не хватает для number(38)?

← →
Владислав © (2006-01-24 15:05) [15]

> MBo © (24.01.06 14:02) [9]
> Elf-hash функция устроит?

Что-то я не могу найти алгоритм, чтобы суть понять и под задачу адаптировать. Может кто-нибудь ткнет пальцем?

> Leonid Troyanovsky © (24.01.06 14:35) [10]

Не подходит. Элементы храняться в списке, но список этот уже отсортирован по другим критериям.

← →
Reindeer Moss Eater © (2006-01-24 15:06) [16]

Delphi:
Double 5.0 x 10^-324 .. 1.7 x 10^308

Oracle:
Number 1.0 x 10^-127 .. 9.9999999999999999999999999999999999999 x 10^121

← →
Владислав © (2006-01-24 15:09) [17]

> Reindeer Moss Eater © (24.01.06 14:49) [11]

Я уже понял Вашу мысль.
Вероятно я плохо объяснил свою проблему, что Вы не поняли, но мне нужен поиск именно на клиенте.

← →
Владислав © (2006-01-24 15:10) [18]

> Reindeer Moss Eater © (24.01.06 15:06) [16]

Осталось еще привести количество значащих цифр, чтобы до конца прояснить ситуацию...

← →
Reindeer Moss Eater © (2006-01-24 15:11) [19]

А в списке на клиенте дабл нельзя иметь?

← →
Владислав © (2006-01-24 15:16) [20]

> Reindeer Moss Eater © (24.01.06 15:11) [19]
> А в списке на клиенте дабл нельзя иметь?

Можно. Но в [6] я привел код, который показывает, что такое решение не работает из-за разницы в количестве значащих цифр.

← →
Leonid Troyanovsky © (2006-01-24 15:31) [21]

> Владислав © (24.01.06 15:05) [15]

> Не подходит. Элементы храняться в списке, но список этот
> уже отсортирован по другим критериям.

Никто не мешает для этого воспользоваться отдельным списком,
который будет ссылаться на индексы (указатели) первого списка.

Т.е., использовать этот список только для быстрого поиска.
Это всего лишь своебразный индекс.

--
Regards, LVT.

← →
MBo © (2006-01-24 15:35) [22]

На паскале для понятности и вдвое быстрее - на асме (© Sha)
function ElfHashPas(const s: string): Integer; var i, h, g: Integer; begin h := 0; for i := 1 to Length(s) do begin h := h shl 4 + Byte(s[i]); g := h and $F0000000; if g <> 0 then h := h xor (g shr 24); h := h and (not g); end; Result := h; end; function ElfHash(const s: string): integer; asm mov edx, eax xor eax, eax test edx, edx jz @Ret sub eax, [edx-4] jz @Ret mov ecx, eax sub edx, eax xor eax, eax push ebx @Loop: movzx ebx, [edx+ecx] add ebx, eax lea eax, [ebx+ebx] shr ebx, 20 lea eax, [8*eax] and ebx, $0F00 xor eax, ebx add ecx, 1 jnz @Loop shr eax, 4 pop ebx @Ret: end;

← →
Владислав © (2006-01-24 15:37) [23]

> Leonid Troyanovsky © (24.01.06 15:31) [21]

Вставка элемента в коллекцию также критична по времени. Вставка в сортированный список займет время.
По тому критерию, по которому коллекция отсортирована сейчас, так она отсортирована сервером.

← →
Reindeer Moss Eater © (2006-01-24 15:39) [24]

А нельзя ли вообще исключить из этого процесса клиента?

← →
Leonid Troyanovsky © (2006-01-24 15:52) [25]

> Владислав © (24.01.06 15:37) [23]

> Вставка элемента в коллекцию также критична по времени.
> Вставка в сортированный список займет время.

Поиск позиции для вставки в отсортированный список - log(n).

Кроме того, чудес на свете не бывает.
Т.е., быстрее ищем - больше приседаний для подготовки.
Поиск с помощью хеш-функции имеет сложность ~ o(n).
Против log(n) бинарного поиска.

Так, что считай сам, сколько добавлений, сколько поисков.

И еще, полезность предварительного хеширования в массив Longint
для меня уже почти очевидна. Например, строка в 40 цифр без
особых усилий превращается в a[0..5] of Longint, т.е. по 8 цифр.

--
Regards, LVT.

← →
Владислав © (2006-01-24 15:52) [26]

> MBo © (24.01.06 15:35) [22]

Спасибо. Это я нашел. Диапазон хеш-значений не подходит. Попробую адаптировать...

> Reindeer Moss Eater © (24.01.06 15:39) [24]
> А нельзя ли вообще исключить из этого процесса клиента?

Есть коллекция на клиенте, есть таблице в БД.
Нужно привести коллекцию в соответсвие, если данные в таблице изменились. При этом хотелось бы получить приемлемое быстродействие при наличии порядка 100000 записей.
Может быть и есть другие варианты, но они должны вписаться в уже существующую архитектуру приложения.

← →
Reindeer Moss Eater © (2006-01-24 16:00) [27]

А что внутри серверной коллекции ?
Навекрняка её можно обработать прямо на сервере.

← →
Leonid Troyanovsky © (2006-01-24 16:00) [28]

> Владислав © (24.01.06 15:52) [26]

> Есть коллекция на клиенте, есть таблице в БД.

А..
Ну, проще всего, если сервер будет давать (и брать) клиенту
идентификаторы в виде набора Longint, т.е. 4 достаточно.

--
Regards, LVT.

>Диапазон хеш-значений не подходит. Попробую адаптировать
Если нужно сузить диапазон, то, если не ошибаюсь, лучше брать старшие биты

> Reindeer Moss Eater © (24.01.06 16:00) [27]

Что в этой коллекции, по большому счету, не имеет никого значения. Ну пусть это будет список таблиц БД. И мне коллекцию обрабатывать не нужно. Мне нужно привести ее в соответствие.

> Leonid Troyanovsky © (24.01.06 16:00) [28]

В таблице есть уникальный индекс типа NUMBER(38). Поля, совместимого с Longint нет. Изменить структуру таблицы я не могу.

> MBo © (24.01.06 16:07) [29]

> Если нужно сузить диапазон, то, если не ошибаюсь, лучше
> брать старшие биты

А зачем его сужать?

--
Regards, LVT.

> Владислав © (24.01.06 16:12) [30]

> В таблице есть уникальный индекс типа NUMBER(38). Поля,

Ну, думаю, в Oracle, есть какой-нибудь прием, позволяющий
поместить 128 битное значение (хоть как varchar) в массив Longint.

А если уж нет, то руками преобразовать в 5 Longint,
экономия, все равно, существенная.

--
Regards, LVT.

Ну пусть это будет список таблиц БД. И мне коллекцию обрабатывать не нужно. Мне нужно привести ее в соответствие.

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

> MBo © (24.01.06 16:15) [32]

> >А зачем его сужать?
> Я так понял, что автору это нужно. Возможно, неправ.

Неправ будет возжелавший оного :)

--
Regards, LVT.

> Leonid Troyanovsky © (24.01.06 15:52) [25]
>
>
> Поиск позиции для вставки в отсортированный список - log(n).
>

Да, но Insert(0), к примеру, в TList притянет за собой сдвиг большого массива. Сдвиг, к сожалению, и так есть, поскольку коллекции используются (TCollection), плюс будет еще один...

> MBo © (24.01.06 16:15) [32]

Правы, только что-то со старшими битами совсем все плохо. :)

> Leonid Troyanovsky © (24.01.06 16:20) [33]
>
> Ну, думаю, в Oracle, есть какой-нибудь прием, позволяющий
> поместить 128 битное значение (хоть как varchar) в массив
> Longint.

А какой выигрыш в преобразовании на сервере? Кроме того NUMBER компактнее. При большом объеме данных и передачи по сети только проиграю.

>
> А если уж нет, то руками преобразовать в 5 Longint,
> экономия, все равно, существенная.

Ну тогда остается открытым вопрос о хеш функции :)

> Reindeer Moss Eater © (24.01.06 16:28) [34]
>
> Так средств самого оракла не хватает, чтобы привести в соответствие
> эту коллекцию? Тем более, что выше шла речь о сотнях тысяч
> записей.

Хммм... Я что-то опять непонятно объясняю?..
Коллекция на клиенте. Ее на клиенте и нужно обновить.

> Leonid Troyanovsky © (24.01.06 16:29) [35]
>
> Неправ будет возжелавший оного :)

Поясните пожалуйста.
Меня бы вполне устроил диапазон хеш значений от 0 до 1023 плюс перебор до 1000 элементов для поиска.

>Коллекция на клиенте. Ее на клиенте и нужно обновить.

Это я непонятно объясняю.
Забыть про обработку коллекции на клиенте.
Обработать её на сервере, а клиенту отдать готовый результат.

Ну тогда остается открытым вопрос о хеш функции :)

SYS.DBMS_CRYPTO_TOOLKIT.Hash
SYS.DBMS_CRYPTO_TOOLKIT.KeyedHash

> Reindeer Moss Eater © (24.01.06 16:51) [38]
> >Коллекция на клиенте. Ее на клиенте и нужно обновить.
>
> Это я непонятно объясняю.
> Забыть про обработку коллекции на клиенте.

Еще раз. Коллекция на клиенте НЕ обрабатывается. Обрабатываться может какой-то элемент. Точнее, он может изменяться, удаляться, создаваться пользователем. Я не могу просто уничтожить элемент коллекции на клиенте потому, что он может быть открыт для редактирования/просмотра пользователем.

> Обработать её на сервере, а клиенту отдать готовый результат.

Первый раз именно так и происходит. А в последующем нужно обновление.

P.S. Подскажите алгоритм хеширования. :)

Хеш-функция. Найти похожие ветки