Как реализован тип данных «словарь» (hash map) под капотом и каковы особенности его работы на уровне Senior?

Словарь (hash map) под капотом — это массив корзин (buckets), каждая из которых хранит связный список, дерево или слот для open addressing. Ключ превращается хэш-функцией в число, которое маппится в индекс корзины обычно через (hash & (n-1)) (если размер — степень двойки). Коллизии обрабатываются цепочками (Java 8+ переходит в красно-черное дерево при длине цепочки ≥ 8 и размере массива ≥ 64) или open addressing (например, в Python).

Коэффициент загрузки (load factor) ≈ 0.75 — компромисс между памятью и скоростью. Когда заполнение превышает порог, массив увеличивается (обычно в 2 раза) и все ключи рехэшируются. Это дорогая операция, поэтому на боевых системах стараются задать ожидаемый размер заранее, чтобы избежать ресайзов. Например, в Java при создании HashMap<>(initialCapacity) массив сразу берётся с запасом.

Для Senior важно:

• Хэш-функция. Если ключи — строки, нужно избегать коллизий: для коротких строк подойдёт алгоритм PN-хэширования, для длинных — циклический CRC или SHA (но он медленный). JDK использует собственный hashCode() с XOR-сдвигами, чтобы распределение было равномерным.
• Производительность. Чтение в лучшем случае O(1), в худшем (при плохой хэш-функции или куче коллизий) — O(n). На практике влияет кеш процессора: если корзина маленькая и данные лежат рядом, работает быстро; если цепочка большая — бегаем по указателям в памяти, что даёт cache miss.
• Многопоточность. HashMap небезопасен в многопоточной среде — в Java при ресайзе может возникнуть бесконечный цикл (из-за перекрёстных ссылок). Для многопоточности используют ConcurrentHashMap — сегментная блокировка (Java 7) или CAS+синхронизация на отдельных корзинах (Java 8+). Он работает в разы быстрее synchronizedMap.
• GC. Если ключи — большие объекты, хэш-таблица хранит ссылки на них; при удалении ключей нужно вызывать remove(), иначе они не соберутся сборщиком мусора. LinkedHashMap с ordering позволяет создавать LRU-кэш.

class MyHashMap<K,V> {
    static class Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
    }
    private Entry<K,V>[] buckets;
    private int size;
    private static final float LOAD_FACTOR = 0.75f;

    public V get(K key) {
        int idx = indexFor(key.hashCode());
        for (Entry<K,V> e = buckets[idx]; e != null; e = e.next) {
            if (e.key.equals(key)) return e.value;
        }
        return null;
    }

    private int indexFor(int h) {
        return h & (buckets.length - 1);
    }
}

Этот код опускает ресайз и работу с null, но показывает суть. На собеседовании обычно ожидают, что вы перечислите, как разрешаются коллизии, зачем нужен остаток от деления по степени двойки, и как избежать деградации производительности.