1

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

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

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

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

3
  • 2
    Не вот это случайно? habr.com/ru/post/421179
    – andreymal
    27 янв 2019 в 16:51
  • @andreymal, да. Спасибо. Я не так хорошо пользуюсь гуглом) Теперь даже не знаю что с вопросом делать 27 янв 2019 в 17:01
  • Ну, так как Stack Overflow стремится быть самодостаточной базой знаний и ответы-ссылки здесь как бы не очень одобряются, может, кто-нибудь ещё и полноценный ответ здесь напишет)
    – andreymal
    27 янв 2019 в 17:04

1 ответ 1

2

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

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

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

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.