Какие данные нужны для сохранения объекта в хэш-таблице
Что проверяют
Понимаете ли вы, как хэш-таблица устроена изнутри, а не только как вызвать put(). Следом почти всегда спрашивают про контракт equals() и hashCode() и про то, что будет, если ключ изменить после вставки.
Как отвечать
Для сохранения нужны ключ и значение, но работает таблица на трёх вещах, которые даёт ключ:
hashCode()ключа: по нему выбирается корзина. ВHashMapхэш дополнительно перемешивается (h ^ (h >>> 16)), а индекс считается как(n - 1) & hash, поэтому ёмкость всегда степень двойки;equals()ключа: в одной корзине может лежать несколько записей, и нужную находят сравнением. Контракт простой: равные объекты обязаны давать одинаковый хэш, обратное не требуется;- неизменяемость ключа: хэш вычисляется один раз при вставке и хранится в узле. Поменяли поле, от которого зависит
hashCode(), и запись осталась в старой корзине,get()её уже не найдёт.
Сама запись это узел с полями hash, key, value, next. Коллизии в HashMap решаются цепочками, а при восьми элементах в корзине и таблице от 64 ячеек цепочка превращается в красно-чёрное дерево. Ёмкость по умолчанию 16, коэффициент загрузки 0.75: когда элементов становится больше 12, таблица удваивается и записи перераскладываются.
Для Android стоит добавить своё. В Kotlin data class генерирует equals() и hashCode() сам, поэтому такие классы удобны как ключи, если поля объявлены через val. Для небольших коллекций есть ArrayMap (меньше памяти, бинарный поиск по массиву хэшей), а для ключей Int есть SparseArray, который обходится без упаковки в Integer.
Где спотыкаются
Переопределяют equals() и забывают hashCode(). Два «равных» объекта попадают в разные корзины, и в HashSet появляются дубли.
Используют как ключ изменяемый объект, например data class с var, и меняют его после put(). Запись есть в карте, а найти её нельзя.
Говорят, что хэш уникален или что hashCode() это адрес объекта в памяти. Коллизии нормальны, а значение по умолчанию лишь идентификатор объекта, про адрес спецификация ничего не обещает.