Ассоциативные массивы и хеш-таблицы: устройство, коллизии и реализация в Python, PHP и Go

Ассоциативный массив хранит данные парами ключ-значение и даёт доступ к значению по ключу, а не по порядковому номеру. Телефонная книга, список виртуальных хостов, метки и аннотации объекта Kubernetes, счётчики метрик по имени работают на одной абстракции.

Под ней почти всегда лежит хеш-таблица: массив бакетов плюс хеш-функция, превращающая ключ в индекс. Вставка, поиск и удаление в среднем стоят O(1), в худшем случае деградируют до O(n). Python (dict), PHP (array) и Go (map) дают одинаковый интерфейс при разном устройстве: открытая адресация, упорядоченная хеш-таблица, бакеты по 8 слотов.

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

О версиях. Пороги и внутренние структуры хеш-таблиц меняются от релиза к релизу. Числа ниже описывают типовое поведение CPython, PHP 7 и 8, а также рантайма Go; перед тем как опираться на конкретную константу, сверьтесь с исходниками и release notes своей версии.

Что такое ассоциативный массив и зачем он нужен

Ассоциативный массив (словарь, отображение, dict, map) хранит набор пар «ключ-значение» и адресует значение по ключу. Ключ не обязан быть числом: в Python это любой хешируемый объект (строка, число, кортеж), в PHP только int или string, в Go любой сравнимый тип, кроме слайсов, map и функций.

Ценность структуры в двух свойствах: произвольный ключ вместо числового индекса и быстрый доступ. Поиск строки перебором среди миллиона строк требует до миллиона сравнений, поиск в хеш-таблице сводится к вычислению хеша и одному-двум сравнениям.

Отличие от индексированного массива

Индексированный массив лежит в непрерывной области памяти, доступ идёт по номеру от 0 до n-1, а адрес элемента считается арифметикой: базовый адрес плюс индекс, умноженный на размер элемента (как вычисляется адрес элемента по индексу). Поиска нет вообще, зато ключ ограничен номером в пределах длины.

Возьмём список студентов. В индексированном массиве обращение идёт по номеру: students[3]. В ассоциативном ключом становится имя: students['ivanov']. Второй вариант читается лучше и не ломается при смене порядка записей.

Задача	Python	PHP	Go
Доступ по номеру	list	array с ключами 0, 1, 2	array, slice
Доступ по произвольному ключу	dict	array	map
Порядок вставки сохраняется	да, с версии 3.7	да, всегда	нет

Python
book = {'alice': '555-01-01', 'bob': '555-02-02'}
number = book['alice']

PHP
$book = ['alice' => '555-01-01', 'bob' => '555-02-02'];
$number = $book['alice'];

Go
book := map[string]string{"alice": "555-01-01", "bob": "555-02-02"}
number := book["alice"]

Ассоциативный массив - абстрактный тип данных, а хеш-таблица - одна из его реализаций. Ту же абстракцию строят на сбалансированном дереве: операции стоят O(log n), зато появляется порядок по ключу и выборка диапазоном.

Устройство хеш-таблицы: от ключа до значения

Путь от ключа к значению состоит из трёх шагов.

Хеш-функция превращает ключ в целое число фиксированной разрядности: h = hash(key).
Хеш отображается на индекс в массиве бакетов. При размере таблицы, равном степени двойки, применяют маску: index = h & (size - 1). Иначе берут остаток от деления: index = h % size. Маска дешевле деления, поэтому размеры таблиц часто держат равными 2^k.
По индексу лежит бакет с хешем, ключом и значением. Сначала сравниваются хеши, затем сами ключи: сравнение двух целых дешевле сравнения строк.

При равномерном распределении на бакет приходится около load factor элементов, поэтому поиск проходит за O(1) в среднем. Хранение полного хеша в бакете позволяет отсеять чужие ключи одним сравнением целых.

Слово «бакет» здесь означает ячейку массива, а не контейнер. Массив бакетов - основа таблицы, и его размер выбирают степенью двойки и в CPython, и в Zend, и в рантайме Go (там степень двойки задаёт число бакетов, каждый из которых хранит 8 слотов).

Хеш-функция: требования и примеры

