middle
Как реализована HashMap — на основе открытой адресации или метода цепочек
HashMap реализован на основе метода цепочек (chaining). Каждой корзине (ячейке массива) соответствует связный список (или красно-черное дерево при большом количестве коллизий), в который добавляются элементы с одинаковым индексом корзины.
| Характеристика | Метод цепочек (HashMap) | Открытая адресация |
|---|---|---|
| Load factor | Может быть > 1 | Должен быть < 1 |
| Деградация | Линейная | Резкая при заполнении |
| Удаление элементов | Простое | Сложное (tombstones) |
| Потребление памяти | Доп. объекты Node | Только массив |
| Сериализация | Сложнее | Проще |
| Пример в JDK | HashMap | IdentityHashMap |
Метод цепочек выбран потому, что он гибче: load factor может превышать 1, производительность деградирует плавно, удаление элементов тривиально. Открытая адресация используется в IdentityHashMap (линейное пробирование), где она оправдана простотой реализации и отсутствием необходимости создавать Node-объекты.
На собеседовании: назовите метод цепочек и объясните, почему. Сравните с открытой адресацией: плюсы (гибкость, простое удаление) и минусы (накладные расходы на Node).