Как работает HashMap поиск элемента по хешу?

165

05 сентября 2019, 00:40

О том как работает HashMap в принципе все понятно. Что такое бандлы, сложность поиска и тд. Все это находится в гугле.

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

Как я понимаю, единственный способ получить время доступа О(1) это массив, обращаясь по индексу. Значит, имея хеш какого-то объекта, необходимо его к этому индексу каким-то образом привести, чтобы по хешу получить все тот же О(1).

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

Answer 1

Тут есть пара важных моментов:

каждый бандл это колллекция;
количество этих бандлов это всегда степень 2-ки.

Когда элемент помещается в HashMap'у, то делается дополнительная операция вычисления остатка от деления хэша на количество бандлов. Этот результат и будет индексом бандла, в который попадёт элемент. Также он никогда не будет больше количества бандлов (остаток от деления ведь!)

А учитывая, что количество бандлов это всегда степень 2-ки, то для оптимизации операция деления заменяется операцией логическое И (хэш) и (количество бандлов - 1)