Хеш-таблица изнутри: коллизии, бакеты и цена O(1)

Хеш-таблица изнутри: коллизии, бакеты и цена O(1)

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

ℹ️ Если ты выбрал не Go

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

Python: dict это хеш-таблица с открытой адресацией и компактным устройством с версии 3.7 - поэтому порядок вставки сохраняется, тогда как в Go порядок обхода намеренно случайный. Аналог sync.Map не нужен в том же виде: у CPython есть GIL, но это не делает операции над dict атомарными в составных сценариях, и для них так же нужен Lock.

PHP: array и есть хеш-таблица, отдельного типа для отображения нет. Отсюда особенности: числовые и строковые ключи в одном массиве, сохранение порядка вставки, а SplObjectStorage нужен там, где ключом должен быть объект.

Что переносится в любой язык: почему средний доступ O(1), а худший O(n); почему хеш-таблица проигрывает массиву на маленьких наборах и на последовательном обходе; зачем предаллокация; почему нельзя рассчитывать на порядок, если язык его не гарантирует; и что параллельный доступ надо защищать.

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

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

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

Map в Go: hash ключа выбирает группу, control word отсеивает чужие ключи за одну операцию

Ключ прогоняется через хеш-функцию - получается число. Старшие биты этого числа выбирают, где искать, младшие помогают быстро отсеять чужие ключи.

Группы по 8 слотов и control word

Начиная с Go 1.24 map устроен по схеме Swiss Tables. Хранилище - массив слотов, разбитый на группы по 8 слотов. К каждой группе прицеплено 64-битное control word: по одному байту на слот.

Байт говорит, что со слотом: пусто, удалено или занято. Если занято - в байте лежат младшие 7 бит хеша ключа (h2).

группа: 8 слотов подряд
control word (64 бита): [h2₀][h2₁][h2₂][h2₃][h2₄][h2₅][h2₆][h2₇]
                          ↑ байт на слот: пусто / удалено / 7 бит хеша

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

Важно, что сравниваются не ключи, а метаданные. Совпадение h2 - это ещё не ответ, а кандидат.

Совпал h2 - есть кандидат, и только тогда сравнивается полный ключ: 7 бит хеша совпадают у разных ключей с вероятностью около 1/128.

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

Если во всей группе не нашлось ни нужного ключа, ни пустого слота - поиск переходит к следующей группе.

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

До Go 1.24 внутри было иначе: массив бакетов bmap по 8 пар, tophash из старших 8 бит хеша и overflow-бакеты, связанные в цепочку. Статья, в которой упоминаются bmap и overflow, описывает Go 1.23 и раньше. Снаружи не изменилось ничего: спецификация языка и ваш код те же.

В PHP массив - это уже ассоциативный хеш-стол (HashTable в Zend), коллизии решаются связыванием через bucket-pointer внутри. Никаких видимых снаружи групп, control word или h2 в 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);

Рост: карта переезжает по частям

Слоты кончились - карте нужно больше места. Наивное решение: выделить массив вдвое больше и переложить туда все записи. Для карты на гигабайт это значит, что одна вставка из миллиона копирует гигабайт, и попадает она в тот запрос, которому не повезло. То есть в p99.

Go так не делает. Большая карта разбита на независимые таблицы не больше 1024 записей каждая, и старшие биты хеша выбирают таблицу. Число используемых битов растёт вместе с числом таблиц - это extendible hashing.

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

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

Маленькая карта, до 8 записей, - это вообще одна группа без всякой обвязки.

m := make(map[string]int)
// внутри: одна группа на 8 слотов
// девятая запись - появляется полноценная таблица
// больше 1024 записей в таблице - она делится на две независимые
<?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 несколько раз (степенями двойки).
import sys