Детерминированность: один и тот же ключ даёт один и тот же хеш в пределах процесса, иначе поиск не найдёт вставленное значение.
Равномерность: хеши распределяются по диапазону без сгустков, особенно в младших битах, которые попадают в индекс по маске.
Скорость: функция вызывается на каждой операции, поэтому дорогие вычисления на каждый байт ключа снижают пропускную способность сервиса.
Стойкость к подбору: если ключи приходят от пользователя, атакующий может подготовить набор, попадающий в один бакет, и превратить O(1) в O(n).

Практика. djb2 (умножение на 33 плюс код символа) годится для простых случаев. MurmurHash3 даёт хорошее распределение и высокую скорость. SipHash-1-3 применяется в CPython для строк и байтов: ключ хеширования выбирается случайно при старте процесса, что закрывает атаку на коллизии, а значение seed задаётся переменной PYTHONHASHSEED, когда нужна воспроизводимость между запусками. Go берёт хеш из рантайма: на amd64 с поддержкой AES работает аппаратный aeshash, иначе memhash, и в оба подмешивается случайный seed hash0. В Zend для строк используется вариант DJBX33A.

Load factor и рехеширование

Load factor (коэффициент заполнения) равен отношению числа элементов к числу бакетов. При 1 000 элементов и 2 048 бакетах он составляет 0,49. Пока значение умеренное, цепочки и пробы короткие; при приближении к единице поиск превращается в перебор.

Пороги отличаются. CPython расширяет таблицу примерно при 2/3 заполнения. Go ориентируется на 6.5 элемента на бакет, то есть на 8 слотов. Zend удваивает таблицу по мере заполнения и перестраивает её после массовых удалений, чтобы убрать пустые бакеты.

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

Расчёт для примера: 10 000 элементов при пороге 2/3 требуют минимум 15 000 бакетов, размер округляется до степени двойки, то есть 16 384 бакета. Плата размазывается по операциям: ёмкость растёт геометрически (1, 2, 4, 8, ...), суммарный объём копирований при n вставках не превышает 2n, отсюда амортизированное O(1) на вставку.

Разовое перехеширование в Python и PHP даёт всплеск задержки на большой таблице: 10 млн элементов копируются целиком внутри одной операции. Go переносит бакеты порциями по нескольку штук на операцию, поэтому рост таблицы растянут во времени.

Коллизии: почему возникают и как разрешаются

Коллизия - ситуация, когда два разных ключа получают один индекс. Причина арифметическая: бакетов конечное число, ключей потенциально бесконечно много. Вероятность хотя бы одной коллизии оценивают как 1 - e^(-n²/2m), где n - число ключей, m - число бакетов. Для 1 000 ключей и 1 000 000 бакетов это около 39%, для 1 000 ключей и 2 048 бакетов - практически 100%.

Вторая причина - слабая хеш-функция: если младшие биты хеша повторяются, ключи кучкуются в узком наборе бакетов и load factor перестаёт что-либо описывать. Третья - подготовленный ввод: набор ключей, подобранный под фиксированный seed.

Метод цепочек

В бакете хранится ссылка на первый элемент цепочки, а записи с одинаковым индексом связываются в список. Поиск идёт по цепочке: сравнение хешей, затем сравнение ключей.

Плюсы: таблица работает при load factor больше 1, удаление сводится к разрыву связи, логика прозрачна. Минусы: каждый элемент платит за указатель (8 байт в 64-битной системе, с накладными расходами аллокатора часто 16-32 байта); узлы разбросаны по памяти, поэтому очередное сравнение ключа даёт промах кэша.

PHP 7 и новее хранит бакеты одним непрерывным массивом в порядке вставки, а коллизии разрешает цепочками бакетов: сочетание даёт локальность памяти и сохранение порядка обхода.

Открытая адресация

Все пары лежат прямо в массиве бакетов. Если ячейка занята, ищут следующую по правилу: линейное пробирование идёт с шагом 1 (i+1, i+2, i+3), квадратичное берёт смещения 1, 4, 9, 16, двойное хеширование вычисляет шаг из второго хеша ключа.

Плюсы: нет указателей на узлы, данные лежат плотно, промахов кэша меньше, памяти на элемент уходит меньше. Минусы: линейное пробирование создаёт кластеры - слитные участки занятых ячеек, удлиняющие пробы для посторонних ключей; удаление требует маркера-надгробия, иначе поиск оборвётся на пустой ячейке и не увидит элементы дальше по пробе.

