Хеш-таблица изнутри: коллизии, бакеты и цена 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: карта переезжает по частям |
Как работает хеш-таблица
Ключ прогоняется через хеш-функцию - получается число. Старшие биты этого числа выбирают, где искать, младшие помогают быстро отсеять чужие ключи.
Группы по 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 ~миллисекунды, а не наносекунды 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 оптимизирован под два сценария:
- Ключ пишется один раз, читается много раз (например, кеш конфигурации).
- Разные горутины работают с разными ключами без пересечения.
До 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"] - потому что рост карты может перенести значение в памяти.
- Concurrency - sync: мьютексы, пулы и sync.Map - потокобезопасная альтернатива map: когда нужна sync.Map и сравнение с RWMutex+map