2

Здраствуйте, вопрос вроде простой, но внятный ответ найти не смог. И так: из коллекций Java я усвоил, что они основываются либо на массивах, либо на взаимоссылках. Всё понятно. Про HM везде объяснение начинается с "вот есть бакеты/корзины"..."которые хранят пару ключ-значение"..."вот есть несколько бакетов"... и т.д. Что из себя представляет бакет (объект с полями К-З, массив, лист?)? Как хранятся эти бакеты (Массив бакетов, лист бакетов?)? Вот в общем и весь вопрос. Дальше про механизм работы мне всё понятно. Спасибо!

8
  • в зависимости от версии джавы. раньше это был обычный двусвязный список, т.е. linkedlist. т.е. по хешу вы ищите бакет со сложностью о(1), а дальше все, что в одном бакете (случаи коллизии) простым перебором, т.е. сложность о(n). для понимания этого думаю достаточно (по крайней мере для начала). 27 дек 2020 в 10:13
  • если линклист, то у него скорость поиска O(n), там же надо по ссылкам идти к нужному объекту? 27 дек 2020 в 10:41
  • все верно, а я как написал? до бакета по хешу о(1), а внутри бакета, т.е. по самому линкедлисту, о(n) 27 дек 2020 в 10:42
  • Ок, а бакеты-то как хранятся? В виде какой структуры? 27 дек 2020 в 18:46
  • третий раз : бакеты - это линкедлист 27 дек 2020 в 22:32

2 ответа 2

2
  • Да, правильно, массив бакетов
  • Но в бакетах не LinkedList, а односвязанный список, в котором есть ссылки только на next node
  • Односвязанный список меняется на красно-черное бинарное дерево при достижении количества его элементов 8 (TREEIFY_THRESHOLD = 8) и обратно при уменьшении кол-ва элементов до 6 (UNTREEIFY_THRESHOLD = 6)
2
  • понял, ввела в заблуждение следующая картинка: cdn.javarush.ru/images/article/…. Отличие односвязного списка от ЛинкедЛист - то, что ссылка у узла есть только на следующий узел? Я так понял. Большое спасибо за ёмкий ответ, кстати. 17 янв 2021 в 17:14
  • 1
    @ДенисКондратов, да, принципиальное отличие от двусвязанного списка в этом. Но вообще это другая структура данных, другой класс. В HashMap список в бакете это java.util.HashMap.Node.
    – pazukdev
    18 янв 2021 в 7:31
1

Всё разобрался, бакеты - это ячейки в обычном массиве которые представляют собой линклисты(с переходом в дерево при определенных условиях). Т.е. хэшмап, упрощённо, массив линклистов.

1
  • 2
    Если под "линклист" подрозумевается LinkedList, то это не так. Там не LinkedList. Там односвязанный список.
    – pazukdev
    17 янв 2021 в 14:03

Ваш ответ

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

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