CPython использует открытую адресацию с псевдослучайным пробированием: смещение зависит от старших битов хеша, поэтому занятые подряд ячейки не превращаются в устойчивый кластер, а размер таблицы остаётся степенью двойки.

Go комбинирует подходы: 8 слотов внутри бакета заполняются открытой адресацией, а переполненный бакет получает бакет-продолжение, то есть цепочку.

Критерий	Метод цепочек	Открытая адресация
Память на элемент	плюс 8-32 байта на указатели	только ключ, хеш и значение
Локальность кэша	низкая	высокая
Удаление	разрыв связи, O(1)	нужен маркер удаления
Load factor выше 1	работает	неприемлем
Кластеризация	отсутствует	есть, лечится нелинейным пробированием

Реализация в Python: dict

dict - хеш-таблица с открытой адресацией и компактным хранением: индексы бакетов лежат в отдельном массиве целых, а записи (хеш, ключ, значение) идут плотным блоком в порядке вставки. Отсюда и порядок обхода: в версии 3.6 он был побочным эффектом реализации, с 3.7 гарантирован спецификацией языка.

Хеш строк и байтов считает SipHash-1-3 с ключом, который рантайм выбирает случайно при старте процесса. Подобрать ключи, попадающие в один бакет, заранее нельзя, и это защищает от отказа через коллизии. Переменная PYTHONHASHSEED фиксирует seed, когда нужна воспроизводимость между запусками.

Расширение запускается примерно на 2/3 заполнения, новая ёмкость берётся от текущего числа записей с запасом, обычно в 2-4 раза. Ключ обязан быть хешируемым: int, str, tuple подходят, list и dict нет.

Особенности и сложность операций

Поиск, вставка и del - O(1) в среднем и O(n) при массовых коллизиях.
Обход items() и values() - O(n), порядок совпадает с порядком вставки.
Память: на 1 млн пар dict занимает порядка 40-50 МБ (оценка для коротких строк и целых, зависит от версии). В 3.11 записи стали компактнее, значения хранятся в одном блоке с ключами.
Словарь не сжимается при удалении отдельных ключей; память возвращает clear() или пересоздание.

fruit = {'apple': 3, 'pear': 5}
fruit['plum'] = 7          # вставка, O(1) в среднем
print(fruit['apple'])      # поиск, выведет 3
del fruit['pear']          # удаление, O(1) в среднем
for k, v in fruit.items(): # обход, O(n)
    print(k, v)

Для кэшей держите ограничение размера: functools.lru_cache с параметром maxsize либо OrderedDict с методом move_to_end, который переносит ключ в конец за O(1) и позволяет вытеснять самый старый элемент.

Реализация в PHP: array

array в PHP - упорядоченная хеш-таблица, которая служит и списком, и словарём. Бакеты лежат одним непрерывным массивом в порядке добавления, поэтому foreach обходит элементы в порядке вставки и сортировка для воспроизводимого вывода не нужна.

Для строковых ключей Zend считает хеш вариантом DJBX33A, коллизии разрешаются цепочками бакетов. С PHP 7 добавлен режим packed array: если ключи идут подряд целыми числами от 0, индексный массив по хешу не нужен и доступ идёт по позиции. Эффект заметен по памяти: упакованный массив на миллион целых в PHP 8 занимает порядка 16-20 МБ, тот же набор со строковыми ключами требует заметно больше.

Ключи приводятся к int или string. Строка с числом без ведущих нулей становится целым ключом, поэтому $arr[1] и $arr['1'] адресуют один элемент. Значения true, false и null превращаются в 1, 0 и пустую строку. Дробный ключ усекается до целого, с PHP 8.1 это устаревшая конструкция.

Сложность и типичные ошибки

Доступ, вставка и unset в среднем выполняются за O(1). Дальше список ловушек, которые чаще всего ломают производительность.

