Изменения
добавлен псевдокод
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
==Простая реализация==
===Вставка===
<pre>insert(item){
x = h1(item.key)
y = h2(item.key)
for (i = 0; i < m; i++){
if (table[x] == null){
table[x] = item
return
}
x = (x + y) % m
}
error() //ошибка, требуется увеличить размер таблицы
}</pre>
===Поиск===
<pre>search(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){
if (table[x] != null)
if (table[x].key == key)
return table[x]
else
return null
x = (x + y) % m
}
return null
}</pre>
==Реализация с удалением==
===Вставка===
<pre>insert(item){
x = h1(item.key)
y = h2(item.key)
for (i = 0; i < m; i++){
if (table[x] == null || deleted[x]){
table[x] = item
deleted[x] = false
return
}
x = (x + y) % m
}
error() //ошибка, требуется увеличить размер таблицы
}</pre>
===Поиск===
<pre>search(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){
if (table[x] != null)
if (table[x].key == key && !deleted[x])
return table[x]
else
return null
x = (x + y) % m
}
return null
}</pre>
===Удаление===
<pre>remove(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){
if (table[x] != null)
if (table[x].key == key)
deleted[x] = true
else
return
x = (x + y) % m
}
}</pre>
==См. также==
* [[Хеширование]]
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Поиск_свободного_места_при_закрытом_хешировании|Поиск свободного места при закрытом хешировании]]
== Литература ==
* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, ''2010''* Седжвик Р. - 1296с'''Фундаментальные алгоритмы на C. — ISBN 978-5-8459-0857Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', 0''2003'' ==Ссылки==* [http://en.wikipedia.org/wiki/Double_hashing Double_hashing]* [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-072001-013151-12 Пример хеш таблицы]* [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием] [[Категория:Дискретная математика и алгоритмы]] [[Категория:Хеширование]]
