Что сравнивается при добавлении в бакет HashMap: ключи или значения?
Что проверяют
Понимаете ли вы устройство HashMap, а не только её интерфейс. Формулировка провокационная: если ответить «значения», разговор про equals и hashCode дальше не пойдёт. Для Android это ещё и разговор про выбор структуры под ограниченную память.
Как отвечать
Сравниваются ключи. Значение при добавлении не участвует ни в выборе корзины, ни в проверке на совпадение, оно просто ложится рядом с ключом.
Порядок такой: у ключа берётся hashCode, результат домешивается сдвигом, чтобы старшие биты влияли на результат, по нему считается индекс корзины. Пустая корзина принимает пару сразу. Если корзина занята, новый ключ сверяется с каждым уже лежащим там: сначала сравнение ссылок и сохранённого хеша, и только при совпадении вызывается equals. Совпал существующий ключ, обновляется значение, сам ключ остаётся прежним, а put возвращает старое значение. Не совпал, пара добавляется в ту же корзину.
Длинная цепочка в одной корзине в современных версиях перестраивается в дерево, чтобы поиск не деградировал до линейного. Значения перебираются только в containsValue, и это честный обход всей карты.
Стоит упомянуть и рост: пары лежат в массиве корзин, при достижении порога заполненности массив удваивается и все записи раскладываются заново, поэтому под известный объём вместимость задают сразу в конструкторе.
Где спотыкаются
Переопределяют equals и забывают hashCode. Объект кладётся в одну корзину, а ищется в другой, и get возвращает null на ключе, который «точно там есть».
Кладут ключом изменяемый объект и правят его поля после вставки. Хеш считается заново, индекс уезжает, запись становится недостижимой, но память занимать продолжает.
Считают HashMap единственным вариантом на Android. На коллекциях из десятков элементов ArrayMap и SparseArray экономят память и упаковку примитивов, и на горячем пути с целочисленными ключами разница заметна.