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

Question

Кто-нибудь знает, как Java реализует свои хеш-таблицы (HashSet или HashMap)? Учитывая различные типы объектов, которые можно захотеть поместить в хеш-таблицу, кажется, что очень трудно придумать хеш-функцию, которая бы хорошо работала во всех случаях.

Answer 1

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

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

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

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

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

new HashMap(finalSize);

Answer 2

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

Answer 3

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

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

Answer 4

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

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

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

Answer 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;
   }

Дайте мне знать, если я что-то не так.