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

Question

[silentproger]

Собственно интересует вопрос, для чего вообще придуман этот механизм с хэшкодами, корзинами, в которых лежат списки объектов с одинаковыми хэшкодами? Почему нет простой карты ссылка->ссылка?

Comments

[Денис Загаевский]

Ivan Sokolov: разве? Strong reference, не? А также остальные, которые явно задаются - weak, soft, phantom.

Answer 1

[Алексей 〒.]

Хэшкод используется для проверки уникальности сохраняемых объектов ключей. Но так как уникальность хэша ограничена длиной типа int, то может возникать коллизия для этого и используются связные списки объектов с одинаковыми хэшкодами.

Почему же не просто ссылки? Представьте, что мы последовательно добавляем в Map два эквивалентных объекта-ключа, ссылки у них разные. Получается в Map будет два объекта, они имеют одинаковые хэши, но разные ссылки. А, по определению, в Map все ключи должны быть уникальны.

Comments

[silentproger]

Разные ссылки -> разные объекты -> разные ключи. Если у меня есть один объект A, у которого поле field1 = 20, field2=30, и объект B того же класса, у которого те же самые значения полей, тогда получится, что в карте как ключи они одновременно не смогут находиться, потому что у них хэшкод одинаковый. Зачем это? Ссылки у них разные, пусть и 2 разных ключа будут, независимо от того, что у них на 100% идентичное содержимое (на момент занесения в карту). Ну вот есть, к примеру, задача: n-ое количество объект с идентичным содержим надо обработать через разные алгоритмы, чтобы потом сравнить как действует каждый алгоритм. Тогда в этом случае HashMap я использовать не смогу.
Интересует именно то, чем обусловлена такая структура Map.

[Максим Мосейчук]

silentproger: хеш-таблица предназначена для быстрого поиска значения по ключу.

У вас есть большие объекты. Например строки. Вместо того, что бы сравнивать длинные строки, хеш-таблица сравнивает короткие хеши, которые чаще всего целиком помещаются в регистр, а значит операция сравнения выполняется за одну машинную команду.
По хешу находится бакет, в котором лежит искомое значение. Тем самым отсекается большая часть заведено неравных элементов. Ну а затем поиск в бакете идёт уже непосредственно по значению.

Та задача, что вы описали, решается обычным списком.

[Максим Мосейчук]

silentproger: ещё раз, другими словами. Назначение хеш-таблицы не хранение, а поиск.

[silentproger]

fshp: "Вместо того, что бы сравнивать длинные строки, хеш-таблица сравнивает короткие хеши"
Я понимаю, что если брать HashMap<String, SomeClass> map, то в этом случая вся эта штука с хэшкодами и equals нужна, поскольку две строки с одинаковым содержимым скорее всего будут разными объектами (map.get("строка") - так по ссылке ничего не найдется, тоже относится и к Integer и тп), но если брать все остальные объекты производимые от кастомных классов, там же смысла в этом нет, проще по ссылке сравнить?
К примеру, есть карта <User, Data>, где ключ - объект типа юзер, а значение - данные, которые ему соответствуют. Вот где-то в программе начинается работа с объектом типа User, необходимо достать соответствующие ему данные, мне надо залесть в эту мапу. Зачем мне там хэшкод переопределять, equals, когда достаточно было бы по ссылке найти ключ и вернуть нужное значение.

[Максим Мосейчук]

silentproger: ну во первых для Integer -128 - 127 это сработает из-за кэша интов.

Во вторых: в кастомных классах вы можете переопределить метод вычисления хеша, сделав требуемое поведение.

В третьих. Пусть объект юзера из БД строиться. Тогда у вас два объекта юзера с одним id будут не равны. Что неверно.

[silentproger]

fshp: осознание пришло, благодарю :)

Answer 2

[Кирилл]

При хорошей хэш-функции получаем временную сложность поиска - O(1). Без хэшкода сложность поиска будет O(n) (при плохой хэш-функции тоже). Корзины нужны для разрешения конфликтов методом цепочек.
Если вы имеете ввиду, что можно использовать адрес объекта вместо хэш-кода, то нельзя из-за того, что GC меняет адреса (операция mark-sweep-compact) или, например, логически эквивалентные объекты могут иметь разные адреса.

Answer 3

[Максим Мосейчук]

Эквивалентные объекты должны иметь эквивалентные идентификаторы.
Ссылки этого не могут обеспечить.