Модуль 20 ⏱ ~18 мин чтения 📐 2 Mermaid диаграмм

4. Открытая адресация и метод цепочек

В предыдущих статьях мы установили непреложный математический факт: коллизии неизбежны в силу парадокса дней рождения и принципа Дирихле. Когда два совершенно разных ключа при делении хеша на размер таблицы получают один и тот же целевой индекс (бакет), мы не можем просто записать значение в ячейку — она уже занята.

Для преодоления этой неизбежности компьютерная инженерия выработала два фундаментальных пути: Метод цепочек (Separate Chaining) и Открытая адресация (Open Addressing). Понимание того, как эти две стратегии ведут себя на физическом кремнии процессора и шине памяти, отличает рядового разработчика от инженера, способного создавать сверхэффективные in-memory кэши и высоконагруженные хранилища.

Метод цепочек (Separate Chaining)

Классическая и интуитивно понятная идея метода цепочек заключается в следующем: массив бакетов хеш-таблицы хранит не сами элементы, а указатели на связанные списки. Если при вставке бакет уже занят другим ключом, мы просто создаем новый узел (Node) в памяти и прикрепляем его к связному списку в этой ячейке (в начало или в конец).

flowchart LR
    subgraph Buckets["Массив бакетов (указатели)"]
        B0["[0] nil"]
        B1["[1] ptr"]
        B2["[2] ptr"]
    end

    subgraph Chain1["Цепочка бакета [1]"]
        N1["Узел 1<br/>Key: A, Val: 10"]
        N2["Узел 2<br/>Key: B, Val: 20"]
        nil1["nil"]
    end

    subgraph Chain2["Цепочка бакета [2]"]
        N3["Узел 3<br/>Key: C, Val: 30"]
        nil2["nil"]
    end

    B1 -->|"коллизия"| N1
    N1 --> N2
    N2 --> nil1

    B2 --> N3
    N3 --> nil2

    classDef bucket fill:#1e293b,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    classDef node fill:#334155,stroke:#f59e0b,stroke-width:1.5px,color:#f8fafc;
    classDef nilNode fill:#0f172a,stroke:#64748b,stroke-width:1px,color:#94a3b8;

    class B0,B1,B2 bucket;
    class N1,N2,N3 node;
    class nil1,nil2 nilNode;

Mechanical Sympathy: Боль для процессора

С чисто алгоритмической точки зрения метод цепочек выглядит привлекательно:

  • Устойчивость к высокому коэффициенту заполнения (Load Factor): Даже если элементов в таблице становится больше, чем бакетов ($\alpha > 1.0$), таблица не перестает работать. Цепочки просто удлиняются, а сложность плавно деградирует.
  • Простота удаления: Удалить элемент тривиально — достаточно изменить указатели prev.next = curr.next и освободить память узла.

Однако на уровне современного кремния метод цепочек порождает серьезные аппаратные издержки:

  1. Pointer Chasing (Погоня за указателями): Узлы связного списка выделяются индивидуально и разбросаны по всей виртуальной памяти кучи (Heap). Чтобы прочесть следующий узел, CPU обязан дождаться завершения загрузки адреса из предыдущего узла.
  2. Убийство Cache Locality: Каждое обращение к новому узлу в куче — это почти гарантированный Cache Miss (промах кэша L1/L2/L3). Процессор отправляет запрос контроллеру памяти и простаивает 150–250 тактов (до 50–70 нс), ожидая данные из оперативной памяти (RAM). Аппаратный предсказатель ветвлений и упреждающей выборки (Hardware Prefetcher) бессилен угадать хаотичные адреса в куче.
  3. Нагрузка на сборщик мусора (GC): Каждая вставка узла — это отдельная аллокация в куче (malloc или рантайм runtime.newobject). Для высоконагруженного Go-бэкенда с миллионами мелких объектов это многократно увеличивает объем работы GC, учащая циклы разметки и порождая микрозадержки (STW и фоновый Pacer).

Открытая адресация (Open Addressing)

Открытая адресация предлагает радикально иной инженерный принцип: все данные хранятся внутри одного непрерывного плоского массива. Никаких связных списков, никаких указателей на узлы и никаких дополнительных аллокаций.

