Почему метод get () в HashMap сравнивает значение хэш-функции и ключ в Java?

Question

Я смотрел на реализацию HashMap в JDK8.В методах get я увидел строку ниже, которая используется для поиска узла, соответствующего данному ключу.

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

Почему необходимо сравнивать значение хеша с ключом?Почему строка выше не написана как:

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

Есть ли объяснение, почему это сделано таким образом?Спасибо.

Answer 1

То, что, кажется, вызывает ваше замешательство, это две вещи:

1.Сравнение значений хеша (часто очень) быстрее, чем прямое сравнение ключей.

2.В операторе == второе условие не будет проверяться, если первое ложно.

Итак, сначала сравниваются значения хеш-функции, что быстро:

• Когда они не равны, вы знаете, что ключи также не равны, и вы сделали.

• Когда они равны, вы не знаете, если ключитакже равны, поэтому вы должны сравнивать ключи, что (относительно) медленно.

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

Answer 2

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

Контракт для hashcode мандатов:

JavaDocs Object.hashCode

Если два объекта равны в соответствии с методом equals (Object), то вызов метода hashCode для каждого из двух объектов должен привести к одинаковому целочисленному результату.

Поэтому, если хэши различны, нет смысла выполнять дальнейшие проверки.

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

---

_{Примечание: * HashMap полагается на то, что ключи не изменяются каким-либо образом, что может изменить их "идентичность "в терминах equals и hashcode - хотя это может показаться очевидным, это явно не упоминается в JavaDocs для HashMap и в прошлом вызывало вопросы: Являются ли изменяемые ключи hashmap опасной практикой? - это охватывается более общим Map контрактом :}

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