Как работает HashMap в Java 7 и как его модифицировали в Java 8.

Как работает HashMap

Давайте начнем с простого, как работал(работает) HashMap в Java 7. Map - это структура данных, которая манипулирует (хранит, удаляет, возвращает) key - > value элементы. Иначе, это словарь, который хранит ключ(например слово), и значение(количество слов найденных в определенном тексте). Hash (в контексте HashMap) означает что манипуляция с объектами будет происходить через вычисления hash значений ключа. Но что нам дает простое вычисления ключа ? Другими словами это то же значение ключа, но представлено в другом виде, но не тут то было, каждый объект, в зависимости от hash значения ключа, будет складываться в определённое место - bucket.

Представьте что при входе в аптеку вы получили талон(с номером 8), и вам необходимо подойти в ту кассу, в которой обслуживает соответствующие набор номеров(5-10) и вы стали в очередь, то есть заняли последнее место. Bucket - в данном случаи это касса с рангом номеров от n до k, а очередь это связанный список.

Теперь представьте, что входит управляющий аптекой, и пытается найти вас по вашему номеру - 8. Первым делом он находит кассу которая обслуживает именно эти номера, и после по цепочки опрашивает всех, пока не дойдет до вас. Это реализация поиска в HashMap.

Проблема

По хорошему, каждый bucket должен хранить малое количество объектов, а лучше один, это дает нам константную скорость доступа к объекту - O(1). Но все мы понимаем что без коллизий не обойтись, поэтому один bucket может разрастись до больших размеров. В свою очередь это приводит к ухудшению времени поиска этого объекта - O(n). Поэтому умные ребята программисты, придумали как это можно побороть.

Решение

Было принято решение использовать сбалансированное дерево вместо связанного списка - JEP. Но использовать не везде, а лишь когда количество элементов в бакете достигает определенной величины - TREEIFY_THRESHOLD = 8. Такой ход, дает нам более предсказуемое время доступа к обьекту - O(log(n)).

Это изменение затронуло не всех а лишь : java.util.HashMap, java.util.LinkedHashMap и java.util.concurrent.ConcurrentHashMap. Например java.util.HashTable - исключили из списка изменений, по причине что в некоторых приложениях как раз таки необходимо сохранять историю заполнения бакета.

Для тестов можете посмотреть эту сылочку. Исходя из результатов теста, можно привести еще один довод начальнику, для перехода на Java 8.

Спасибо за внимание.