1 Тема від capitaNemo

  • capitaNemo
  • Користувач
  • Поза форумом
  • Дата реєстрації: 05.03.2019
  • Повідомлень: 10
    • Репутація: 0

Тема: Концепція HashMap & HashSet

Вивчаю колекції, намагаюся підвести підсумки по HashMap & HashSet якщо я в чомусь не правий, пишіть

Я знаю що HashMap це просто масив з об'єктів Entry, які в свою чергу містять два об'єкти - це ключ і значення. Потім з ключа береться хешкод і по ньому визначається в якому індексі буде лежати даний об'єкт Entry. Кожен індекс масиву це зв'язаний список, так як індекси двох Ентрі об'єктів можуть збігтися і тоді під одним індесок будуть знаходитися декілька Entry об'єктів (у зв'язаному списку)

Питання 1: Тобто hashmap це просто масив (нехай ArrayList), який містить пов'язані списки (нехай ArrayList <LinkedList>) а ті в свою чергу складаються з об'єктів Entry (нехай ArrayList <LinkedList <Entry >>), так?

Питання 2: Я так розумію HashSet працює так само, масив з пов'язаних списків (Бакета), по хешкоду визначається індекс, але ці пов'язані списки (елементи масиву) вже не містять об'єкти Entry а сам об'єкт який ми помістили в HashSet, так?

За наведеним прикладом не судіть строго просто питаюсь на простих прикладах зрозуміти цю концепцію

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 602
    • Репутація: 13310

Re: Концепція HashMap & HashSet

Питання 1: загалом є кілька різних ідей, що саме робити при колізіях. Є описані вами ланцюжки. Є відкрита адресація, коли при колізії шукається наступний кандидат на місце, далі ще один і т.д., доки не знайдеться пуста комірка. Зараз популярне т.зв. "гешування Робін Гуда" (англ. Robin Hood hashing), коли значення може викидатися з комірки при колізії, якщо пошук за новим значенням буде в середньому швидшим; але що саме використовується в Java - треба лізти в документацію, цілком можливо, що це лишається на реалізацію, а стандарт вимагає тільки підтримувати інтерфейс.
Питання 2: так.

Подякували: capitaNemo, leofun012

koala вебсайт