Какова цель хранения хеша в Node of HashMap?

Question

static class Node implements Map.Entry {
      final int hash;
      final K key;
      V value;
      Node next;

}

Во внутренней реализации HashMap в java узел хранит хэш.

Почему он используется?Я не вижу в этом необходимости.

Answer 1

Я считаю, что основной причиной является повышение производительности.Вызов equals() может быть дорогим для некоторых объектов.С помощью Оценка короткого замыкания jvm не нужно вызывать equals(), если хеш уже не совпадает

Так реализовано getNode (вызывается, когдаитерация по сегменту для поиска узла.

     if (first.hash == hash && 
         ((k = first.key) == key || (key != null && key.equals(k))))

//( Same HashCode AND ((Same Object reference of the Key) OR (equal method says True in Key Object) )

Редактировать: как упоминалось @moreON, хэш также необходим для перехеширования

Answer 2

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

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

Редактировать: Также не самая лучшая точка зрения, которую Энди К поднял в своем ответе (а я полностью упустил) - при добавлении элементов строгое равенствосравнение должно быть сделано для ключа - при любом разрешении коллизий несколько хешей будут сталкиваться из-за гораздо меньшего размера карты хеш-функции, чем набор возможных результатов хеш-функции.Использование предварительно вычисленного хеша позволяет быстро тестировать неравенство.