m: dict[str, int] = {}
# внутри: таблица на 8 слотов (PyDict_MINSIZE), тоже открытая адресация,
# но без групп по 8 с control word. Плюс отдельный компактный массив записей
# в порядке вставки - поэтому обход dict упорядочен.
# Заполняется на 2/3 (шестая запись) - таблица целиком удваивается,
# как минимум до 16 слотов; потом 32 на 11-й, 64 на 22-й записи.
# Разбиения на независимые таблицы по 1024 записи нет: гигабайтный dict
# при росте перекладывается за одну вставку. Подсказки размера тоже нет.

# Рост можно увидеть по размеру объекта:
prev = sys.getsizeof(m)
for i in range(40):
    m[f"user:{i}"] = i
    size = sys.getsizeof(m)
    if size != prev:
        print(f"len={len(m):2d} size={size}")  # скачки на 1, 6, 11, 22 записях
        prev = size

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

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

ℹ️ Пока достаточно знать: горутины и мьютекс

Дальше в уроке встречаются горутины и sync.RWMutex. Горутина - это функция, запущенная словом go и работающая одновременно с остальным кодом (урок о горутинах). Мьютекс (sync.Mutex) - замок: пока одна горутина держит его через Lock, другие ждут. sync.RWMutex - его вариант, который пускает много читателей сразу (RLock), но писателя - только одного. Подробно - в уроке Пакет sync; для этого урока хватит сказанного.

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. Но проверка best-effort: она срабатывает, только если поймала запись «в моменте», и гонка может пройти незамеченной, тихо испортив данные. Надёжно такие ошибки находит race detector (go test -race).

<?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 (распределённое).

import threading

m: dict[str, int] = {}

# Аналог горутин здесь - threading (общая память, как и в Go).
# Детектора гонок у dict нет, и программа не упадёт:
# одна запись m[k] = v под GIL выполняется целиком.
threading.Thread(target=lambda: m.__setitem__("a", 1)).start()
threading.Thread(target=lambda: m.__setitem__("b", 2)).start()

# Но безопасность на уровне одной операции - не атомарность сценария.
# m["hits"] += 1 - это чтение, сложение и запись: три операции,
# между которыми поток могут вытеснить. Потерянные инкременты гарантированы.
lock = threading.Lock()


def hit() -> None:
    with lock:  # составные операции над dict - только под Lock
        m["hits"] = m.get("hits", 0) + 1

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

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";
}
# dict сохраняет порядок вставки (гарантия языка с 3.7), так что
# "случайного порядка" нет - но порядок вставки не равен сортированному.
# Если нужен сортированный обход - sorted() по ключам, как и в Go:
for k in sorted(m):
    print(k, m[k])

# А вот set и frozenset порядок не гарантируют: обход идёт по слотам таблицы.
# Для строк он к тому же меняется от запуска к запуску - хеш рандомизирован.

В 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();
        }
    }
}
import threading


class SafeMap:
    # В stdlib нет RWMutex - только Lock и RLock (реентерабельный,
    # не «читательский»). Разделение читателей и писателей пишут руками
    # или берут из сторонних пакетов (readerwriterlock).
    def __init__(self) -> None:
        self._lock = threading.Lock()
        self._m: dict[str, int] = {}

    def get(self, k: str) -> int | None:
        with self._lock:
            return self._m.get(k)  # None вместо (0, false)

    def set(self, k: str, v: int) -> None:
        with self._lock:
            self._m[k] = v

Одиночные get/set под GIL и так не рвут dict, поэтому класс кажется лишним. Нужен он ради составных операций (прочитал, посчитал, записал) и ради инварианта «все обращения через один замок»: как только появится increment, место для него уже есть.

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. Разные горутины работают с разными ключами без пересечения.

До Go 1.24 внутри было два уровня хранилища (read без локов и dirty под локом), и запись новых ключей была дорогой. С Go 1.24 sync.Map построена на конкурентном hash-trie: записи в разные ключи почти не мешают друг другу. Но API остаётся нетипизированным (any), поэтому для большинства задач по-прежнему проще 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 PX для распределённой блокировки (мьютекса), WATCH/MULTI/EXEC для оптимистичной.
  • 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) // ключа нет - delete просто ничего не делает, без panic
}

