Разрешение коллизий — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 100 промежуточных версий 17 участников)
Строка 1: Строка 1:
'''Разрешение коллизий''' в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки а можно открытую адресацию.
+
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.  
  
При использовании списков такой проблемы не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто добавить элемент в начало списка.
+
== Разрешение коллизий с помощью цепочек ==
 +
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
 +
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
  
[[Открытое и закрытое хеширование#Закрытое хеширование|Закрытое хеширование]] работает иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята - необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.
+
В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна <tex>O(1)</tex>. Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за <tex>O(n)</tex>
  
== Стратегии поиска ==
+
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
 +
 
 +
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.
 +
 
 +
== Линейное разрешение коллизий ==
 +
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 +
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
 +
 
 +
=== Стратегии поиска ===
  
 
''' Последовательный поиск '''
 
''' Последовательный поиск '''
Строка 18: Строка 28:
 
По сути последовательный поиск - частный случай линейного, где <tex>q=1</tex>.
 
По сути последовательный поиск - частный случай линейного, где <tex>q=1</tex>.
  
[[Файл:hashtables2.png|400px|Линейный поиск с шагом q.]]
+
[[Файл:Hashtables56.PNG|400px|Линейный поиск с шагом q.]]
  
 
''' Квадратичный поиск '''
 
''' Квадратичный поиск '''
Строка 26: Строка 36:
 
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
 
[[Файл:hashtables3.png|400px|Квадратичный поиск.]]
  
== Проверка наличия элемента в таблице==
+
=== Проверка наличия элемента в таблице===
  
 
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
 
Проверка осуществляется аналогично добавлению: мы проверяем ячейку <tex>i</tex> и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.
  
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца. Однако, если мы придём в ту ячейку, откуда начинался поиск, то добавить элемент в текущую таблицу будет невозможно и необходимо провести операцию перехеширования.
+
При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.
 +
 
 +
=== Проблемы данных стратегий ===
 +
 
 +
Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров  — последовательностей занятых ячеек.
 +
 
 +
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
 +
Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
 +
 
 +
=== Удаление элемента без пометок ===
 +
 
 +
Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на <tex>q</tex> позиций назад. При этом:
 +
* если в цепочке встречается элемент с другим хешем, то он должен остаться на своём месте (такая ситуация может возникнуть если оставшаяся часть цепочки была добавлена позже этого элемента)
 +
* в цепочке не должно оставаться "дырок", тогда любой элемент с данным хешем будет доступен из начала цепи
 +
 
 +
Учитывая это будем действовать следующим образом: при поиске следующего элемента цепочки будем пропускать все ячейки с другим значением хеша, первый найденный элемент копировать в текущую ячейку, и затем рекурсивно его удалять. Если такой следующей ячейки нет, то текущий элемент можно просто удалить, сторонние цепочки при этом не разрушатся (чего нельзя сказать про случай квадратичного поиска).
 +
 
 +
 
 +
''' Псевдокод '''
 +
 
 +
'''function''' delete('''Item''' i):
 +
      j = i + q
 +
      '''while''' table[j] == ''null'' '''or''' table[j].key != table[i].key
 +
        '''if''' table[j] == ''null''
 +
            table[i] = ''null''
 +
            '''return'''
 +
        j += q
 +
      table[i] = table[j]
 +
      delete(j)   
 +
 
 +
Хеш-таблицу считаем зацикленной
 +
 
  
== Проблемы данных стратегий ==
+
{{Утверждение
 +
|about=о времени работы
 +
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
 +
|proof=
 +
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{---}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
 +
}}
  
Проблем две - крайне нетривиальное удаление элемента из таблицы и образование кластеров.
+
Вариант с зацикливанием мы не рассматриваем, поскольку если <tex>q</tex> взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций
Кластер - последовательность занятых клеток. Их наличие замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
+
 
Для защиты от кластеризации используется Двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
+
 
 +
Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.
 +
* В редактируемой цепи не остаётся дырок
 +
Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце <tex>\mathrm{delete}</tex> (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.
 +
* Элементы, которые уже на своих местах, не должны быть сдвинуты.
 +
Это учтено.
 +
* В других цепочках не появятся дыры
 +
Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на <tex>q</tex> позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.
  
 
==Двойное хеширование==
 
==Двойное хеширование==
'''Двойное хеширование''' {{---}} метод борьбы с коллизиями, возникающими при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
+
'''Двойное хеширование''' (англ. double hashing) {{---}} метод борьбы с коллизиями, возникающими при открытой адресации, основанный на использовании двух хеш-функций для построения различных последовательностей исследования хеш-таблицы.
  
 
===Принцип двойного хеширования===
 
===Принцип двойного хеширования===
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \mod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) +  h_2(k)) \mod m </tex>, затем <tex> (h_1(k) +  2 \cdot h_2(k)) \mod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) +  i \cdot h_2(k)) \mod m </tex> где <tex>  i = (0, 1, \; ... \;,  m - 1) </tex>
+
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex>n \bmod m </tex> {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) +  h_2(k)) \bmod m </tex>, затем <tex> (h_1(k) +  2 \cdot h_2(k)) \bmod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) +  i \cdot h_2(k)) \bmod m </tex> где <tex>  i = (0, 1, \; ... \;,  m - 1) </tex>
  
 
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
 
Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].
Строка 59: Строка 112:
 
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
 
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
  
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \mod (m-1) + 1 </tex>
+
Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \bmod (m-1) + 1 </tex>
  
 
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
 
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
Строка 68: Строка 121:
  
 
<center>
 