array_shift удаляет первый элемент и переиндексирует весь массив: O(n) на вызов. Очередь на array_shift при 100 000 задач превращается в миллиарды копирований. Для очередей берите SplQueue.
in_array и array_search ищут по значениям линейно, O(n). Если поиск нужен часто, постройте обратный индекс через array_flip, помня, что он работает только со строковыми и целыми значениями.
isset($a['k']) быстрее array_key_exists, но возвращает false, если значение ключа равно null. Для ключей с null-значениями нужен array_key_exists.
После массовых unset бакеты остаются пустыми, таблица перестраивается не сразу, и процесс занимает память по пику, а не по факту.
array_merge переиндексирует числовые ключи; когда ключи нужно сохранить, применяйте оператор сложения массивов или array_replace.

$fruit = ['apple' => 3, 'pear' => 5];
$fruit['plum'] = 7;              // вставка, O(1) в среднем
echo $fruit['apple'];            // 3
unset($fruit['pear']);           // удаление, O(1) в среднем
foreach ($fruit as $k => $v) {   // порядок вставки
    echo $k, ' ', $v, PHP_EOL;
}

Реализация в Go: map

Классическая схема map: массив бакетов, в каждом бакете 8 слотов под пары ключ-значение и массив tophash - по одному байту старших битов хеша на слот. Байты tophash позволяют отбросить несовпадающие слоты, не сравнивая сами ключи. Переполненный бакет получает бакет-продолжение, то есть внутри бакетов работает цепочка.

Хеш считает рантайм: на amd64 с AES это aeshash, иначе memhash, в оба подмешивается случайный seed hash0, выбранный при старте программы. Порядок обхода map намеренно не определён, поэтому код, который на него полагается, ломается при смене версии или нагрузки.

Рост начинается, когда среднее число элементов на бакет превышает 6.5, то есть примерно 52 записи на 8 слотов. Рантайм удваивает число бакетов и переносит данные порциями по нескольку бакетов за операцию, поэтому одиночная вставка не оплачивает весь рехеш целиком. Отдельный случай - рост без удвоения: когда бакетов достаточно, но слишком много бакетов-продолжений, таблица перестраивается в тот же размер, чтобы уложить элементы плотнее.

map - ссылочный тип. Передача в функцию копирует только заголовок, данные остаются общими, как у срезов и представлений с общим буфером (срезы, view и слайсы без копирования данных).

Смена реализации: в Go 1.24 рантайм перевёл map на схему по мотивам Swiss Tables, где слоты сгруппированы иначе и цепочек бакетов нет. Бакетная механика выше описывает версии до 1.24 и остаётся полезной для понимания поведения; константы и стоимость операций сверяйте с release notes своей версии.

Сложность и потокобезопасность

Поиск, вставка и удаление - O(1) в среднем, O(n) в вырожденном случае. map не защищён мьютексом: одновременная запись из двух горутин приводит к фатальной ошибке рантайма (fatal error: concurrent map writes), которую нельзя перехватить через recover. Варианты для конкурентного доступа: sync.RWMutex вокруг обычной map, sync.Map для сценария «много чтений, записи редкие», шардирование на несколько map по хешу ключа при высокой нагрузке на запись.

Удаление не возвращает память: размер бакетов не уменьшается, и map живёт с пиковым размером до конца жизни. Освободить память можно только пересозданием. При известном объёме указывайте размер при создании: make(map[string]int, 100000) резервирует место сразу и убирает первые рехеширования.

m := map[string]int{"apple": 3, "pear": 5}
m["plum"] = 7              // вставка, O(1) в среднем
v, ok := m["apple"]        // поиск: v == 3, ok == true
delete(m, "pear")          // удаление, O(1) в среднем
for k, val := range m {    // обход: порядок не определён
    fmt.Println(k, val)
}

cache := make(map[string]int, 100000) // резерв под 100000 записей

Сложность основных операций: что нужно помнить

Таблица верна для всех трёх языков статьи: везде используется хеширование и геометрический рост таблицы.

Операция	Средний случай	Худший случай
Поиск	O(1)	O(n)
Вставка	O(1) амортизированно	O(n)
Удаление	O(1)	O(n)
Обход всех элементов	O(n)	O(n)
Память	O(n)	O(n)

Реализация	Разрешение коллизий	Порог роста	Порядок обхода
Python dict	открытая адресация с псевдослучайным пробированием	примерно 2/3 заполнения	порядок вставки
PHP array	цепочки бакетов	удвоение при заполнении	порядок вставки
Go map	8 слотов в бакете плюс бакеты-продолжения	6.5 элемента на бакет	не определён, случаен

