Не могу до конца понять двойное хеширование (перемешанные таблицы)

[FasterHarder]

Всем программистам привет! Respect!
Подскажите чтобы окончательно понять метод двойного хеширования!...
в общем разобрался с перемешанными таблицами, использующими перемешивание сложением (открытая адресация) и использующими перемешивание сцеплением...
нашел немного теории про двойное хеширование:

Для обеспечения равномерного распределения ключей в хэш-таблице при наличии коллизий можно применять метод двойного хэширования.
Он состоит в том, что если при включении или поиска ключа в хэш-таблице возникает коллизия, то к ключу (или к комбинации ключа и текущего
индекса массива) применяется вторичная хэш-функция, значение которой указывает циклическое смещение в массиве от текущего индекса к
элементу, в который следует включать или в котором следует искать требуемую запись

мне все понятно, кроме: "значение которой указывает циклическое смещение в массиве от текущего индекса к элементу"

например, если брать перемешивание сцеплением и обрабатывать целых числа, то функцию расстановки (хеш-функцию) можно применить как взятие остатка при делении на 10, т е для чисел 12, 48, 3, 5, 7, 63, 15, 202, 103, 188, 30, 43, 6, 18, 19 получим таблицу:
0-30
1-пусто
2-12-202
3-3-63-103-43
4-пусто
5-5-15
6-6
7-7
8-48-188-18
9-19

можно ли как-нибудь для этого случая воспользоваться двойным хешированием или нет?...и что означает "значение которой указывает циклическое смещение в массиве от текущего индекса к элементу"? (хотя бы пример любой на пальцах)...

подскажите как быть то??..буду очень признателен....

Сообщение отредактировано: FasterHarder - 21.12.10, 10:40

[MBo]

Пусть хэш-таблица длиной L. И даны две строки A и B.
Их хэш-коды первого уровня H1(A) и H1(B).
Если H1(A) <> H1(B), то индексы А и B в таблице - определенЫ.
Если же H1(A) = H1(B), то вычисляется H2(B), и индекс второй строки будет (H1(B) + H2(B)) mod L.
Вот эта операция взятия модуля и называется циклическим смещением.

[FasterHarder]

MBo, начинаю потихоньку понимать, а если будет, что:
позиция (H1(B) + H2(B)) mod L УЖЕ занята (т е на какой то предшествующей операции уже туда попал элемент), что тогда???

Добавлено 21.12.10, 13:08
т е вариант, когда вставляются одинаковые элементы...

Добавлено 21.12.10, 13:12
и можно ли привести какой либо вариант на натуральных числах с функцией расстановки I(N % 10) использующей двойное хеширование??

[Pavia]

MBo
По моему неправильно.

С двойным хэшированием я плохо знаком теория такая.
Пусть у нас есть таблица. Которая частично заполнена.
Так вот беря h1(A) мы смотрим что у нас в этой таблице пусто хорошо. Уже что-то лжит плохо. Имеем место коллизия? Как бороться? Надо положить в "соседнию" свободную ячейку.

Так вот таких строк может быть много. Ну посчитали мы второй хэш а вдруг опять коллизия. Такое не годится.
Как выбрать "соседнию"? Так вот идея первая круговая. Просто увеличиваем индекс J. (H1(A)+j) mod L до тех пор пока не найдется свободное место. J и означает цикличность. Но такая группировка не всегда хорошая. Поэтому придумали ряд модификаций.

Линейная (H1(A)+j*k)mod L квадратичная (H1(A)+j*k1+j*j*k2) mod L. А есть идея использовать второй хэш (H1(A)+j*H2(A)) mod L.

Добавлено 21.12.10, 13:20
http://en.wikipedia.org/wiki/Double_hashing

[FasterHarder]

Цитата Pavia @ 21.12.10, 13:19

Как выбрать "соседнию"? Так вот идея первая круговая. Просто увеличиваем индекс J. (H1(A)+j) mod L до тех пор пока не найдется свободное место.

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

[MBo]

>позиция (H1(B) + H2(B)) mod L УЖЕ занята
тогда проверяется (H1(B) + 2 * H2(B)) mod L
и т.д.


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


пример кода с дв. хэшированием есть тут: http://ru.wikipedia.org/wiki/Хеш-таблица
(обрати внимание, что второй хэш не может быть нулевым - чтобы сдвиг обязательно был)

Добавлено 21.12.10, 13:29
Pavia
>По моему неправильно.
Не увидел особой разницы в наших краткоописаниях.

[FasterHarder]

Цитата MBo @ 21.12.10, 13:24

тогда проверяется (H1(B) + 2 * H2(B)) mod L

примерно понятно..

N.B. правда ведь возможен вариант вроде, когда это зациклится...

[MBo]

>возможен вариант вроде, когда это зациклится...
Что значит зациклится? Размер таблицы не зря выбирают из простых чисел.

[Pavia]

FasterHarder
Здесь всё описано.
http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF
Правда применительно к линейной. Но думаю на двойное хэширование тоже распространяется.
Ну если вы перебрали j от 0 до L и всё занято, то просто увеличиваете таблицу (Увеличить L). А для тех у кого туго с английским, то лучше увеличивать не дожидаясь 100% заполнения, а гораздо раньше.

[FasterHarder]

Цитата MBo @ 21.12.10, 16:39

Что значит зациклится? Размер таблицы не зря выбирают из простых чисел.

ааа, вот оно что..понятно...