Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

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

Страницы: 1 2 3 >
Владислав © (2006-01-24 11:44:00)
Приветствую, Мастера.

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

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

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

Владислав (2006-01-25 15:15:00) [1]
В итоге решил положиться на то, что ключевому полю будут присваиваться последовательные значения. Посему для значений хеша решил взять младшие разряды значения поля в таблице.

Спасибо огромное всем за помощь!

Leonid Troyanovsky (2006-01-24 18:16:00) [2]

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

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

Дык, добавить все, а потом и сортировать.
При больших вставках так и делают.
Приурочить это дело к сеансам обмена с сервером.

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

--
Regards, LVT.

Leonid Troyanovsky (2006-01-24 18:09:00) [3]

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

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

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

Берем последний (с младшими разрядами) Longint и делаем
hash := a[4] and $3FF.

Только, эти списки поиска тоже надо поддерживать
(т.е., это тоже небесплатно).

--
Regards, LVT.

Leonid Troyanovsky (2006-01-24 17:56:00) [4]

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

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

Не, я имел ввиду такое преобразование, которое сохранит размер.
Т.е., 128 бит - это 4 клиентских Longint. Какой-нибудь пользовательский
тип данных и cast к нему. В общем, нужен запрос или хранимая
процедура, которая может быть использована для возвращения
клиенту вожделенных 128 бит (хотя бы в параметр).

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

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

В качестве хеш-функции я бы просто взял пятый элемент массива.

--
Regards, LVT.

Владислав (2006-01-24 17:30:00) [5]

> MBo © (24.01.06 17:11) [41]

Понял я в чем дело. С числами с рандомным набором цифр действительно равномерно.
Если же числа идут по порядку, все плохо. :)

MBo (2006-01-24 17:11:00) [6]
>только что-то со старшими битами совсем все плохо.

достаточно равномерное распределение при Shift=4..18

procedure MeanStdDev(const Data: array of Integer; var Mean, StdDev: Extended); var S: Extended; N, I: Integer; begin N := High(Data) - Low(Data) + 1; Mean := 0; for I := Low(Data) to High(Data) do Mean := Mean + Data[i]; Mean := Mean / N; S := 0; for I := Low(Data) to High(Data) do S := S + Sqr(Mean - Data[I]); StdDev := Sqrt(S / (N - 1)); end; procedure TForm1.Button1Click(Sender: TObject); var s: string; i, k: Integer; a: array[0..1023] of Integer; Shift: Byte; Mn, StdD: Extended; begin for Shift := 0 to 22 do begin FillChar(a, SizeOf(a), 0); for k := 1 to 100000 do begin s := ''; for i := 1 to 38 do s := s + Chr(Ord('0') + Random(10)); i := ElfHash(s); Inc(a[(i shr Shift) and 1023]); end; // for i := 0 to 1023 do Memo1.Lines.Add(IntToStr(a[i])); MeanStdDev(a, Mn, StdD); Memo1.Lines.Add(Format('%d %6.1f %6.1f', [Shift, Mn, StdD])); end; end;

Еще можно попробовать CRC16

Владислав (2006-01-24 17:07:00) [7]

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

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

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

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

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

Reindeer Moss Eater (2006-01-24 17:02:00) [8]
Ну тогда остается открытым вопрос о хеш функции :)

SYS.DBMS_CRYPTO_TOOLKIT.Hash
SYS.DBMS_CRYPTO_TOOLKIT.KeyedHash

Reindeer Moss Eater (2006-01-24 16:51:00) [9]
>Коллекция на клиенте. Ее на клиенте и нужно обновить.

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

Владислав (2006-01-24 16:42:00) [10]

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

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

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

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

Владислав (2006-01-24 16:36:00) [11]

> 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,
> экономия, все равно, существенная.

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

Leonid Troyanovsky (2006-01-24 16:29:00) [12]

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

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

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

--
Regards, LVT.

Reindeer Moss Eater (2006-01-24 16:28:00) [13]
Ну пусть это будет список таблиц БД. И мне коллекцию обрабатывать не нужно. Мне нужно привести ее в соответствие.

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

Leonid Troyanovsky (2006-01-24 16:20:00) [14]

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

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

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

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

--
Regards, LVT.

MBo (2006-01-24 16:15:00) [15]
>Leonid Troyanovsky © (24.01.06 16:12) [31]
>А зачем его сужать?
Я так понял, что автору это нужно. Возможно, неправ.

Владислав (2006-01-24 16:12:00) [16]

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

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

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

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

Leonid Troyanovsky (2006-01-24 16:12:00) [17]

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

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

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

--
Regards, LVT.

MBo (2006-01-24 16:07:00) [18]
>Диапазон хеш-значений не подходит. Попробую адаптировать
Если нужно сузить диапазон, то, если не ошибаюсь, лучше брать старшие биты

Leonid Troyanovsky (2006-01-24 16:00:00) [19]

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

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

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

--
Regards, LVT.

Reindeer Moss Eater (2006-01-24 16:00:00) [20]
А что внутри серверной коллекции ?
Навекрняка её можно обработать прямо на сервере.

Страницы: 1 2 3 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »