Map изнутри: хеш-таблицы в Go

Map изнутри: хеш-таблицы в Go

Мы уже умеем пользоваться map. Теперь разберёмся, почему map - это O(1), когда это не так, и что делать с конкурентным доступом.

Представь очередь. В связном списке ты знаешь только соседа: чтобы найти нужного, идёшь от одного к другому за O(n). А потом заходит бабуля. Она помнит всех: кто пришёл, кто отошёл, кто «только спросить», кто занимал за рыжим в кепке. Спроси про любого - ответит мгновенно. Бабуля - это hash map: доступ к любому за O(1). Пока ты бежишь по очереди от соседа к соседу - бабуля уже всё знает.

В жизниВ коде
приметы человека («рыжий в кепке»)ключ
полка в бабулиной памятибакет
двое с одинаковыми приметамиколлизия
людей стало столько, что полки не хватаетрост map и эвакуация

Как работает хеш-таблица

Map в Go: hash ключа определяет bucket, коллизии складываются в один bucket

Go использует массив бакетов (bmap). Каждый бакет хранит до 8 пар ключ-значение. При коллизии пара кладётся в свободный слот того же бакета. Когда бакет переполняется - runtime создаёт overflow-бакет и связывает его с основным.

Структура bucket изнутри (упрощённо)

bmap {
    tophash [8]uint8       // верхние 8 бит хеша каждого ключа
    keys    [8]K           // ключи
    values  [8]V           // значения
    overflow *bmap         // указатель на overflow-бакет
}

tophash - оптимизация поиска: при чтении сначала сравниваются 8-битные «хеши хешей», и только при совпадении проверяется полный ключ. Это сильно ускоряет lookup на промахах.

По-бабулиному это «рыжий?». Сначала одна примета, и только если совпала - бабуля вглядывается в лицо целиком.

В PHP массив - это уже ассоциативный хеш-стол (HashTable в Zend), коллизии решаются связыванием через bucket-pointer внутри. Никаких видимых снаружи bmap, tophash или overflow в PHP нет: всё спрятано в C-структурах Zend. PHP-эквиваленты ниже показывают API, а не байтовое представление.

<?php
declare(strict_types=1);

// Обычный PHP-массив - универсальный hash map (и одновременно list)
$m = [];
$m['user:1'] = ['name' => 'Alice'];
$m['user:2'] = ['name' => 'Bob'];

// Для strict-типизации ключей/значений есть ext-ds (`pecl install ds`):
// \Ds\Map поддерживает любые ключи (включая объекты), быстрее на больших данных
$map = new \Ds\Map();
$map->put('user:1', ['name' => 'Alice']);
$value = $map->get('user:1', default: null);

Load factor и рост

Когда отношение count / 2^B превышает 6.5 (количество элементов на бакет), runtime удваивает количество бакетов и постепенно переселяет данные в новые бакеты (evacuation). Это происходит инкрементально на каждой операции записи - без stop-the-world паузы.

m := make(map[string]int)
// внутри: hmap.B = 0 → 1 бакет
// при добавлении ~8 элементов B становится 1 → 2 бакета
// и так далее
<?php
declare(strict_types=1);

// PHP не даёт API для подсказки начальной capacity у обычного array.
// На больших данных снижение реаллокаций даёт \SplFixedArray или \Ds\Map:
$m = new \Ds\Map();
$m->allocate(10000); // зарезервировать capacity заранее
for ($i = 0; $i < 10000; $i++) {
    $m->put('user:' . $i, $i);
}
// Без allocate() Zend ресайзил бы HashTable несколько раз (степенями двойки).

В PHP начальная capacity HashTable - 8 элементов, при превышении он удваивается. Это происходит синхронно (без incremental evacuation как в Go), но единственный запрос обычно не настолько горячий, чтобы это было заметно.

Особенности Go map

Map не safe для конкурентного доступа

m := make(map[string]int)

// fatal error: concurrent map writes
go func() { m["a"] = 1 }()
go func() { m["b"] = 2 }()

Это не panic, а fatal error: программа падает целиком, без шанса восстановиться через recover. Runtime специально включает детектор гонок на map в release-сборках.

<?php
declare(strict_types=1);

// Внутри одного запроса PHP однопоточен - конкуренции нет
$m = [];
$m['a'] = 1;
$m['b'] = 2;

