3. Двойное хеширование

h(key,i)=(h1(key)+ih2(key)) mod hashTableSize

арифметическая прогрессия по модулю mспервым членом h1(key) и шагом

h2(key)

h1 (key)=key mod hashTableSize

h2 (key)=1+(key mod hashTableSize’)

►пример

8881234, 8882345,8883456,8884321,8886543 hashTableSize =11

h1(key)= key mod 11 h2(key)= key mod 7 h1(8881234)=88812234 mod 11 = 10 h1(8882345)= 8882345 mod 11= 10 (coll) h2 (8882345)=8882345 mod 7 =3 h1(8883456)=8883456 mod 11 = 10 (coll) h2(8883456)=8883456 mod 7 =1

h1(8884321)=8884321 mod 11 =6

h1(8886543)=8886543 mod 11 =6(coll) h2(8885432)=8885432 mod 7 =3 (coll)

Реализация

//----------------------------

вставка элемента

//----------------найти по ключу, вернуть индекс в таблице

//------------------------

удаление элемента по ключу

Исследование времени

хэш-таблица - совокупность связанных списков

Размер	Время
таблицы ,	поиска,
hashTableSize	µs
1	869
2	432
4	214
8	106
16	54
32	28
64	15
128	9
256	6
512	4
1024	4
2048	3
4096	3
8192	3

эффективность

►Коэффициент загрузки должен быть 0.2 до 0.7

►Количество ячеек в хэше простое число

►Алгоритм хэширования надо

тестировать на простых и критических наборах

►Конфликты лучше решать с помощью цепочек