Когда в Хашмапе произошло столкновение? [Дубликат]

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

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

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

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

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

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

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

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

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

Он мог бы сформировать связанный список. Просто контракт 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

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

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

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

Рассмотрим источник 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's 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

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

Map<Foo, List<Bar>> myMap;

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