Коллизии в map java

392

08 июня 2017, 06:02

Подскажите пожалуйста, как реализуются коллизии в map java и чем отличаются реализации этих коллизий (массивы и LinkedList)?

Answer 1

Наверное, все-таки, не реализуются, а разрешаются? И не интерфейс Map<K,V>, а класс HashMap<K,V>? Если все так, то читайте ниже.

Существует два основных способа разрешения коллизий:

Метод цепочек. В этом случае корзина (bucket) может хранить несколько элементов, и хранятся они, в большинстве случаев, в виде связного списка (linked list).
Метод открытой адресации. Здесь, при возникновении коллизии, происходит поиск некоторой свободной ячейки, куда и добавляется очередной элемент.

В Java, для разрешения коллизий, используется метод цепочек.

Изначально, корзина в HashMap представляет из себя связный список (linked list). При возникновении коллизии, очередная пара добавляется в этот список.

В последних версиях JDK, в случае, если размер связного списка становится более 8 (константа TREEIFY_THRESHOLD), то происходит преобразование связного списка в дерево, при этом, найти элемент в HashMap в худшем случае уже можно за O(log(n)), а не за O(n), как в связном списке.