Может ли два ключа, имеющие другой hashCode, быть частью одного и того же ведра в HashMap в Java?

Question

У меня есть HashMap. В нем 16 ведер (по умолчанию). Возможно ли, что два ключа, имеющие разные хэш-коды, являются частью одного и того же ведра? Или всегда создается новое ведро для другого hashCode, и таким образом HashMap расширяет размер ведра?

Прочитайте много сообщений, но только смутил себя.

Answer 1

Да, это возможно. Поскольку количество ведер намного меньше числа возможных hashCodes (количество ковшей пропорционально количеству записей в HashMap, а число возможных hashCodes - это число возможных значений int, что намного больше), окончательное сопоставление hashCode с ведром выполняется с помощью некоторого оператора модуля, поэтому несколько hashCodes могут быть сопоставлены с одним и тем же ведром (если, например, у вас есть 16 ведер, то оба значения hashCodes 1 и 17 будут сопоставлены с одним и тем же ведром (обратите внимание, что на hashCode я не имею в виду значение, возвращаемое методом hashCode, так как HashMap применяет дополнительную функцию на этом hashCode, чтобы улучшить распределение хэш-кодов)).

Именно поэтому hashCode недостаточно, чтобы определить, присутствует ли ключ, который мы ищем, на карте - мы также должны использовать equals.

Answer 2

Взятые из How HashMap works in Java:

Поскольку внутренний массив HashMap имеет фиксированный размер, и если вы продолжаете хранить объекты, в какой-то момент времени хэш-функции будет возвращать то же место ведро для двух различных ключей, это называется столкновением в HashMap. В этом случае связанный список формируется в этом месте ковша, и новая запись сохраняется как следующий узел.

И тогда, когда там, если мы хотим get что объект из списка мы должны equals():

Если попытаться извлечь объект из этого связанного списка, нам нужна дополнительная проверка для поиска правильной value, это делается методом equals(). Поскольку каждый узел содержит запись, HashMap продолжает сравнивать ключевой объект элемента с переданным ключом с помощью equals(), и когда он возвращает true, Map возвращает соответствующее значение.

Answer 3

hashcode() возвращает interger в java, поэтому вам нужно отобразить целочисленный диапазон в размер ведра. Если вы переводите из более крупного набора в меньший набор, чтобы у вас всегда были столкновения. Если вы посмотрите исходный код HashMap, вы найдете следующий метод для сопоставления int с длиной ведра.

static int indexFor(int h, int length) { 
      return h & (length-1); 
} 

хэш-код предобработан для получения равномерного распределения с помощью:

static int hash(int h) { 
     // This function ensures that hashCodes that differ only by 
     // constant multiples at each bit position have a bounded 
     // number of collisions (approximately 8 at default load factor). 
     h ^= (h >>> 20)^(h >>> 12); 
     return h^(h >>> 7)^(h >>> 4); 
    } 

Применяется дополнительный хэш-функции для данного хэш-код, который защищает от плохих функций качества хэш. Это важно, потому что HashMap использует хэш-таблицы с длиной в две строки, которые в противном случае сталкиваются с конфликтами для хэш-кодов, которые не отличаются в младших битах. Примечание. Нулевые ключи всегда отображают хэш 0, таким образом, индекс 0.

HashMap source