Разрешение конфликтов в Java HashMap

Ответ 1

Когда вы вставляете пару (10, 17), а затем (10, 20), технически никакого столкновения не происходит. Вы просто заменяете старое значение новым значением или заданным ключом 10 (так как в обоих случаях 10 равно 10, а хэш-код для 10 всегда равен 10).

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

В качестве примера предположим, что две строки "abra ka dabra" и "wave my wand" дают хеш-коды 100 и 200 соответственно. Предполагая, что общий размер массива равен 10, оба они попадают в одно и то же ведро (100 % 10 и 200 % 10). Chaining гарантирует, что всякий раз, когда вы выполняете map.get( "abra ka dabra" );, вы получаете правильное значение, связанное с ключом. В случае хэш-карты в Java это делается с помощью метода equals.

Ответ 2

В HashMap ключ - это объект, содержащий методы hashCode() и equals(Object).

Когда вы вставляете новую запись на карту, она проверяет, известна ли hashCode. Затем он перебирает все объекты с помощью этого хэш-кода и проверяет их равенство с .equals(). Если найден одинаковый объект, новое значение заменит старый. Если нет, он создаст новую запись на карте.

Обычно, говоря о картах, вы используете collision, когда два объекта имеют один и тот же hashCode, но они разные. Они внутренне хранятся в списке.

Ответ 3

Возможно, он сформировал связанный список. Просто для этого контракта Map требуется, чтобы он заменил запись:

V put(K key, V value)

Связывает указанное значение с указанным ключом на этой карте (дополнительная операция). Если на карте ранее содержалось отображение для ключ, старое значение заменяется указанным значением. (Отображение m является сказал, что содержит отображение для ключа k тогда и только тогда, когда m.containsKey(k) вернет true.)

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

Для карты для хранения списков значений это должно быть Multimap. Здесь Google: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Коллекция, подобная карте, но которая может связывать несколько значений с одним ключом. Если вы дважды вызываете put (K, V) с тем же ключом, но разные значения, multimap содержит сопоставления от ключа к обоим значения.

Изменить: разрешение столкновений

Это немного другое. Столкновение происходит, когда два разных ключа имеют один и тот же хеш-код, или два ключа с разными хэш-кодами происходят в один и тот же ковш в базовом массиве.

Рассмотрим источник HashMap (удалены биты и куски):

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // i is the index where we want to insert the new element
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // take the entry that already in that bucket
    Entry<K,V> e = table[bucketIndex];
    // and create a new one that points to the old one = linked list
    table[bucketIndex] = new Entry<>(hash, key, value, e);
}

Для тех, кому интересно, как класс Entry в HashMap начинает вести себя как список, оказывается, что HashMap определяет свой собственный статический класс Entry, который реализует Map.Entry. Вы можете убедиться сами, просмотрев исходный код:

GrepCode для HashMap

Ответ 4

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

Ответ 5

Это не определено. Чтобы достичь этой функциональности, вам необходимо создать карту, которая отображает ключи в списки значений:

Map<Foo, List<Bar>> myMap;

Или вы можете использовать Multimap из коллекций google collections/guava

Ответ 6

Прежде всего, у вас есть понятие хэширования немного неправильно, и он был исправлен г-ном Санджаем.

И да, Java действительно реализует технику разрешения конфликтов. Когда два ключа получают хэшированные до одного и того же значения (поскольку используемый внутренний массив конечен по размеру, и в какой-то момент метод hashcode() возвращает одно и то же значение хэша для двух разных ключей) в это время связанный список формируется в ведре где вся информация вводится как объект Map.Entry, содержащий пару ключ-значение. Доступ к объекту с помощью ключа в худшем случае требует O (n), если запись присутствует в таких списках. Сравнение ключа, переданного с каждым ключом в таком списке, будет выполняться методом equals().

Хотя из Java 8 связанные списки заменяются деревьями (O (log n))

Ответ 7

Существует различие между столкновением и дублированием. Столкновение означает, что hashcode и bucket одинаковы, но в двух экземплярах он будет таким же хэш-кодом, таким же ведром, но здесь метод equals попадает в изображение.

Обнаружено столкновение, и вы можете добавить элемент в существующий ключ. но в случае дублирования он заменит новое значение.