Если целевой бакет уже занят, алгоритм не создает список, а ищет следующую свободную ячейку в том же самом массиве по строго определенной формуле (Probe Sequence). Простейший и самый популярный вариант — Линейное пробирование (Linear Probing): если индекс i занят, проверяем i+1, затем i+2 и так далее (с зацикливанием по модулю размера таблицы).

flowchart LR
    H["Хеш ключа: index = 1"] --> S1["[1] Занято (Key: A)"]
    S1 -->|"шаг + 1"| S2["[2] Занято (Key: B)"]
    S2 -->|"шаг + 1"| S3["[3] СВОБОДНО! (Записываем)"]

    subgraph Table["Непрерывный массив в памяти"]
        S0["[0] Занято"]
        S1
        S2
        S3
        S4["[4] Пусто"]
    end

    classDef occupied fill:#1e293b,stroke:#f43f5e,stroke-width:1.5px,color:#f8fafc;
    classDef target fill:#0f172a,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    classDef freeSlot fill:#134e4a,stroke:#10b981,stroke-width:2px,color:#f8fafc;

    class S0,S1,S2 occupied;
    class S3 freeSlot;
    class S4,H target;

Mechanical Sympathy: Радость процессорного кэша

Открытая адресация максимально дружелюбна к архитектуре CPU:

  1. Идеальная пространственная локальность (Cache Locality): Массив лежит в памяти одним монолитным сегментом. При обращении к ячейке [1] контроллер памяти подтягивает в L1-кэш целую кэш-линию (Cache Line) размером 64 байта, куда сразу попадают соседние ячейки [2], [3] и т.д.
  2. Отсутствие промахов кэша: Последовательная проверка соседних ячеек при линейном пробировании выполняется практически со скоростью регистров процессора (1–4 такта CPU), поскольку данные уже находятся в L1/L2 кэше.
  3. Zero Allocations (Ноль аллокаций): Вставка нового элемента не требует вызова malloc или выделения памяти в куче — запись идет в заранее аллоцированный буфер.

Вторая проблема открытой адресации — Кластеризация (Clustering). При линейном пробировании занятые ячейки имеют свойство слипаться в огромные непрерывные блоки (первичная кластеризация). Поиск и вставка в такой блок вырождаются в линейный обход $O(N)$. Чтобы таблица сохраняла эффективность, Load Factor при открытой адресации стараются удерживать не выше 0.6–0.7.

Архитектурный компромисс в Go

Создатели Go (Кен Томпсон, Роб Пайк) проектировали язык для системного программирования и высоконагруженных сетевых сервисов. Они глубоко понимали изъяны обоих подходов: классический метод цепочек губит производительность кэша, а чистая открытая адресация страдает от кластеризации и требует громоздкого механизма надгробий (Tombstones).

В основе хэш-таблицы Go лежит массив структур bmap (бакетов). Главное инженерное решение заключается в том, что bmap — это не одиночный узел списка, а плотный мини-массив, вмещающий ровно 8 пар ключ-значение:

TEXT 
+-------------------------------------------------------------+
| bmap (Bucket)                                               |
|  tophash: [8]uint8  (хранит старшие 8 бит хешей)             |
|  keys:    [8]KeyType                                        |
|  elems:   [8]ElemType                                       |
|  overflow: *bmap    (указатель на следующий бакет при нужде)|
+-------------------------------------------------------------+
  1. Внутри бакета — Открытая адресация и SIMD-дружественность: 8 ключей и 8 значений лежат последовательно в одном блоке памяти. Массив tophash размером всего 8 байт мгновенно проверяется процессором (в 1 инструкцию или короткий цикл) без заглядывания в сами ключи. При попадании в бакет все 8 элементов уже находятся в одной кэш-линии CPU.
  2. Между бакетами — Метод цепочек: Если все 8 слотов бакета заполнены (коллизия 9-го уровня для одного бакета), рантайм Go выделяет overflow bucket (бакет переполнения) и связывает его указателем overflow, как в методе цепочек.

Благодаря этому гибридному дизайну рантайм Go практически полностью устраняет эффект кластеризации (типичный для открытой адресации) и сводит к минимуму хождение по указателям в памяти: обращение к следующему узлу кучи происходит только после быстрой проверки 8 элементов в быстром кэше.

Теперь, заложив надежный фундамент теории, математики и методов борьбы с коллизиями, мы готовы препарировать главную встроенную структуру данных Go до последнего байта. В следующей статье мы разберем: 5. Внутреннее устройство map в Go.