struct{} как значение имеет размер 0 (unsafe.Sizeof(struct{}{}) == 0), тогда как bool - 1 байт. Но в map это почти никогда не экономит память: слот хранит ключ и значение вместе и выравнивается по ключу, поэтому для ключей int64, int32 или string слот map[K]bool и map[K]struct{} одинакового размера. Замер на миллионе ключей в Go 1.24 показывает одинаковый расход памяти для обоих вариантов.

Главный смысл идиомы map[string]struct{} - явно сказать читателю «важно только наличие ключа» и не оставить места для значения false, которое пришлось бы как-то трактовать. Сама запись в map при этом стоит заметно больше одного байта: ключ, control-байт с h2, выравнивание слота и запас свободных слотов (таблица растёт, когда заполнится примерно на 7/8).

<?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
# Идиома map[string]struct{} не нужна: set - встроенный тип.
# Внутри это та же хеш-таблица, что у dict, но слот хранит только хеш
# и указатель на ключ - поля под значение нет вовсе, экономить нечего.
tags: set[str] = set()

tags.add("alice")          # Add
"alice" in tags            # Has - в среднем O(1)
tags.discard("alice")      # Remove; в отличие от remove() не бросает KeyError

# Что отличается: set, как и dict, требует хешируемых элементов
# (строки, числа, кортежи, frozen dataclass), а list и dict в него не положить.
# Если нужен неизменяемый набор (ключ другого dict, константа) - frozenset.

В 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;
# Подсказки размера у dict нет: ни в конструкторе, ни отдельным методом.
# Любой способ построить словарь на 10000 записей пройдёт через
# десяток удвоений таблицы (8 -> 16 -> ... -> 16384):
m: dict[str, int] = {}
for i in range(10000):
    m[f"user:{i}"] = i

# То же самое, но одной строкой - и с теми же удвоениями внутри:
m = {f"user:{i}": i for i in range(10000)}

# Что остаётся: строить словарь один раз и не пересоздавать его в горячем цикле,
# а если ключи - плотные целые 0..N-1, брать не dict, а list:
counters = [0] * 10000  # одна аллокация, индекс вместо хеша
counters[42] = 1

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

Насколько это выгодно на ваших данных - вопрос к замеру, а не к статье. Минимальный бенчмарк (положи в файл map_test.go и запусти go test -bench . -benchmem):

package bench

import (
    "strconv"
    "testing"
)

const n = 10000

func BenchmarkMapGrowth(b *testing.B) {
    keys := make([]string, n)
    for i := range keys {
        keys[i] = "user:" + strconv.Itoa(i)
    }

    b.Run("prealloc", func(b *testing.B) {
        b.ReportAllocs()
        for range b.N {
            m := make(map[string]int, n)
            for i, k := range keys {
                m[k] = i
            }
        }
    })

    b.Run("no_prealloc", func(b *testing.B) {
        b.ReportAllocs()
        for range b.N {
            m := make(map[string]int)
            for i, k := range keys {
                m[k] = i
            }
        }
    })
}

Смотри на колонки B/op и allocs/op: без предаллокации их заметно больше, потому что таблица несколько раз растёт и копирует записи.

Ключи 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)); // OutOfBoundsException: другой экземпляр - другой ключ,
// если Point не реализует \Ds\Hashable (методы hash() и equals())

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

from dataclasses import dataclass


# Ключом может быть любой хешируемый объект: тот, у кого согласованы
# __hash__ и __eq__. frozen=True даёт dataclass оба метода по полям -
# это и есть аналог comparable-структуры.
@dataclass(frozen=True)
class Point:
    x: int
    y: int


visited: dict[Point, bool] = {}
visited[Point(1, 2)] = True
visited[Point(1, 2)]  # True - равенство по значению, а не по identity

