Ответ
В Go map реализован как хеш-таблица. Производительность map напрямую зависит от скорости вычисления хеша ключа. Для очень больших ключей хеширование всей последовательности байт может быть медленным.
Чтобы оптимизировать этот процесс, в Go существует специальная логика для ключей, размер которых превышает 128 байт (maxKeySize в рантайме).
Как это работает:
Хеширование с ограничением: Вместо того чтобы хешировать все байты ключа, Go-рантайм вычисляет хеш, основываясь преимущественно на первых 128 байтах. Это компромисс между скоростью хеширования и качеством хеш-функции.
Хранение полного ключа: Несмотря на урезанное хеширование,
mapвсегда хранит полную, не измененную копию ключа внутри своей структуры (в бакете).Разрешение коллизий:
- Когда вы обращаетесь к
map, рантайм сначала вычисляет хеш ключа, чтобы найти нужный бакет (ячейку хеш-таблицы). - Если два разных ключа (с одинаковыми первыми 128 байтами) попадают в один и тот же бакет (коллизия), Go перебирает элементы в этом бакете.
- Для каждого элемента он сравнивает искомый ключ с сохраненным в бакете полным ключом байт в байт, чтобы найти точное совпадение.
- Когда вы обращаетесь к
Последствия такого подхода:
- Преимущество: Быстрое хеширование для больших ключей.
- Недостаток: Если у вас много ключей, которые различаются только после 128-го байта, все они будут иметь одинаковый хеш. Это приведет к формированию длинных цепочек в одном бакете, что замедлит операции вставки и поиска до уровня линейного сканирования
O(n)внутри этого бакета.
// Ключ размером 256 байт
type BigKey [256]byte
m := make(map[BigKey]int)
key1 := BigKey{1}
key2 := BigKey{1}
// Изменим байт за пределами первых 128
key2[200] = 99
// key1 и key2, скорее всего, будут иметь одинаковый хеш
// и попадут в один бакет, что замедлит доступ при большом
// количестве таких ключей.
m[key1] = 100
m[key2] = 200Эта логика реализована в функции typehash в исходном коде рантайма Go (runtime/alg.go).