HashMap. Реализация подробно рассмотрена во множестве статей, например на хабре.Нюансы которые стоит повторить и запомнить:
🔘 Общий принцип: внутренний массив
table, содержащий бакеты (корзины) – списки элементов с одинаковыми пересчитанными хэш-суммами;🔘 Пересчет хэш-суммы для умещения
int индексов в capacity ячейках table;🔘
rehash – удвоение размера table при достижении threshold (capacity*loadFactor) занятых бакетов;🔘 Невозможность сжать однажды раздувшийся
table;🔘 Два способа разрешения коллизий: используемый в
HashMap метод цепочек и альтернатива – открытая адресация;🔘 Варианты для многопоточного использования: пересинхронизированная
Hashtable и умная ConcurrentHashMap;🔘 Оптимизация Java 8: превращение списка в бакете в дерево при достижении 8 элементов – при большом количестве коллизий скорость доступа растет с O(n) до O(log(n));
🔘 Явное использование бакета 0 для ключа
null;🔘 Связь с
HashSet – HashMap, в котором используются только ключи;🔘 Нет гарантий порядка элементов;
Обсуждая этот вопрос на интервью вы обязательно затронете особенности методов equals/hashCode. Возможно придется поговорить об альтернативных хранилищах ключ-значение – TreeMap, LinkedHashMap.