// Кросс-запросное хранилище - APCu (local) или Redis (shared)
apcu_store('users:count', 42);
$count = apcu_fetch('users:count');
// Или через Symfony Cache:
// $cache->get('users:count', fn () => loadFromDb());

В классическом PHP-FPM этой проблемы нет: каждый запрос - изолированный процесс, shared memory отсутствует. Если нужно «общее» хранилище между запросами - используют APCu (in-memory, per-машина) или Redis (распределённое).

Итерация в случайном порядке

m := map[string]int{"a": 1, "b": 2, "c": 3}
for k, v := range m {
    fmt.Println(k, v) // порядок РАЗНЫЙ на каждом запуске
}

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

Это же свойство объясняет, почему индексы в базах данных построены на B-tree, а не на хеш-таблице: по хешу можно найти точное значение, но нельзя пройти диапазон BETWEEN или отдать данные уже отсортированными.

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
    fmt.Println(k, m[k])
}
<?php
declare(strict_types=1);

// PHP-эквивалент: array_keys + сортировка ключей
$keys = array_keys($m);
sort($keys);
foreach ($keys as $k) {
    echo $k . ' => ' . $m[$k] . "\n";
}

// Или короче - ksort напрямую сортирует array по ключам in-place:
ksort($m);
foreach ($m as $k => $v) {
    echo $k . ' => ' . $v . "\n";
}

В PHP противоположное поведение: массив сохраняет порядок вставки (insertion order). Это часть спецификации, а не деталь реализации. Если нужен отсортированный обход - ksort($m).

<?php
declare(strict_types=1);

$m = ['a' => 1, 'b' => 2, 'c' => 3];
foreach ($m as $k => $v) {
    // порядок ВСЕГДА a, b, c - insertion order
}

// Отсортированный обход:
ksort($m); // сортирует по ключам in-place
foreach ($m as $k => $v) {
    echo $k . ' => ' . $v . "\n"; // a, b, c (теперь гарантированно sorted)
}

Конкурентный доступ: sync.Map vs sync.RWMutex+map

Вариант 1: map + RWMutex

type SafeMap struct {
    mu sync.RWMutex
    m  map[string]int
}

func (s *SafeMap) Get(k string) (int, bool) {
    s.mu.RLock()
    defer s.mu.RUnlock()
    v, ok := s.m[k]
    return v, ok
}

func (s *SafeMap) Set(k string, v int) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.m[k] = v
}

Простой, предсказуемый, работает на любых типах. Но при write-heavy нагрузке писатели блокируют всех читателей.

В PHP-FPM аналог sync.RWMutex не нужен внутри одного запроса (нет конкуренции). Для shared state между процессами/инстансами используют symfony/lock:

<?php
declare(strict_types=1);

use Symfony\Component\Lock\LockFactory;
use Symfony\Component\Lock\Store\RedisStore;

final class SafeCounter
{
    public function __construct(
        private readonly \Redis $redis,
        private readonly LockFactory $lockFactory,
    ) {}

    public function increment(string $key): int
    {
        $lock = $this->lockFactory->createLock($key, ttl: 5.0);
        $lock->acquire(blocking: true);
        try {
            $current = (int) $this->redis->get($key);
            $this->redis->set($key, $current + 1);
            return $current + 1;
        } finally {
            $lock->release();
        }
    }
}

symfony/lock - distributed lock через Redis/Postgres/файловую ФС, не in-process mutex. Latency ~миллисекунды, а не наносекунды Go sync.Mutex. Для атомарных счётчиков лучше Redis INCR без явного lock'а.

Вариант 2: sync.Map

var m sync.Map
m.Store("a", 1)
v, ok := m.Load("a")
m.Delete("a")
m.Range(func(k, v any) bool { return true })

sync.Map оптимизирован под два сценария:

  1. Ключ пишется один раз, читается много раз (например, кеш конфигурации).
  2. Разные горутины работают с разными ключами без пересечения.

Внутри есть два уровня хранилища (read - без локов, dirty - под локом) и атомарные операции на чтение. Запись по новому ключу - медленнее обычного map+Mutex, потому что требует синхронизации между уровнями.

Когда что брать

СценарийВыбор
read-heavy, фиксированный набор ключейsync.Map
write-heavy, частые новые ключиmap + sync.Mutex
смешанная нагрузка, простотаmap + sync.RWMutex
очень горячий путь, миллион горутинsharded map (N бакетов с отдельными mutex)

Бенчмарки на конкретном профиле нагрузки обязательны - выбор «по чуйке» часто проигрывает.

