Что такое бакет в хэш-таблице
Что проверяют
Понимаете ли вы устройство HashMap из стандартной библиотеки и помните ли, что на мобильном устройстве у него есть цена. Вопрос базовый, но для Android хороший ответ всегда заканчивается разговором про память и про специализированные коллекции.
Как отвечать
Бакет это ячейка внутреннего массива таблицы. Индекс берётся побитовым И от хэша и размера таблицы минус один, поэтому размер всегда степень двойки. Перед этим хэш перемешивается: старшие биты подмешиваются к младшим, иначе значимой осталась бы только младшая часть.
Коллизии разрешаются цепочкой внутри бакета. Когда цепочка в одном бакете становится длинной, а сама таблица достаточно большая, список перестраивается в сбалансированное дерево, и поиск внутри бакета становится логарифмическим вместо линейного.
При достижении коэффициента заполнения таблица удваивается, и содержимое каждого бакета разбивается на две части по одному дополнительному биту хэша.
Для Android важна вторая половина ответа. Каждая запись это отдельный объект узла, а примитивные ключи уходят в обёртки. Поэтому для небольших словарей есть ArrayMap с двумя массивами и бинарным поиском по отсортированным хэшам, и SparseArray для целочисленных ключей без упаковки; бакетов там нет вовсе.
Где спотыкаются
Нарушают контракт equals и hashCode. Переопределили одно и забыли второе, и объект кладётся в один бакет, а ищется в другом. В Kotlin это обычно закрывает data class, но ровно до момента, когда поле добавят в класс и забудут про сравнение.
Кладут в ключ изменяемый объект и меняют его после вставки. Хэш посчитан при добавлении, запись остаётся в старом бакете, и по тому же самому ключу словарь её больше не находит.
Считают ArrayMap бесплатной заменой везде. Он выигрывает по памяти на десятках элементов, а на тысячах проигрывает: вставка в середину массива и бинарный поиск стоят дороже прямого попадания в бакет.