Вот я создаю HashMap, по умолчанию у нее 16 ячеек, вставляю в нее несколько значений с разным ключом, хэш функция проверяет, в зависимости от ключа, в какую ячейку вставить значение.
Вот я вставил значения:
map.put(1,"one");map.put(4,"four");map.put(2,"two");map.put(3,"three"),
места для их вставки в хэш таблицу определила хэш функция, и они вставились по очереди по возрастанию значения ключа.
Но есть ситуация, когда значения могут иметь разные ключи но один хэш код(сгенерировать такую ситуация у меня не получается), по этому, предположим, я произвожу вставку еще одного элемента, и тут у него вычисляет такой же хэш код как и у элемента (1,"one"), в этом случае, в статье предлагаются 2 способа решения:
1. Метод ячейки - когда каждая ячейка представляет собой список из элементов, в котором хранятся элементы с одинаковых хэш кодом.
2. Метод адресации - когда для значения, с таким же хэш кодом, ищется пустая ячейка, где-то, после этого значения.
Проблема в том что про это написали, а как это реализовать - не показали. И я не могу понять, то ли это все автоматически работает при добавлении нового значения в хэш таблицу, либо нужно самому создавать какие-то методы, и описывать поведение при коллизии.
А так же, как пометить ячейку как удаленную, чтобы алгоритм поиска не нарушился?
Сергей Горностаев,
1) Способы решения(метод ячейки и метод адресации), они встроенные в hashmap или их нужно самому писать как отдельные методы, которые срабатывают при коллизии? То есть, если произойдет колизия, то что произойдет то вообще, вот я вставляю новое значение, и ее хэш совпадает с хэшем уже существующего элемента в таблице, что будет? Сработает метод ячейки или метод адресации, или ничего не сработает?
2) Как очистить ячейку, чтобы она была помечена как удаленная, чтобы алгоритм поиска не нарушился?
Если речь про стандартный HashMap, то там, конечно, всё работает из коробки. Там реализован, условно, метод цепочек. Но, на самом деле, там строятся не цепочки, a сбалансированные деревья(rb-tree).
Если речь про самописную реализацию, то в ней, конечно, всё надо руками писать. В каждой ячейке - список, или каким-то образом искать пустую ячейку.
foonfyrick, нужно знать, как оно устроено, чтобы понимать, как с ним работать. Например, если ключ - это твой класс, то нужно правильно и консистентно переопределить equals и hashCode. Также нужно не заучить, какая сложность вставки в хэштаблицу, а уметь прикинуть на ходу. Если ты понимаешь, что внутри, то работаешь с этим не как с магическим чёрным ящиком, а вполне осознанно. Например, есть IdentityHashMap, она вообще-то нарушает контракт Map, но иногда бывает полезна. А есть SortedMap(TreeMap), у неё внутри rb-tree, сложности операций другие, зато есть полезные свойства, типа того, что ключи отсортированы. Но почему и как они отсортированы, лучше знать, а не просто полагаться на слово Sorted. A есть LinkedHashMap, она тратит дополнительную память на поддержание связного списка для фиксации порядка итерации по ключам. Новые свойства опять. Имхо, просто всё это заучивать бессмысленно, а если ты понял идею, то можешь по ней сделать выводы.
Писать свою реализацию обычно бессмысленно, в каких-то очень редких случаях, наверное нужно. Обычно стандартные библиотека языка содержит словарь в том или ином виде. Но на собеседованиях я, например, иногда спрашиваю. На этой задаче мне удобно смотреть, как человек пишет код.
Хэш код нужен только для распределения ключей по группам (спискам). А поиск осуществляется простым перебором по списку и сравнением equal.
То есть создаёте к примеру два списка. При добавлении объекты с четным хэшем кладете в первый список, с нечётным в другой. Так же и поиск. Если хэш чётный перебираете первый список, нечётный второй.
Получается эффективнее в два раза чем просто один список. Если хэш делить на четыре или восемь групп, то будет ещё эффективнее при большем количестве элементов.
Средний
Средний
