как hashtables справляется с коллизиями?

<p>я слышал в своих классах степени, что <code>hashtable</code> поместит новую запись в "следующую доступную" корзину, если новая запись key столкнется с другой.</p><p>как <code>hashtable</code> будет по-прежнему возвращать правильное значение, если это столкновение происходит при обращении к нему с ключом столкновения?</p><p>я предполагаю, что <code>keys</code> имеют тип <code>string</code> и <code>hashcode()</code> возвращает значение по умолчанию, сгенерированное, скажем, java.</p><p>если я реализую свою собственную функцию хеширования и использую ее как часть справочной таблицы (т. е. <code>hashmap</code> или <code>dictionary</code>), какие существуют стратегии для борьбы с коллизиями?</p><p>я даже видел заметки, касающиеся простых чисел! информация не очень понятна из поиска google.</p>

<p>хеш-таблицы обрабатывают коллизии одним из двух способов.</p><p><strong>вариант 1:</strong> наличие в каждом сегменте связанного списка элементов, которые хэшируются в этом сегменте. вот почему плохая хеш-функция может сделать поиск в хеш-таблицах очень медленным.</p><p><strong>вариант 2:</strong> если все записи хеш-таблицы заполнены, то хеш-таблица может увеличить количество имеющихся в ней сегментов, а затем перераспределить все элементы в таблице. хеш-функция возвращает целое число, и хеш-таблица должна взять результат хеш-функции и изменить его по размеру таблицы таким образом, чтобы можно было быть уверенным, что он попадет в корзину. таким образом, увеличив размер, он будет перефразировать и запускать вычисления по модулю, которые, если вам повезет, могут отправлять объекты в разные корзины.</p><p>java использует оба варианта 1 и 2 в своих реализациях хеш-таблицы.</p>

<p>когда вы говорили о том, что "хэш-таблица поместит новую запись в" следующее доступное "поле, если новая запись ключа столкнется с другой.", вы говорите о <strong> стратегии открытой адресации </strong> разрешение коллизий хеш-таблицы.</p><hr><p>есть несколько стратегий для хеш-таблицы для разрешения коллизий.</p><p>первый тип большого метода требует, чтобы ключи (или указатели на них) были сохранены в таблице вместе со связанными значениями, что дополнительно включает в себя:</p><ul> <li><strong> отдельная цепочка </strong></li> </ul><p><img src="https://i.stack.imgur.com/jgx80.png" alt="enter image description here"></p><ul> <li><strong> открытая адресация </strong></li> </ul><p><img src="https://i.stack.imgur.com/dihhf.png" alt="enter image description here"></p><ul> <li><strong> объединенное хеширование </strong></li> <li><strong> хеширование кукушки </strong></li> <li><strong> хэширование робин гуда </strong></li> <li><strong> хэширование с 2 вариантами </strong></li> <li><strong> хеширование hopscotch </strong></li> </ul><hr><p>другим важным методом обработки столкновений является <strong> динамическое изменение размера </strong>, которое дополнительно имеет несколько способов:</p><ul> <li><strong> изменение размера путем копирования всех записей </strong></li> <li><strong> инкрементное изменение размера </strong></li> <li><strong> монотонные клавиши </strong></li> </ul><hr><p><strong>edit</strong>: вышеперечисленные заимствованы из <a href="http://en.wikipedia.org/wiki/hash\_table#collision\_resolution">wiki\_hash\_table</a> , куда вы должны обратиться, чтобы получить больше информации.</p>

<p>есть несколько методов, доступных для обработки столкновений. я объясню некоторые из них</p><p><strong> цепочка: </strong> в цепочке мы используем индексы массива для хранения значений. если хэш-код второго значения также указывает на тот же индекс, мы заменяем это значение индекса на связанный список, и все значения, указывающие на этот индекс, сохраняются в связанном списке, а фактический индекс массива указывает на заголовок связанного списка. но если существует только один хэш-код, указывающий на индекс массива, то значение непосредственно сохраняется в этом индексе. та же логика применяется при получении значений. это используется в java hashmap/hashtable, чтобы избежать коллизий.</p><p><strong> линейное зондирование: </strong> этот метод используется, когда у нас в таблице больше индекса, чем значений, которые нужно сохранить. техника линейного зондирования работает по принципу непрерывного увеличения, пока вы не найдете пустой слот. псевдокод выглядит так:</p><pre><code>index = h(k) while( val(index) is occupied) index = (index+1) mod n </code></pre><p><strong> техника двойного хеширования: </strong> в этом методе мы используем две функции хеширования h1 (k) и h2 (k). если слот в h1 (k) занят, то вторая функция хеширования h2 (k) используется для увеличения индекса. псевдокод выглядит так:</p><pre><code>index = h1(k) while( val(index) is occupied) index = (index + h2(k)) mod n </code></pre><p>методы линейного зондирования и двойного хеширования являются частью техники открытой адресации, и ее можно использовать только в том случае, если количество доступных слотов превышает количество добавляемых элементов. это занимает меньше памяти, чем цепочка, потому что здесь не используется дополнительная структура, но она медленная из-за большого количества движения, пока мы не найдем пустой слот. также в технике открытой адресации, когда элемент извлекается из слота, мы помещаем надгробную плиту, чтобы указать, что элемент удален отсюда, поэтому он пуст.</p><p>для получения дополнительной информации см. <a href="http://coder2design.com/hashing/">этот сайт</a> .</p>

