@foonfyrick

HashMap коллизия?

Вот я создаю HashMap, по умолчанию у нее 16 ячеек, вставляю в нее несколько значений с разным ключом, хэш функция проверяет, в зависимости от ключа, в какую ячейку вставить значение.
Вот я вставил значения:
map.put(1,"one");map.put(4,"four");map.put(2,"two");map.put(3,"three"),
места для их вставки в хэш таблицу определила хэш функция, и они вставились по очереди по возрастанию значения ключа.
Но есть ситуация, когда значения могут иметь разные ключи но один хэш код(сгенерировать такую ситуация у меня не получается), по этому, предположим, я произвожу вставку еще одного элемента, и тут у него вычисляет такой же хэш код как и у элемента (1,"one"), в этом случае, в статье предлагаются 2 способа решения:
1. Метод ячейки - когда каждая ячейка представляет собой список из элементов, в котором хранятся элементы с одинаковых хэш кодом.
2. Метод адресации - когда для значения, с таким же хэш кодом, ищется пустая ячейка, где-то, после этого значения.

Проблема в том что про это написали, а как это реализовать - не показали. И я не могу понять, то ли это все автоматически работает при добавлении нового значения в хэш таблицу, либо нужно самому создавать какие-то методы, и описывать поведение при коллизии.
А так же, как пометить ячейку как удаленную, чтобы алгоритм поиска не нарушился?
  • Вопрос задан
  • 86 просмотров
Решения вопроса 2
zagayevskiy
@zagayevskiy Куратор тега Java
Android developer at Yandex
Если речь про стандартный HashMap, то там, конечно, всё работает из коробки. Там реализован, условно, метод цепочек. Но, на самом деле, там строятся не цепочки, a сбалансированные деревья(rb-tree).

Если речь про самописную реализацию, то в ней, конечно, всё надо руками писать. В каждой ячейке - список, или каким-то образом искать пустую ячейку.
Ответ написан
@gsaw
Хэш код нужен только для распределения ключей по группам (спискам). А поиск осуществляется простым перебором по списку и сравнением equal.

То есть создаёте к примеру два списка. При добавлении объекты с четным хэшем кладете в первый список, с нечётным в другой. Так же и поиск. Если хэш чётный перебираете первый список, нечётный второй.

Получается эффективнее в два раза чем просто один список. Если хэш делить на четыре или восемь групп, то будет ещё эффективнее при большем количестве элементов.

Или вопроса не понял.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Emphasoft Санкт-Петербург
от 200 000 до 400 000 ₽
The AnyLogic Company Санкт-Петербург
от 180 000 ₽
от 150 000 до 400 000 ₽
07 мар. 2021, в 15:26
7000 руб./за проект
07 мар. 2021, в 15:07
20000 руб./за проект
07 мар. 2021, в 14:55
3000 руб./за проект