# НЕ могут быть ключами: list, dict, set, обычный (не frozen) dataclass -
# у них __hash__ = None. Но это не ошибка компиляции, а TypeError
# в рантайме, в момент visited[[1, 2]] = True: "unhashable type: 'list'".
# Вместо списка - tuple, вместо set - frozenset.

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

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

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 - разные ключи
# Третий вариант поведения: ключи считаются одинаковыми, если равны
# по __eq__ и совпали по __hash__. У чисел это так между типами:
# 1 == 1.0 == True, и хеши у них специально согласованы.
m: dict[object, str] = {}
m[1] = "int"
m[1.0] = "float"  # перезапишет m[1]
m[True] = "bool"  # перезапишет m[1]
m["1"] = "str"    # а строка - отдельный ключ, приведения типов нет
print(m)  # {1: 'bool', '1': 'str'}

# Ключ при этом хранится тот, что был вставлен первым (int 1),
# а значение - последнее. Ловушка Go «int32 и int64 - разные ключи»
# здесь невозможна: типов чисел с разной шириной в языке просто нет.

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

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

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; // ошибки нет: null молча превращается в ['x' => 1]
// (для false такое автосоздание deprecated с PHP 8.1; strict_types тут ни при чём)

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

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

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

# «nil map» нет: есть None, и с ним не работает ни чтение, ни запись
m: dict[str, int] | None = None
# m["x"]      -> TypeError: 'NoneType' object is not subscriptable
# m["x"] = 1  -> TypeError: 'NoneType' object does not support item assignment

# Идиоматично - инициализировать пустым dict:
m = {}
m["x"] = 1  # OK

# Зато чтение отсутствующего ключа - не нулевое значение, как в Go,
# а KeyError. Это ловушка в обратную сторону: Go молча вернёт 0,
# а здесь упадёт.
# v = m["nope"]  -> KeyError: 'nope'

# Безопасные паттерны:
v = m.get("nope", 0)          # 0, без исключения

freq: defaultdict[str, int] = defaultdict(int)
freq["word"] += 1             # отсутствующий ключ создаётся с int() == 0

counts = Counter(["a", "b", "a"])
counts["a"]                   # 2
counts["zzz"]                 # 0 - Counter вернёт 0 и не создаст ключ

В 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];
# Не UB, а гарантированное исключение: итератор dict следит за размером
# таблицы и при добавлении или удалении ключа бросает
# RuntimeError: dictionary changed size during iteration.
for k in m:
    if cond(k):
        m[new_key()] = 0  # RuntimeError на следующем шаге цикла

# Идиома 1 - итерироваться по снимку ключей, менять оригинал:
for k in list(m):
    if cond(k):
        m[new_key()] = 0

# Идиома 2 - собрать изменения и применить после, как в Go:
additions = {new_key(): 0 for k in m if cond(k)}
m.update(additions)

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

Go разрешает и удалять, и добавлять ключи во время range: программа не сломается. Но запись, добавленная во время обхода, может попасть в этот же обход, а может быть пропущена. Чтобы результат был предсказуемым, собирай новые ключи в отдельный slice и добавляй после цикла.

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

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

// FIX: хранить указатели
m2 := map[string]*LargeStruct{"x": {}}
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; // работает напрямую
from dataclasses import dataclass, replace


# dict хранит не значения, а указатели на объекты - как map[string]*T в Go.
# Поэтому «копии при чтении» нет: v - тот же объект, что лежит в словаре.
@dataclass
class LargeData:
    field: int = 0


m = {"x": LargeData()}
v = m["x"]
v.field = 1  # изменяет объект в m["x"]


# Ловушка возвращается с неизменяемыми значениями: tuple, frozen dataclass,
# int, str. Их нельзя поменять на месте - только собрать новое и положить обратно.
@dataclass(frozen=True)
class FrozenData:
    field: int = 0


m2 = {"x": FrozenData()}
# m2["x"].field = 1  -> FrozenInstanceError
m2["x"] = replace(m2["x"], field=1)  # новое значение под тем же ключом

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

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