В PHP нет sync-примитивов для in-process конкуренции (FPM однопоточен на запрос). Аналоги «глобальной» map'ы между запросами:

  • APCu - in-memory key/value на одну ноду, lock-free atomic operations (apcu_inc, apcu_cas).
  • Redis - распределённый аналог sync.Map: HSET/HGET для maps, INCR для атомарных счётчиков, SET ... NX для оптимистичных блокировок.
  • symfony/lock - распределённые блокировки поверх Redis/Postgres.
<?php
declare(strict_types=1);

// In-memory shared cache per node (APCu)
$key = 'feature:enabled';
if (!apcu_exists($key)) {
    apcu_store($key, true, ttl: 60);
}
$enabled = apcu_fetch($key);

// Atomic increment - thread-safe на уровне APCu
apcu_inc('requests:total');

// Distributed map через Redis (через symfony/cache)
// $cache = new RedisAdapter($redisClient);
// $val = $cache->get('user:42', fn () => $repo->find(42));

Когда map, когда slice

// Проверка наличия - map O(1) vs slice O(n)
seen := make(map[string]bool)
seen["alice"] = true
if seen["bob"] { // O(1)
    // ...
}

// Подсчёт частот
freq := make(map[string]int)
for _, word := range words {
    freq[word]++ // O(1) на каждую операцию
}

На малых данных (< 50 элементов) slice с линейным поиском часто быстрее map из-за cache locality и отсутствия хеширования. Профилируй, если разница важна.

В очереди из пяти человек бабуля не нужна - проще обернуться и посмотреть.

Map как множество (set)

type Set map[string]struct{}

func NewSet() Set {
    return make(Set)
}

func (s Set) Add(key string) {
    s[key] = struct{}{}
}

func (s Set) Has(key string) bool {
    _, ok := s[key]
    return ok
}

func (s Set) Remove(key string) {
    delete(s, key)
}

struct{} занимает 0 байт - идеально для множеств. Альтернатива map[string]bool тратит лишний байт на значение.

<?php
declare(strict_types=1);

// Set через массив с null-значениями: ключ - элемент, значение игнорируем
$set = [];
$set['alice'] = true;
$set['bob'] = true;
isset($set['alice']); // true - O(1)
unset($set['alice']);

// SplObjectStorage - set для объектов (по identity, не по equals)
$users = new \SplObjectStorage();
$users->attach($userA);
$users->contains($userA); // true

// ext-ds: \Ds\Set - быстрый value-set
$tags = new \Ds\Set(['php', 'go', 'algorithms']);
$tags->add('php'); // no-op, уже есть
$tags->contains('go'); // true

В PHP \Ds\Set (ext-ds) - честный value-set с O(1) операциями. \SplObjectStorage - set именно для объектов (по spl_object_id).

Предаллокация map

// ПЛОХО: начинаем с маленького map, постоянные эвакуации
m := make(map[string]int, 0)

// ХОРОШО: знаем примерный размер
m := make(map[string]int, 10000)
<?php
declare(strict_types=1);

// У обычного array нет hint'а размера - Zend ресайзит HashTable сам.
// Для критичных по производительности мест используют \Ds\Map с allocate():
$m = new \Ds\Map();
$m->allocate(10000); // capacity заранее, без промежуточных удвоений
for ($i = 0; $i < 10000; $i++) {
    $m->put('user:' . $i, $i);
}

// Для пар «int-ключ → int-значение» с known max size - SplFixedArray:
$counters = new \SplFixedArray(10000); // C-array, индексация 0..N-1
$counters[42] = 1;

Подсказка размера избегает многократного удвоения бакетов и копирования содержимого. На 10K вставок разница - десятки процентов времени и аллокаций.

Ключи map

Ключом может быть любой comparable тип: числа, строки, bool, указатели, структуры (если все поля comparable), массивы фиксированного размера, интерфейсы (с осторожностью).

type Point struct {
    X, Y int
}

visited := make(map[Point]bool)
visited[Point{1, 2}] = true

НЕ могут быть ключами: слайсы, map, функции, структуры с такими полями. Это compile-time ошибка.

<?php
declare(strict_types=1);

final readonly class Point
{
    public function __construct(public int $x, public int $y) {}
}

// В обычном массиве - сериализуем в строку:
$visited = [];
$key = $point->x . ',' . $point->y;
$visited[$key] = true;