<center>
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \mod 13 </tex>
+
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 </tex>
 
</center>
 
</center>
  
 
<center>
 
<center>
<tex> h_1(k) = k \mod 13 </tex>
+
<tex> h_1(k) = k \bmod 13 </tex>
 
</center>
 
</center>
  
 
<center>
 
<center>
<tex> h_2(k) = 1 + k \mod 11 </tex>
+
<tex> h_2(k) = 1 + k \bmod 11 </tex>
 
</center>
 
</center>
  
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \mod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \mod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
+
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ.
  
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
 
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
Строка 89: Строка 142:
  
 
'''Вставка'''
 
'''Вставка'''
<pre>add(item)
+
'''function''' add('''Item''' item):
  x = h1(item.key)
+
      x = h1(item.key)
  y = h2(item.key)
+
      y = h2(item.key)
  for (i = 0; i < m; i++)   
+
      '''for''' (i = 0..m)   
      if table[x] == null
+
        '''if''' table[x] == ''null''
        table[x] = item
+
            table[x] = item
        return       
+
            '''return'''      
      x = (x + y) mod m   
+
        x = (x + y) '''mod''' m   
  table.resize() //ошибка, требуется увеличить размер таблицы</pre>
+
      table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
  
 
'''Поиск'''
 
'''Поиск'''
<pre>search(key)
+
'''Item''' search('''Item''' key):
  x = h1(key)
+
      x = h1(key)
  y = h2(key)
+
      y = h2(key)
  for (i = 0; i < m; i++)
+
      '''for''' (i = 0..m)
      if table[x] != null
+
        '''if''' table[x] != ''null''
        if table[x].key == key
+
            '''if''' table[x].key == key
            return table[x]
+
              '''return''' table[x]
      else
+
        '''else'''
        return null
+
            '''return''' ''null''
      x = (x + y) mod m   
+
        x = (x + y) '''mod''' m   
  return null</pre>
+
      '''return''' ''null''
  
 
===Реализация с удалением===
 
===Реализация с удалением===
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
+
Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
  
 
'''Вставка'''
 
'''Вставка'''
<pre>add(item)
+
'''function''' add('''Item''' item):
  x = h1(item.key)
+
      x = h1(item.key)
  y = h2(item.key)
