Я слышал на своих курсах, что a HashTable
поместит новую запись в «следующую доступную» корзину, если новая запись Key сталкивается с другой.
Как все HashTable
же вернуть правильное значение, если это столкновение произойдет при вызове одного обратно с помощью ключа столкновения?
Я предполагаю , что Keys
являются String
тип и hashCode()
возвращает значение по умолчанию генерируется скажем Java.
Если я реализую свою собственную функцию хеширования и использую ее как часть таблицы поиска (например, HashMap
или Dictionary
), какие существуют стратегии для борьбы с коллизиями?
Я даже видел заметки, относящиеся к простым числам! Информация не так понятна из поиска Google.
Когда вы говорили о том, что «Hash Table поместит новую запись в« следующую доступную »корзину, если новая запись Key сталкивается с другой.», Вы говорите о стратегии открытой адресации разрешения конфликтов хеш-таблицы.
Для хеш-таблицы существует несколько стратегий разрешения конфликтов.
Первый тип большого метода требует, чтобы ключи (или указатели на них) хранились в таблице вместе со связанными значениями, что дополнительно включает:
Другой важный метод обработки столкновений - это динамическое изменение размера , которое также имеет несколько способов:
РЕДАКТИРОВАТЬ : приведенное выше заимствовано из wiki_hash_table , куда вы должны пойти, чтобы получить дополнительную информацию.
источник
Существует несколько методов обработки столкновений. Я объясню некоторые из них
Цепочка: в цепочке мы используем индексы массивов для хранения значений. Если хеш-код второго значения также указывает на тот же индекс, мы заменяем это значение индекса связанным списком, и все значения, указывающие на этот индекс, сохраняются в связанном списке, а фактический индекс массива указывает на заголовок связанного списка. Но если есть только один хэш-код, указывающий на индекс массива, тогда значение сохраняется непосредственно в этом индексе. Та же логика применяется при извлечении значений. Это используется в Java HashMap / Hashtable, чтобы избежать коллизий.
Линейное зондирование: этот метод используется, когда у нас больше индекса в таблице, чем значений, которые нужно сохранить. Техника линейного зондирования работает по принципу увеличения, пока вы не найдете пустой слот. Псевдокод выглядит так:
Метод двойного хеширования: в этом методе мы используем две функции хеширования h1 (k) и h2 (k). Если слот в h1 (k) занят, тогда вторая хеш-функция h2 (k) используется для увеличения индекса. Псевдокод выглядит так:
Методы линейного зондирования и двойного хеширования являются частью техники открытой адресации и могут использоваться только в том случае, если количество доступных слотов превышает количество добавляемых элементов. Это требует меньше памяти, чем цепочка, потому что здесь не используется дополнительная структура, но она медленная из-за большого количества перемещений, пока мы не найдем пустой слот. Также в технике открытой адресации, когда элемент удаляется из слота, мы помещаем надгробие, чтобы указать, что элемент удален отсюда, поэтому он пуст.
Для получения дополнительной информации посетите этот сайт .
источник
Я настоятельно рекомендую вам прочитать это сообщение в блоге, которое недавно появилось на HackerNews: Как HashMap работает в Java.
Короче говоря, ответ
источник
Это на самом деле не так, по крайней мере , для Oracle JDK (это является деталью реализации , которая может варьироваться от различных реализаций API). Вместо этого каждая корзина содержит связанный список записей до Java 8 и сбалансированное дерево в Java 8 или выше.
Он использует,
equals()
чтобы найти действительно совпадающую запись.Существуют различные стратегии обработки столкновений с разными преимуществами и недостатками. Статья Википедии о хэш-таблицах дает хороший обзор.
источник
Hashtable
иHashMap
в jdk 1.6.0_22 от Sun / Oracle.public V get(Object key)
(та же версия, что и выше). Если вы найдете точную версию, в которой появляются эти связанные списки, мне было бы интересно узнать.Entry
объектов:localEntry = localEntry.next
e = e.next
нет++index
. +1Обновление с Java 8: Java 8 использует самоуравновешенное дерево для обработки столкновений, улучшая худший случай с O (n) до O (log n) для поиска. Использование самоуравновешенного дерева было введено в Java 8 в качестве улучшения по сравнению с цепочкой (использовавшейся до java 7), которая использует связанный список и имеет наихудший случай O (n) для поиска (так как он должен проходить список)
Чтобы ответить на вторую часть вашего вопроса, вставка выполняется путем сопоставления заданного элемента с заданным индексом в базовом массиве хэш-карты, однако при возникновении коллизии все элементы все равно должны быть сохранены (сохранены во вторичной структуре данных , а не просто заменены в базовом массиве). Обычно это делается, делая каждый компонент массива (слот) вторичной структурой данных (также называемой корзиной), и элемент добавляется в корзину, находящуюся в данном индексе массива (если ключ еще не существует в корзине, в в каком случае он заменяется).
Во время поиска ключ хешируется до соответствующего индекса массива, и выполняется поиск элемента, соответствующего (точному) ключу в заданном сегменте. Поскольку корзине не требуется обрабатывать конфликты (сравнивает ключи напрямую), это решает проблему конфликтов, но делает это за счет необходимости выполнять вставку и поиск во вторичной структуре данных. Ключевым моментом является то, что в хэш-карте хранятся и ключ, и значение, и поэтому, даже если хеш-код сталкивается, ключи сравниваются напрямую на равенство (в сегменте), и, таким образом, могут быть однозначно идентифицированы в сегменте.
Обработка коллизий обеспечивает наихудшую производительность вставки и поиска от O (1) в случае отсутствия обработки коллизий до O (n) для цепочки (связанный список используется как вторичная структура данных) и O (журнал n) для самоуравновешенного дерева.
Ссылки:
источник
Он будет использовать метод equals, чтобы увидеть, присутствует ли ключ, даже, особенно если в одной корзине более одного элемента.
источник
Поскольку существует некоторая путаница в отношении того, какой алгоритм использует Java HashMap (в реализации Sun / Oracle / OpenJDK), вот соответствующие фрагменты исходного кода (из OpenJDK, 1.6.0_20, в Ubuntu):
Этот метод (процитировать от линии 355 до 371) называется при поиске записи в таблице, например , из
get()
,containsKey()
и некоторых других. Цикл for здесь проходит через связанный список, образованный объектами записи.Вот код для входных объектов (строки 691-705 + 759):
Сразу после этого идет
addEntry()
метод:Это добавляет новую запись в начало корзины со ссылкой на старую первую запись (или null, если таковой нет). Точно так же
removeEntryForKey()
метод просматривает список и заботится об удалении только одной записи, оставляя остальную часть списка нетронутой.Итак, вот список связанных записей для каждого сегмента, и я очень сомневаюсь, что он изменился с
_20
на_22
, поскольку так было с 1.2 и далее.(Этот код (c) Sun Microsystems 1997-2007 гг. И доступен под GPL, но для копирования лучше использовать исходный файл, содержащийся в src.zip в каждом JDK от Sun / Oracle, а также в OpenJDK.)
источник
вот очень простая реализация хеш-таблицы на java. только в орудиях
put()
иget()
, но вы легко можете добавить все, что захотите. он полагается наhashCode()
метод Java, который реализуется всеми объектами. вы можете легко создать свой собственный интерфейс,и, если хотите, принудительно реализовать его с помощью клавиш.
источник
Существуют различные методы разрешения коллизий: раздельное связывание, открытая адресация, хеширование Робин Гуда, хеширование с кукушкой и т. Д.
Java использует раздельную цепочку для разрешения коллизий в хэш-таблицах. Вот отличная ссылка на то, как это происходит: http://javapapers.com/core-java/java-hashtable/
источник