Map изнутри: хеш-таблицы в Go
Map изнутри: хеш-таблицы в Go
Мы уже умеем пользоваться map. Теперь разберёмся, почему map - это O(1), когда это не так, и что делать с конкурентным доступом.
Представь очередь. В связном списке ты знаешь только соседа: чтобы найти нужного, идёшь от одного к другому за O(n). А потом заходит бабуля. Она помнит всех: кто пришёл, кто отошёл, кто «только спросить», кто занимал за рыжим в кепке. Спроси про любого - ответит мгновенно. Бабуля - это hash map: доступ к любому за O(1). Пока ты бежишь по очереди от соседа к соседу - бабуля уже всё знает.
| В жизни | В коде |
|---|---|
| приметы человека («рыжий в кепке») | ключ |
| полка в бабулиной памяти | бакет |
| двое с одинаковыми приметами | коллизия |
| людей стало столько, что полки не хватает | рост map и эвакуация |
Как работает хеш-таблица
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 ~миллисекунды, а не наносекунды Gosync.Mutex. Для атомарных счётчиков лучше RedisINCRбез явного 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 оптимизирован под два сценария:
- Ключ пишется один раз, читается много раз (например, кеш конфигурации).
- Разные горутины работают с разными ключами без пересечения.
Внутри есть два уровня хранилища (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"] - потому что эвакуация может перенести значение в памяти.
- Concurrency - sync: мьютексы, пулы и sync.Map - потокобезопасная альтернатива map: когда нужна sync.Map и сравнение с RWMutex+map