Решения коллизий в мапе
Коллизия может возникнут при 3 условиях: относительно hash(), относительно hashCode(), и относительно вычисления индекса. Заключим их в двух ситуациях: например, пусть размер таблицы равен size, и есть два объекта: O1 и 02.
(hash(O1.hashcode()) % size) == (hash(O2.hashcode()) % size), причемhash(O1.hashcode()) == hash(O2.hashcode())(hash(O1.hashcode()) % size) == (hash(O2.hashcode()) % size), причемhash(O1.hashcode()) != hash(O2.hashcode())
Что будет в ситуации первой? Что будет в ситуации второй?
Почему делается в первую очередь эта проверка в мапе?
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
Ответы (1 шт):
Предисловие
P.S. Формулировка вопроса оставляет желать лучшего, но раз никто еще не ответил, то я постараюсь додумать и предложить свой вариант ответа.
Насколько я понимаю речь идет об исходниках HashMap из стандартной коллекции java.
Если так, то небольшое превью касательно её устройства (несколько упрощенно) и терминологии:
HashMap представляет из себя массив (также называемый buckets), каждым элементом которого (т.е. каждый bucket) является однонаправленным списком (упрощенный аналог LinkedList).
При вставке элемента в HashMap сначала определяется bucket (индекс массива), куда он должен попасть. Определение bucket'а осуществляется посредством взятия остатка от деления значения hashCode (добавляемого элемента) на длину массива (длину buckets).
P.S. На самом деле, там все несколько сложнее: старшая часть hashCode "замешивается" с младшей (первые_два_байта_hashCode ^ вторые_два_байта_hashCode), т.к. при определении bucket'а участвует только младшая (в вашем вопросе это соответствует операци hash(hashCode())), а от младшей части берутся последние n бит (например, hash(hashCode()) & 0b1111), где n-это степень двойки, которая является размером массива.
Объяснение
Вначале у вас if'ом проверяется факт того, что элементы находятся в одном и том же bucket'е, но это еще не говорит о том, что они равны - просто они были распределены таким образом (см. предисловие).
Если значения hashCode() двух элементов не равны, то это гарантировано разные элементы (второй ваш случай).
Если значения hashCode() двух элементов равны, то, вероятно (но не факт), что это один и тот же элемент (первый ваш случай). Тем не менее, hashCode() выдает значение из множества int, которое ограничено 4 байтами (2^32 уникальных значений), как следствие множество hashCode() гарантировано меньше, чем потенциальное количество элементов, которых можно создать в java (оно ограничено лишь доступным размером "кучи" (она же, heap)).
Как следствие, для проверки равенства элементов приходится также сравнивать и сами значения элементов, посредством вызова метода equals().
Можно было бы подумать: "Почему бы сразу не вызвать equals, зачем сравнивать hash?"
Сначала сравниваются на равенство hash, т.к. побитово сравнить примитивные 4-байтные int'ы куда быстрее, нежели вызвать equals для каждого экземпляра класса, где в общем случае может находиться какой-угодно код сравнения (возможно, написанный крайне неэффективно).
Конечно же, в частном случае (когда в bucket'е ровно один элемент или несколько, но их hashCode'ы равны) это может оказаться самую малость менее выгодно.