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

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами: метод цепочек, открытая адресация и т.д. Очень важно сводить количество коллизий к минимуму, так как это увеличивает время работы с хеш-таблицами.  
+
'''Разрешение [[Хеш-таблица|коллизий]]''' (англ. collision resolution) в [[Хеш-таблица|хеш-таблице]], задача, решаемая несколькими способами. Например, при помощи метода цепочке или открытой адресации. Коллизии замедляют время работы с хеш-таблицой, поэтому с ними нужно бороться.
  
 
== Разрешение коллизий с помощью цепочек ==
 
== Разрешение коллизий с помощью цепочек ==
Строка 5: Строка 5:
 
Каждая ячейка <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: Строка 13:
 
== Линейное разрешение коллизий ==
 
== Линейное разрешение коллизий ==
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличие от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно, будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
+
Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
  
 
=== Стратегии поиска ===
 
=== Стратегии поиска ===
Строка 60: Строка 60:
 
''' Псевдокод '''
 
''' Псевдокод '''
  
  '''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''' '''or''' 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);    
  
 
Хеш-таблицу считаем зацикленной
 
Хеш-таблицу считаем зацикленной
Строка 142: Строка 142:
  
 
'''Вставка'''
 
'''Вставка'''
  '''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..m)   
             '''if''' table[x] == ''null''
+
             '''if''' table[x] == '''null'''
 
               table[x] = item
 
               table[x] = item
 
             '''return'''       
 
             '''return'''       
Строка 153: Строка 153:
  
 
'''Поиск'''
 
'''Поиск'''
  '''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..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''
+
       '''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)
Строка 177: Строка 177:
 
             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()<span style="color:Green">// ошибка, требуется увеличить размер таблицы
 
'''Поиск'''
 
'''Поиск'''
  '''Item''' search('''Item''' key):
+
  '''Item''' search('''Item''' key)
 
       x = h1(key)
 
       x = h1(key)
 
       y = h2(key)
 
       y = h2(key)
Строка 193: Строка 193:
  
 
'''Удаление'''
 
'''Удаление'''
  '''function''' remove('''Item''' key):
+
  '''function''' remove('''Item''' key)
 
       x = h1(key)
 
       x = h1(key)
 
       y = h2(key)
 
       y = h2(key)
Строка 204: Строка 204:
 
       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.
+
В Java 8 для разрешения коллизий используется модифицированный метод цепочек. Суть его заключается в том, что когда количество элементов в корзине превышает определенное значение, данный бакет переходит от использования связного списка к использованию сбалансированного дерева. Такой подход позволяет улучшить производительность с <tex>O(n)</tex> до <tex>O(log(n))</tex>. Данный способ используется в таких коллекциях как HashMap, LinkedHashMap и ConcurrentHashMap.
 
+
[[Файл:Hashing_in_Java8.png|400px|Хеширование в Java 8.]]
[[Файл:Hashing_in_Java8.png|500px|Хеширование в Java 8.]]
 
  
 
==См. также==
 
==См. также==
Строка 214: Строка 213:
 
* [[Идеальное_хеширование|Идеальное хеширование]]
 
* [[Идеальное_хеширование|Идеальное хеширование]]
  
== Источники информации ==
+
== Литература ==
 
* Бакнелл Дж. М. «Фундаментальные алгоритмы и структуры данных в 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://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]
Строка 227: Строка 228:
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]
[[Категория: Структуры данных]]
 

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

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

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

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