+
      y = h2(item.key)
  for (i = 0; i < m; i++
+
      '''for''' (i = 0..m) 
      if table[x] == null || deleted[x]
+
        '''if''' table[x] == '''null''' '''or''' deleted[x]
        table[x] = item
+
            table[x] = item
        deleted[x] = false
+
            deleted[x] = '''false'''
        return       
+
            '''return'''      
      x = (x + y) mod m   
+
        x = (x + y) '''mod''' m   
  table.resize() //ошибка, требуется увеличить размер таблицы</pre>
+
      table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
 
 
 
'''Поиск'''
 
'''Поиск'''
<pre>search(key)
+
'''Item''' search('''Item''' key):
  x = h1(key)
+
      x = h1(key)
  y = h2(key)
+
      y = h2(key)
  for (i = 0; i < m; i++)  
+
      '''for''' (i = 0..m)  
      if table[x] != null
+
        '''if''' table[x] != '''null'''
        if table[x].key == key && !deleted[x]
+
            '''if''' table[x].key == key '''and''' !deleted[x]
            return table[x]
+
              '''return''' table[x]
      else
+
        '''else'''
        return null
+
            '''return''' '''null'''
      x = (x + y) mod m   
+
        x = (x + y) '''mod''' m   
  return null</pre>
+
      '''return''' '''null'''
  
 
'''Удаление'''
 
'''Удаление'''
<pre>remove(key)
+
'''function''' remove('''Item''' key):
  x = h1(key)
+
      x = h1(key)
  y = h2(key)
+
      y = h2(key)
  for (i = 0; i < m; i++)
+
      '''for''' (i = 0..m)
      if table[x] != null
+
        '''if''' table[x] != '''null'''
        if table[x].key == key
+
            '''if''' table[x].key == key
            deleted[x] = true
+
              deleted[x] = '''true'''
      else  
+
        '''else'''
        return
+
            '''return'''
      x = (x + y) mod m</pre>
+
        x = (x + y) '''mod''' m
  
== Разрешение коллизий с помощью списков ==
+
==Альтернативная реализация метода цепочек==
 +
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данныx типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
  
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
+
[[Файл:Hashing_in_Java8.png|500px|Хеширование в Java 8.]]
 
 
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.
 
 
 
[[Файл:open_hash.png|420px|Разрешение коллизий при помощи цепочек.]]
 
 
 
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
 
 
 
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.
 
  
 
==См. также==
 
==См. также==
 
* [[Хеширование]]
 
* [[Хеширование]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
 +
* [[Идеальное_хеширование|Идеальное хеширование]]
  
== Литература ==
+
== Источники информации ==
* Бакнелл Дж. М. '''Фундаментальные алгоритмы и структуры данных в Delphi''', ''2003''
+
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
* Кнут Д. Э. '''Искусство программирования, том 3. Сортировка и поиск''', ''2-е издание, 2000''
+
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''', ''2010''
+
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0
* Седжвик Р. '''Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск''', ''2003''
+
* Седжвик Р. «Фундаментальные алгоритмы на C. Части 1-4. Анализ. Структуры данных. Сортировка. Поиск», 2003
 
+
* [http://openjdk.java.net/jeps/180 Handle Frequent HashMap Collisions with Balanced Trees]
==Ссылки==
 
 
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
 
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia {{---}} Double_hashing]
 
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Разрешение коллизий]
 
* [http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0 Разрешение коллизий]
Строка 182: Строка 227:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]
 +
[[Категория: Структуры данных]]

Текущая версия на 19:28, 4 сентября 2022

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

Разрешение коллизий с помощью цепочек

Разрешение коллизий при помощи цепочек.

Каждая ячейка [math]i[/math] массива [math]H[/math] содержит указатель на начало списка всех элементов, хеш-код которых равен [math]i[/math], либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна [math]O(1)[/math]. Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за [math]O(n)[/math]

Время работы поиска в наихудшем случае пропорционально длине списка, а если все [math]n[/math] ключей захешировались в одну и ту же ячейку (создав список длиной [math]n[/math]) время поиска будет равно [math]\Theta(n)[/math] плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех [math]n[/math] элементов.

Удаления элемента может быть выполнено за [math]O(1)[/math], как и вставка, при использовании двухсвязного списка.

Линейное разрешение коллизий

Пример хеш-таблицы с открытой адресацией и линейным пробированием.

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

Стратегии поиска

Последовательный поиск

При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+1, i+2, i+3[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент.

Последовательный поиск, частный случай линейного поиска.

Линейный поиск

Выбираем шаг [math]q[/math]. При попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math]i+(1 \cdot q), i+(2 \cdot q), i+(3 \cdot q)[/math] и так далее, пока не найдём свободную ячейку. В неё и запишем элемент. По сути последовательный поиск - частный случай линейного, где [math]q=1[/math].

Линейный поиск с шагом q.

Квадратичный поиск

Шаг [math]q[/math] не фиксирован, а изменяется квадратично: [math]q = 1,4,9,16...[/math]. Соответственно при попытке добавить элемент в занятую ячейку [math]i[/math] начинаем последовательно просматривать ячейки [math] i+1, i+4, i+9[/math] и так далее, пока не найдём свободную ячейку.

Квадратичный поиск.

Проверка наличия элемента в таблице

Проверка осуществляется аналогично добавлению: мы проверяем ячейку [math]i[/math] и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку.

При поиске элемента может получится так, что мы дойдём до конца таблицы. Обычно поиск продолжается, начиная с другого конца, пока мы не придём в ту ячейку, откуда начинался поиск.

Проблемы данных стратегий

Проблем две — крайне нетривиальное удаление элемента из таблицы и образование кластеров — последовательностей занятых ячеек.

Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер. Для защиты от кластеризации используется двойное хеширование и хеширование кукушки.

Удаление элемента без пометок

Рассуждение будет описывать случай с линейным поиском хеша. Будем при удалении элемента сдвигать всё последующие на [math]q[/math] позиций назад. При этом:

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

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


Псевдокод

function delete(Item i):
     j = i + q
     while table[j] == null or table[j].key != table[i].key
        if table[j] == null
           table[i] = null
           return
        j += q
     table[i] = table[j]
     delete(j)    

Хеш-таблицу считаем зацикленной


Утверждение (о времени работы):
Асимптотически время работы [math]\mathrm{delete}[/math] и [math]\mathrm{find}[/math] совпадают
[math]\triangleright[/math]
Заметим что указатель [math]j[/math] в каждой итерации перемещается вперёд на [math]q[/math] (с учётом рекурсивных вызовов [math]\mathrm{delete}[/math]). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего — с учётом вызова [math]\mathrm{find}[/math] собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
[math]\triangleleft[/math]

Вариант с зацикливанием мы не рассматриваем, поскольку если [math]q[/math] взаимнопросто с размером хеш-таблицы, то для зацикливания в ней вообще не должно быть свободных позиций


Теперь докажем почему этот алгоритм работает. Собственно нам требуется сохранение трёх условий.

  • В редактируемой цепи не остаётся дырок

Докажем по индукции. Если на данной итерации мы просто удаляем элемент (база), то после него ничего нет, всё верно. Если же нет, то вызванный в конце [math]\mathrm{delete}[/math] (см. псевдокод) заметёт созданную дыру (скопированный элемент), и сам, по предположению, новых не создаст.

  • Элементы, которые уже на своих местах, не должны быть сдвинуты.

Это учтено.

  • В других цепочках не появятся дыры

Противное возможно только в том случае, если какой-то элемент был действительно удалён. Удаляем мы только последнюю ячейку в цепи, и если бы на её месте возникла дыра для сторонней цепочки, это бы означало что элемент, стоящий на [math]q[/math] позиций назад, одновременно принадлежал нашей и другой цепочкам, что невозможно.

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

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

Принцип двойного хеширования

При двойном хешировании используются две независимые хеш-функции [math] h_1(k) [/math] и [math] h_2(k) [/math]. Пусть [math] k [/math] — это наш ключ, [math] m [/math] — размер нашей таблицы, [math]n \bmod m [/math] — остаток от деления [math] n [/math] на [math] m [/math], тогда сначала исследуется ячейка с адресом [math] h_1(k) [/math], если она уже занята, то рассматривается [math] (h_1(k) + h_2(k)) \bmod m [/math], затем [math] (h_1(k) + 2 \cdot h_2(k)) \bmod m [/math] и так далее. В общем случае идёт проверка последовательности ячеек [math] (h_1(k) + i \cdot h_2(k)) \bmod m [/math] где [math] i = (0, 1, \; ... \;, m - 1) [/math]

Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за [math]O(1)[/math], в худшем — за [math]O(m)[/math], что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

[math]\forall x \neq y \; \exists h_1,h_2 : p(h_1(x)=h_1(y))\gt p((h_1(x)=h_1(y)) \land (h_2(x)=h_2(y)))[/math]

Выбор хеш-функций

[math] h_1 [/math] может быть обычной хеш-функцией. Однако чтобы последовательность исследования могла охватить всю таблицу, [math] h_2 [/math] должна возвращать значения:

  • не равные [math] 0 [/math]
  • независимые от [math] h_1 [/math]
  • взаимно простые с величиной хеш-таблицы

Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а [math] h_2 [/math] возвращает натуральные числа, меньшие [math] m [/math]. Второй — размер таблицы является степенью двойки, а [math] h_2 [/math] возвращает нечетные значения.

Например, если размер таблицы равен [math] m [/math], то в качестве [math] h_2 [/math] можно использовать функцию вида [math] h_2(k) = k \bmod (m-1) + 1 [/math]

Вставка при двойном хешировании

Пример

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

[math] h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod 13 [/math]

[math] h_1(k) = k \bmod 13 [/math]

[math] h_2(k) = 1 + k \bmod 11 [/math]

Мы хотим вставить ключ 14. Изначально [math] i = 0 [/math]. Тогда [math] h(14,0) = (h_1(14) + 0\cdot h_2(14)) \bmod 13 = 1 [/math]. Но ячейка с индексом 1 занята, поэтому увеличиваем [math] i [/math] на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При [math] i = 2 [/math] получаем [math] h(14,2) = (h_1(14) + 2\cdot h_2(14)) \bmod 13 = 9 [/math]. Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных [math] k [/math] пара [math] (h_1(k),h_2(k)) [/math] дает различные последовательности ячеек для исследования.

Простая реализация

Пусть у нас есть некоторый объект [math] item [/math], в котором определено поле [math] key [/math], от которого можно вычислить хеш-функции [math] h_1(key)[/math] и [math] h_2(key) [/math]

Так же у нас есть таблица [math] table [/math] величиной [math] m [/math], состоящая из объектов типа [math] item [/math].

Вставка

function add(Item item):
     x = h1(item.key)
     y = h2(item.key)
     for (i = 0..m)    	
        if table[x] == null
           table[x] = item
           return      
        x = (x + y) mod m   
     table.resize()// ошибка, требуется увеличить размер таблицы

Поиск

Item search(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m)
        if table[x] != null
           if table[x].key == key
              return table[x]
        else
           return null
        x = (x + y) mod m   
     return null

Реализация с удалением

Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив [math]deleted[/math] типов [math]bool[/math], равный по величине массиву [math]table[/math]. Теперь при удалении мы просто будем помечать наш объект как удалённый, а при добавлении как не удалённый и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.

Вставка

function add(Item item):
     x = h1(item.key)
     y = h2(item.key)
     for (i = 0..m)   	
        if table[x] == null or deleted[x]
           table[x] = item
           deleted[x] = false
           return      
        x = (x + y) mod m   
     table.resize()// ошибка, требуется увеличить размер таблицы

Поиск

Item search(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m) 
        if table[x] != null
           if table[x].key == key and !deleted[x]
              return table[x]
        else
           return null
        x = (x + y) mod m   
     return null

Удаление

function remove(Item key):
     x = h1(key)
     y = h2(key)
     for (i = 0..m)
        if table[x] != null
           if table[x].key == key
              deleted[x] = true
        else 
           return
        x = (x + y) mod m

Альтернативная реализация метода цепочек

В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию сбалансированного дерева. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан линейный порядок. То есть при использовании данныx типа [math]\mathbf{int}[/math] или [math]\mathbf{double}[/math] имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с [math]O(n)[/math] до [math]O(\log(n))[/math]. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.

Хеширование в Java 8.

См. также

Источники информации