Редактирование: Разрешение коллизий

Перейти к: навигация, поиск

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.  
+
'''Разрешение коллизий'''(англ. collision resolution) в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию.
 +
 
 +
При использовании списков особых проблем не возникает, так как там в каждой ячейке хранится список всех элементов. При добавлении необходимо просто добавить элемент в начало списка.
 +
 
 +
При открытой адресации будет иначе: в каждой ячейке хеш-таблицы хранится только один элемент. Тогда при добавлении, если ячейка свободна, мы просто записываем добавляемый элемент в эту ячейку. Однако если эта ячейка занята {{---}} необходимо поместить добавляемый элемент в какую-нибудь другую свободную ячейку. Такие ситуации нередки, так как невозможно использовать хеш-функцию, не дающую коллизий, а каждой ячейке таблицы соответствует одно значение хеш-функции. Далее мы рассмотрим несколько стратегий поиска свободного места в данном случае.
  
 
== Разрешение коллизий с помощью цепочек ==
 
== Разрешение коллизий с помощью цепочек ==
 
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
 
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало [[Список|списка]] всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
+
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
  
В зависимости от того нужна ли нам уникальность значений операции вставки у нас будет работать за разное время. Если не важна, то мы используем список, время вставки в который будет в худшем случае равна <tex>O(1)</tex>. Иначе мы проверяем есть ли в списке данный элемент, а потом в случае его отсутствия мы его добавляем. В таком случае вставка элемента в худшем случае будет выполнена за <tex>O(n)</tex>
+
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.
  
 
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
 
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
Строка 13: Строка 17:
 
== Линейное разрешение коллизий ==
 
== Линейное разрешение коллизий ==
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
+
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
  
 
=== Стратегии поиска ===
 
=== Стратегии поиска ===
Строка 47: Строка 51:
  
 
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
 
Кластеризация замедляет все операции с хеш-таблицей: при добавлении требуется перебирать всё больше элементов, при проверке тоже. Чем больше в таблице элементов, тем больше в ней кластеры и тем выше вероятность того, что добавляемый элемент попадёт в кластер.
Для защиты от кластеризации используется двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
+
Для защиты от кластеризации используется Двойное хеширование и [[Хеширование кукушки|хеширование кукушки]].
 +
 
  
 
=== Удаление элемента без пометок ===
 
=== Удаление элемента без пометок ===
Строка 60: Строка 65:
 
''' Псевдокод '''
 
''' Псевдокод '''
  
'''function''' delete('''Item''' i):
+
  '''function''' delete('''Item''' i)  
 
       j = i + q
 
       j = i + q
       '''while''' table[j] == ''null'' '''or''' table[j].key != table[i].key
+
       '''while''' table[j] == null || table[j].key != table[i].key
         '''if''' table[j] == ''null''
+
         '''if''' (table[j] == null)
             table[i] = ''null''
+
             table[i] = null
 
             '''return'''
 
             '''return'''
 
         j += q
 
         j += q
 
       table[i] = table[j]
 
       table[i] = table[j]
       delete(j)  
+
       delete(j);     
  
 
Хеш-таблицу считаем зацикленной
 
Хеш-таблицу считаем зацикленной
Строка 77: Строка 82:
 
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
 
|statement=Асимптотически время работы <tex>\mathrm{delete}</tex> и <tex>\mathrm{find}</tex> совпадают
 
|proof=
 
|proof=
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего {{---}} с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
+
Заметим что указатель <tex>j</tex> в каждой итерации перемещается вперёд на <tex>q</tex> (с учётом рекурсивных вызовов <tex>\mathrm{delete}</tex>). То есть этот алгоритм последовательно пройдёт по цепочке от удаляемого элемента до последнего - с учётом вызова <tex>\mathrm{find}</tex> собственно для нахождения удаляемого элемента, мы посетим все ячейки цепи.
 
}}
 
}}
  
Строка 137: Строка 142:
  
 
===Простая реализация===
 
===Простая реализация===
Пусть у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </tex>
+
Пусть у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> \mathrm{h_1(key)}</tex> и <tex> \mathrm{h_2(key)} </tex>
  
 
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.
 
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex>, состоящая из объектов типа <tex> item </tex>.
  
 
'''Вставка'''
 