Худший случай O(n) наступает не только в теории: достаточно слабой хеш-функции или подобранного набора ключей, и все элементы уйдут в один бакет. Порядок величин: при миллионе записей и равномерном распределении поиск занимает десятки-сотни наносекунд, при вырожденном - микросекунды и больше, потому что каждое сравнение ключа превращается в перебор строк. Именно поэтому CPython и рантайм Go рандомизируют seed хеша.

Обратная сторона - память. Все три структуры платят за нагрузку: цепочки держат указатели, открытая адресация оставляет пустые бакеты после удалений, а запас под load factor 0,5 означает, что таблица хранит вдвое больше слотов, чем элементов.

Как выбрать размер таблицы и избежать типичных ошибок

Задавайте размер заранее. Go: make(map[string]int, 100000) выделяет место под нужное число записей одной операцией. Python: публичного API для предвыделения dict нет, но конструктор словаря из последовательности пар с известной длиной получает подсказку по размеру, поэтому dict(zip(keys, values)) для 100 000 пар выгоднее цикла с накоплением. PHP: обычный array ёмкость не принимает, для плотных числовых наборов фиксированного размера есть SplFixedArray.

Держите load factor около 0,5-0,75. Ниже 0,5 вы платите памятью, выше 0,75 растёт средняя длина проб и цепочек. Если таблица на 10 млн элементов растёт при 2/3 заполнения, запас под рехеширование измеряется десятками мегабайт на каждой итерации роста.

Не пишите свою хеш-функцию для стандартных типов. Для пользовательских ключей в Python берите hash от неизменяемых полей, например у frozen dataclass. В Go ключом может быть только сравнимый тип: слайс, map и функция в ключ не годятся, составной ключ собирают в строку или в структуру из сравнимых полей.

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

Практические советы для DevOps

Считайте размер таблиц до выката. Словарь на 10 млн пар со строковыми ключами занимает сотни мегабайт (порядка 400 МБ и выше для Python, оценка зависит от длины строк и версии). В контейнере с лимитом памяти это путь к OOMKill.
Ограничивайте кэши. В Python берите functools.lru_cache с maxsize, для собственного LRU - OrderedDict и move_to_end, это O(1) на обращение. В Go sync.Map подходит для редких записей и частых чтений, а размер контролируйте сами.
Проверяйте настройки хеш-таблиц Nginx: размер таблицы имён виртуальных хостов задают директивы server_names_hash_max_size и server_names_hash_bucket_size, а при слишком маленьком значении конфигурация не собирается и в логе появляется сообщение с просьбой увеличить параметр.
В Kubernetes метки и аннотации объектов - обычные map. Суммарный размер объекта ограничен запросом к etcd (по умолчанию порядка 1,5 МиБ), у аннотаций есть отдельное ограничение по объёму, поэтому хранить в них конфигурацию целиком не стоит.
Оценивайте нагрузку на рехеширование. Если сервис наполняет таблицу в горячем пути, предварительное выделение и прогрев на старте убирают всплеск задержки после рестарта.

Типичные ошибки проектирования:

Хранить в хеш-таблице данные, которым нужен порядок по ключу или выборка диапазоном: порядок вставки не заменяет порядок по значению ключа.
Ждать, что удаление освободит память: в Go map не сжимается, в PHP таблица перестраивается не сразу, в CPython dict освобождает память при clear, но не при удалении отдельных ключей.
Использовать изменяемые объекты как ключи в Python: после изменения полей хеш перестаёт совпадать с сохранённым, и ключ становится недостижимым.
Обращаться к map из нескольких горутин без синхронизации: вместо исключения процесс падает целиком.
Забыть про приведение ключей в PHP: массив с ключом '1' и массив с ключом 1 для интерпретатора одно и то же.

Проверка занимает один рабочий день. Возьмите профилировщик памяти (tracemalloc в Python, memory_get_usage в PHP, runtime.MemStats в Go), измерьте самую крупную таблицу в сервисе до и после прогрева, сравните результат с лимитом контейнера и зафиксируйте порог, при котором начинается рехеширование. Если таблица растёт без границ, ограничение размера и вынос холодных данных во внешнее хранилище обходятся дешевле, чем увеличение лимита памяти.