<p>я настоятельно рекомендую вам прочитать этот пост в блоге, который недавно появился на hackernews: <a href="http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html">как работает hashmap в java</a> </p><p>короче говоря, ответ</p><blockquote> <p>что произойдет, если два разных объекта ключа hashmap имеют одинаковый хэш-код?</p> <p>они будут храниться в том же сегменте, но не в следующем узле связанного списка. и метод keys equals () будет использоваться для определения правильной пары ключ-значение в hashmap.</p> </blockquote>

<blockquote> <p>я слышал в своих классах степени, что hashtable поместит новую запись в "следующую доступную" корзину, если новая запись key столкнется с другой.</p> </blockquote><p>на самом деле это не так, по крайней мере для oracle jdk (это <em> </em> деталь реализации, которая может варьироваться в зависимости от реализации api. вместо этого каждый блок содержит связанный список записей до java 8 и сбалансированное дерево в java 8 или выше.</p><blockquote> <p>тогда как hashtable будет по-прежнему возвращать правильное значение, если это столкновение происходит при вызове одного с ключом столкновения?</p> </blockquote><p>он использует <code>equals()</code>, чтобы найти фактически совпадающую запись.</p><blockquote> <p>если я реализую свою собственную функцию хеширования и использую ее как часть справочной таблицы (например, hashmap или dictionary), какие существуют стратегии для борьбы со столкновениями?</p> </blockquote><p>существуют различные стратегии обработки столкновений с различными преимуществами и недостатками. <a href="http://en.wikipedia.org/wiki/hash\_table#collision\_resolution">запись википедии о хеш-таблицах</a> дает хороший обзор.</p>

<p><strong> обновление с java 8: </strong> java 8 использует самоуравновешенное дерево для обработки столкновений, улучшая наихудший случай от o(n) до o (log n) для поиска. использование самоуравновешенного дерева было введено в java 8 как улучшение по сравнению с цепочкой (использовалось до java 7), которое использует связанный список и имеет наихудший случай o(n) для поиска (так как нужно пройти по списку)</p><p>чтобы ответить на вторую часть вашего вопроса, вставка выполняется путем сопоставления данного элемента с данным индексом в базовом массиве hashmap, однако, когда происходит коллизия, все элементы все равно должны быть сохранены (сохранены во вторичной структуре данных , а не просто заменить в базовом массиве). обычно это делается путем превращения каждого компонента массива (слота) во вторичную структуру данных (иначе говоря, в корзину), и элемент добавляется в корзину, находящуюся в данном индексе массива (если ключ еще не существует в корзине, в в каком случае он заменен).</p><p>во время поиска ключ хэшируется в соответствующий ему индекс массива, и выполняется поиск элемента, соответствующего (точному) ключу в данном сегменте. поскольку корзина не нуждается в обработке коллизий (сравнивает ключи напрямую), это решает проблему коллизий, но делает это за счет необходимости выполнения вставки и поиска во вторичной структуре данных. ключевым моментом является то, что в хэш-карте хранятся и ключ, и значение, и поэтому даже если хеш-код сталкивается, ключи сравниваются непосредственно на равенство (в сегменте) и, таким образом, могут быть однозначно идентифицированы в сегменте.</p><p>обработка коллизий приносит худшую производительность вставки и поиска от o(1) в случае отсутствия коллизий до o(n) для создания цепочки (связанный список используется как вторичная структура данных) и o (log n) для самоуравновешенного дерева.</p><p>рекомендации:</p><blockquote> <p>java 8 имеет следующие улучшения/изменения объектов hashmap в случае высоких коллизий.</p> <ul> <li> <p>альтернативная хеш-функция string, добавленная в java 7, была удалена.</p> </li> <li> <p>корзины, содержащие большое количество сталкивающихся ключей, будут сохранять свои записи в сбалансированном дереве вместо связанного списка после достижения определенного порога.</p> </li> </ul> <p>вышеуказанные изменения обеспечивают производительность o(log(n)) в худших случаях ( <a href="https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8">https://www.nagarro.com/en/blog/post/24/performance-improvement-for). -hashmap-в-java-8</a> )</p> </blockquote>

<p>поскольку существует некоторая путаница в отношении того, какой алгоритм использует hashmap java (в реализации sun/oracle/openjdk), здесь приведены соответствующие фрагменты исходного кода (из openjdk, 1.6.0\_20, в ubuntu):</p><pre><code>/** * returns the entry associated with the specified key in the * hashmap. returns null if the hashmap contains no mapping * for the key. */ final entry<k,v> getentry(object key) { int hash = (key == null) ? 0 : hash(key.hashcode()); for (entry<k,v> e = table[indexfor(hash, table.length)]; e != null; e = e.next) { object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } </code></pre><p>этот метод (например, строки 355–371) вызывается при поиске записи в таблице, например, из <code>get()</code>, <code>containskey()</code> и некоторых других. цикл for здесь проходит через связанный список, сформированный объектами entry.</p><p>вот код для ввода объектов (строки 691-705 + 759):</p><pre><code>static class entry<k,v> implements map.entry<k,v> { final k key; v value; entry<k,v> next; final int hash; /** * creates new entry. */ entry(int h, k k, v v, entry<k,v> n) { value = v; next = n; key = k; hash = h; } // (methods left away, they are straight-forward implementations of map.entry) } </code></pre><p>сразу после этого следует метод <code>addentry()</code>:</p><pre><code>/** * adds a new entry with the specified key, value and hash code to * the specified bucket. it is the responsibility of this * method to resize the table if appropriate. * * subclass overrides this to alter the behavior of put method. */ void addentry(int hash, k key, v value, int bucketindex) { entry<k,v> e = table[bucketindex]; table[bucketindex] = new entry<k,v>(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); } </code></pre><p>это добавляет новую запись в начале корзины со ссылкой на старую запись <em>первая</em> (или ноль, если такой нет). точно так же метод <code>removeentryforkey()</code> просматривает список и заботится об удалении только одной записи, оставляя остальную часть списка без изменений.</p><p>итак, вот список связанных записей для каждого сегмента, и я очень сомневаюсь, что он изменился с <code>\_20</code> на <code>\_22</code>, так как он был похож на 1.2.</p><p>(этот код (c) 1997-2007 sun microsystems и доступен под лицензией gpl, но для копирования лучше использовать исходный файл, содержащийся в src.zip в каждом jdk от sun/oracle, а также в openjdk.)</p>

<p>он будет использовать метод equals, чтобы увидеть, присутствует ли ключ даже, особенно если в одном сегменте содержится более одного элемента.</p>

<p>существуют различные методы разрешения коллизий. некоторые из них - это отдельная цепочка, открытая адресация, хэширование робин гуда, хеширование кукушки и т.д.</p><p>в java для разделения коллизий в хэш-таблицах используется отдельная цепочка. вот отличная ссылка на то, как это происходит: <a href="http://javapapers.com/core-java/java-hashtable/">http://javapapers.com/core-java/java-hashtable/</a> </p>

<p>вот очень простая реализация хеш-таблицы в java. только реализует <code>put()</code> и <code>get()</code>, но вы можете легко добавить все, что захотите. он основан на методе java <code>hashcode()</code>, который реализован всеми объектами. вы можете легко создать свой собственный интерфейс,</p><pre><code>interface hashable { int gethash(); } </code></pre><p>и заставить его быть реализованным клавишами, если хотите.</p><pre><code>public class hashtable<k, v> { private static class entry<k,v> { private final k key; private final v val; entry(k key, v val) { this.key = key; this.val = val; } } private static int bucket\_count = 13; @suppresswarnings("unchecked") private list<entry>[] buckets = new list[bucket\_count]; public hashtable() { for (int i = 0, l = buckets.length; i < l; i++) { buckets[i] = new arraylist<entry<k,v>>(); } } public v get(k key) { int b = key.hashcode() % bucket\_count; list<entry> entries = buckets[b]; for (entry e: entries) { if (e.key.equals(key)) { return e.val; } } return null; } public void put(k key, v val) { int b = key.hashcode() % bucket\_count; list<entry> entries = buckets[b]; entries.add(new entry<k,v>(key, val)); } } </code></pre>