Как Java реализует хеш-таблицы?

Ответ 1

HashMap и HashSet очень похожи. Фактически, второй содержит экземпляр первого.

A HashMap содержит массив ведер, чтобы содержать его записи. Размер массива всегда равен 2. Если вы не укажете другое значение, изначально есть 16.

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

Записи будут вставлены до тех пор, пока они не достигнут коэффициента нагрузки. Этот коэффициент 0,75 по умолчанию и не рекомендуется изменять его, если вы не очень уверены в том, что делаете. 0,75 в качестве коэффициента загрузки означает, что HashMap из кодов 16 может содержать только записи 12 (16 * 0,75). Затем будет создан массив ведер, удвоив размер предыдущего. Все записи будут помещены снова в новый массив. Этот процесс известен как rehashing и может быть дорогостоящим.

Следовательно, наилучшая практика, если вы знаете, сколько записей будет вставлена, заключается в том, чтобы построить HashMap с указанием его конечного размера:

new HashMap(finalSize);

Ответ 2

Вы можете проверить источник HashMap, например.

Ответ 3

Java зависит от реализации каждого класса метода hashCode() для равномерного распределения объектов. Очевидно, что плохой метод hashCode() приведет к проблемам с производительностью для больших хеш-таблиц. Если класс не предоставляет метод hashCode(), по умолчанию в текущей реализации будет возвращена некоторая функция (т.е. Хеш) адреса объекта в памяти. Цитата из документа API:

Насколько это разумно практично, метод hashCode, определенный классом Объект возвращает разные целые числа для отдельных объектов. (Это обычно реализуется путем преобразования внутренний адрес объекта в целое число, но это техника реализации не требуемый программным обеспечением JavaTM язык).

Ответ 4

Существует два общих способа реализации HashMap. Разница заключается в том, как один имеет дело с столкновениями.

Первый метод, который является одним из пользователей Java, делает каждое ведро в HashMap содержащим односвязный список. Для этого каждый ведро содержит тип Entry, который кэширует хэш-код, имеет указатель на ключ, указатель на значение и указатель на следующую запись. Когда в Java возникает столкновение, в список добавляется еще одна запись.

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

Ответ 5

Своими словами:

Объект Entry создается для хранения ссылки на ключ и значение.

В HashMap имеется массив Entry.

Индекс для данной записи - это хеш, возвращаемый key.hashCode()

Если есть столкновение (два ключа дали один и тот же индекс), запись сохраняется в атрибуте .next существующей записи.

То, как два объекта с одним и тем же хэшем могут быть сохранены в коллекции.

Из этого ответа мы получаем:

   public V get(Object key) {
       if (key == null)
           return getForNullKey();
       int hash = hash(key.hashCode());
       for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
           Object k;
           if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
               return e.value;
       }
       return null;
   }

Сообщите мне, если у меня что-то не так.