Емкость (capacity) и заполненность (load factor) для HashMap

#коллекции #hashcode

Господа,
поймал себя на том, что не понимаю базовых вещей по Hash-коллекциям.

Предположим, переопределили hashCode() таким образом, что он равен для всех экземпляров
класса, который используется в качестве ключа HashMap (или значения HashSet).
Значит ли это, что фактически все заносимые в коллекцию Entry окажутся в одной-единственной
"корзине",
или все же будет создано некоторое количество корзин (по умолчанию, кажется, 16),
в каждой из которых элементы ключи имеют один и тот же код?

Известно также, что при достижении load factor (0.75) происходит динамическое перераспеределение
корзин. Но тогда вновь вопрос - а в чем же здесь роль специфической реализации hashCode(),
если все подстраивается по каким-то внутренним алгоритмам hash-коллекций?
    

Ответы

Ответ 1

Я бы очень рекомендовал книгу Effective Java, автор Joshua Bloch (есть и на русском
языке). Там описано очень много нюансов работы с Java, которые могут сильно повлиять
на ваш код.

По первому вопросу:
Вы правы, вот выдержка из выше приведенной книги (Item 9: Always override hashCode
when you override equals)


// The worst possible legal hash function - never use!
@Override public int hashCode() { return 42; }

  
  It’s legal because it ensures that equal objects have the same hash
  code. It’s atrocious because it ensures that every object has the
  same hash code. Therefore, every object hashes to the same bucket, and
  hash tables degenerate to linked lists.


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

Про второй вопрос не очень понятно, но постараюсь ответить. Грубо говоря для определения
места в HashMap мы будем использовать операцию деления по модулю (т.е. hashCode() &
n, где n - количество корзин являющееся степенью двойки). Таким образом при увеличении
количества корзин произойдет перераспределение (пересчет места в таблице) для нового
размера. Но если, как в первом вопросе, функция hashCode() будет возвращать одинаковые
значения, но никакое перераспределение не поможет, элементы останутся в одной корзине.
В том и смысл - если хэш функция генерирует более равномерные результаты, корзины будут
заполняться равномерно, не будет большого количества пустых корзин и перераспределение
будет более эффективным.

Советую так же прочитать:


Структуры данных в картинках. HashMap 
Джошуа Блох, Java. Эффективное программирование 
Joshua Bloch, Effective Java