// Или \Ds\Map с объектным ключом:
$visited = new \Ds\Map();
$visited->put(new Point(1, 2), true);
$visited->get(new Point(1, 2)); // работает, если есть __equals (или identity)

В PHP-массиве ключ - только int или string (всё остальное приводится). Объект или массив как ключ - ошибка. Если нужны произвольные ключи (объекты, массивы) - есть \Ds\Map или \SplObjectStorage.

\Ds\Map уважает identity для объектов: два разных экземпляра Point(1, 2) - два разных ключа. Если нужно равенство по значению - сериализуй в строку или объедини с WeakMap.

Интерфейс как ключ - ловушка

var m = map[any]int{}
m[int32(1)] = 1
m[int64(1)] = 2
fmt.Println(m[int(1)]) // 0 - другой тип, другой ключ!
<?php
declare(strict_types=1);

// PHP-противоположность: ключ всегда приводится к int или string.
// int 1, float 1.0, string '1', bool true - все становятся ключом 1
$m = [];
$m[1] = 'int';
$m[1.0] = 'float';   // перезапишет $m[1]
$m['1'] = 'string';  // перезапишет $m[1]
$m[true] = 'bool';   // перезапишет $m[1]
// в итоге $m === [1 => 'bool']

// \Ds\Map уважает тип:
$ds = new \Ds\Map();
$ds->put(1, 'int');
$ds->put('1', 'string');
$ds->count(); // 2 - разные ключи

Сравнение интерфейсов учитывает и тип, и значение. Неявные конвертации не происходят.

Типичные ошибки

1. Чтение nil map работает, запись - panic

var m map[string]int
_ = m["x"]   // OK, вернёт нулевое значение
m["x"] = 1   // panic: assignment to entry in nil map

Всегда make перед записью.

<?php
declare(strict_types=1);

// В PHP нет «nil map» - неинициализированная переменная просто становится array
$m = null;
$m['x'] = 1; // TypeError в strict_types - попытка array-write по null

// Идиоматично - инициализировать пустым array:
$m = [];
$m['x'] = 1; // OK

// Чтение несуществующего ключа без isset() - E_WARNING и null:
$v = $m['nope']; // Undefined array key

// Безопасный паттерн:
$v = $m['nope'] ?? 0; // 0, без warning

В PHP такого нет: неопределённая переменная при записи $m['x'] = 1 автоматически создаётся как массив (с warning или без - зависит от strict mode). Чтение $m['x'] без isset выдаст E_NOTICE/E_WARNING и null.

2. Изменение map во время итерации

for k := range m {
    if cond(k) {
        m[newKey()] = 0 // поведение не определено
    }
}
<?php
declare(strict_types=1);

// В PHP foreach работает над КОПИЕЙ массива (copy-on-write) - можно модифицировать,
// но изменения не видны в текущем цикле:
$m = ['a' => 1, 'b' => 2, 'c' => 3];
foreach ($m as $k => $v) {
    if ($v > 1) {
        $m['new_' . $k] = 0; // добавится в оригинал, но НЕ войдёт в текущий обход
    }
}

// Идиома - собрать изменения и применить после:
$additions = [];
foreach ($m as $k => $v) {
    if (cond($k)) {
        $additions['new_' . $k] = 0;
    }
}
$m = [...$m, ...$additions];

Go формально разрешает удаление текущего ключа, но добавление новых - UB. Собирай изменения в отдельный slice и применяй после цикла.

3. Указатели на значения в map

m := map[string]LargeStruct{}
v := m["x"]
v.Field = 1    // изменяет КОПИЮ, не значение в map!

// FIX: хранить указатели
m2 := map[string]*LargeStruct{}
m2["x"].Field = 1 // работает
<?php
declare(strict_types=1);

// В PHP объекты ВСЕГДА передаются по handle (что-то вроде указателя):
final class LargeData
{
    public int $field = 0;
}

$m = ['x' => new LargeData()];
$v = $m['x'];
$v->field = 1; // изменит тот же объект, что и в $m['x']

// А вот массивы в значении - copy-on-write, как и в Go-примере:
$m2 = ['x' => ['field' => 0]];
$v2 = $m2['x'];
$v2['field'] = 1;       // изменит копию
$m2['x']['field']; // 0

// Идиоматично - либо обернуть в class, либо модифицировать через ключ:
$m2['x']['field'] = 1; // работает напрямую

Go не позволяет брать &m["x"] - потому что эвакуация может перенести значение в памяти.

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой и вести прогресс.