Создавали ли свою реализацию HashMap

Что проверяют

Вопрос не про факт написания, а про то, понимаете ли вы устройство хеш-таблицы: хеш-функция, бакеты, коллизии, рост таблицы, контракт equals/hashCode. На Android к этому добавляется вопрос, уместна ли вообще HashMap там, где память дороже удобства.

Как отвечать

Честно: писали учебно или на собеседовании, в приложении брали готовую. Дальше показать устройство. Массив бакетов, индекс считается от хеша ключа, коллизии складываются в цепочку внутри бакета, при переполнении таблица растёт и ключи перераспределяются. В JDK индекс берётся как (n - 1) & hash при размере, равном степени двойки, а сам хеш дополнительно перемешивается (h ^ (h >>> 16)), чтобы на номер бакета влияли и старшие биты. Длинная цепочка перестраивается в дерево, порог заполнения по умолчанию 0.75.

Минимальный каркас:

private fun indexOf(key: K): Int {
    val h = key.hashCode()
    return (h xor (h ushr 16)) and (table.size - 1)
}

Android-часть ответа: для небольших коллекций есть ArrayMap и SparseArray. Они хранят данные в двух массивах, не создают объект Entry на каждую пару и не боксят Int, поэтому на сотнях элементов выигрывают по памяти, проигрывая по скорости поиска.

Где спотыкаются

Берут индекс как hashCode() % size. Хеш бывает отрицательным, индекс уходит в минус, и реализация падает на первом же таком ключе. Нужна маска and (n - 1) при степени двойки либо Math.floorMod.

Ломают контракт ключа: переопределили equals без hashCode, либо положили в карту изменяемый объект и потом поменяли его поля. Ключ остаётся в старом бакете, а get возвращает null, хотя запись в карте есть.

Говорят «доступ всегда за O(1)». Это средняя оценка при равномерном хеше, при плохом хеше всё вырождается в перебор цепочки. Отдельно путают гарантии: HashMap не потокобезопасна и порядка обхода не обещает, порядок вставки держит LinkedHashMap.