'''Вставка'''
'''function''' add('''Item''' item):
+
  '''function''' add('''Item''' item)
 
       x = h1(item.key)
 
       x = h1(item.key)
 
       y = h2(item.key)
 
       y = h2(item.key)
         '''for''' (i = 0..m)   
+
         '''for''' (i = 0; i < m; i++)   
             '''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()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
+
       table.resize() //ошибка, требуется увеличить размер таблицы
  
 
'''Поиск'''
 
'''Поиск'''
'''Item''' search('''Item''' key):
+
  '''Item''' search('''Item''' key)
 
       x = h1(key)
 
       x = h1(key)
 
       y = h2(key)
 
       y = h2(key)
       '''for''' (i = 0..m)
+
       '''for''' (i = 0; i < m; i++)
         '''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''
+
       '''return''' null
  
 
===Реализация с удалением===
 
===Реализация с удалением===
Чтобы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
+
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
  
 
'''Вставка'''
 
'''Вставка'''
'''function''' add('''Item''' item):
+
  '''function''' add('''Item''' item)
 
       x = h1(item.key)
 
       x = h1(item.key)
 
       y = h2(item.key)
 
       y = h2(item.key)
       '''for''' (i = 0..m) 
+
       '''for''' (i = 0; i < m; i++
         '''if''' table[x] == '''null''' '''or''' deleted[x]
+
         '''if''' table[x] == null || deleted[x]
 
             table[x] = item
 
             table[x] = item
             deleted[x] = '''false'''
+
             deleted[x] = false
 
             '''return'''       
 
             '''return'''       
         x = (x + i * y) '''mod''' m   
+
         x = (x + y) mod m   
       table.resize()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
+
       table.resize() //ошибка, требуется увеличить размер таблицы
 
'''Поиск'''
 
'''Поиск'''
'''Item''' search('''Item''' key):
+
  '''Item''' search('''Item''' key)
 
       x = h1(key)
 
       x = h1(key)
 
       y = h2(key)
 
       y = h2(key)
       '''for''' (i = 0..m)  
+
       '''for''' (i = 0; i < m; i++)  
         '''if''' table[x] != '''null'''
+
         '''if''' table[x] != null
             '''if''' table[x].key == key '''and''' !deleted[x]
+
             '''if''' table[x].key == key && !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'''
+
       '''return''' null
  
 
'''Удаление'''
 
'''Удаление'''
'''function''' remove('''Item''' key):
+
  '''function''' remove('''Item''' key)
 
       x = h1(key)
 
       x = h1(key)
 
       y = h2(key)
 
       y = h2(key)
       '''for''' (i = 0..m)
+
       '''for''' (i = 0; i < m; i++)
         '''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
+
       x = (x + y) mod m
  
==Альтернативная реализация метода цепочек==
+
== Разрешение коллизий в Java 8==
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данная корзина переходит от использования связного списка к использованию [[АВЛ-дерево|сбалансированного дерева]]. Но данный метод имеет смысл лишь тогда, когда на элементах хеш-таблицы задан [[Отношение порядка|линейный порядок]]. То есть при использовании данный типа <tex>\mathbf{int}</tex> или <tex>\mathbf{double}</tex> имеет смысл переходить к дереву поиска, а при использовании каких-нибудь ссылок на объекты не имеет, так как они не реализуют нужный интерфейс. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(\log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
+
[[Файл:Hashing_in_Java8.png|thumb|400px|right|Хеширование в Java 8.]]
 +
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в бакете превышает определенное значение, данный бакет переходит от использования связного списка к использованию сбалансированного дерева. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(log(n))</tex> Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
  
[[Файл:Hashing_in_Java8.png|500px|Хеширование в Java 8.]]
 
  
 
==См. также==
 
==См. также==
 
* [[Хеширование]]
 
* [[Хеширование]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
 
* [[Хеширование_кукушки|Хеширование кукушки]]
* [[Идеальное_хеширование|Идеальное хеширование]]
 
  
== Источники информации ==
+
== Литература ==
 
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
 
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в Delphi», 2003
 
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд «Алгоритмы: построение и анализ», 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010.— Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г.{{---}} ISBN 0-201-89685-0
 
* Дональд Кнут. «Искусство программирования, том 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 Разрешение коллизий]
Строка 227: Строка 232:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]
[[Категория: Структуры данных]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: