Устройство map †
«ФинГуру» докачал десять миллионов файлов, и поиск по индексу стал проседать. Сергей принёс жалобу клиента на планёрку, и Миша из любопытства заглянул внутрь индекса filesByID.
внутри карта — хеш-таблица Swiss Tables: группы по 8 слотов с control-байтами, рост при load factor 7/8 через rehash (Go 1.24+).
Группы по восемь слотов
Внутренне карта — хеш-таблица Swiss Tables. Хранение поделено на группы по восемь слотов; у каждого слота есть control-байт — младшие 7 бит хеша ключа (H2).
При поиске ключ хешируется: старшие биты хеша (H1) выбирают группу, а H2 одной быстрой проверкой сравнивается с control-байтами всех слотов группы. Совпал H2 — проверяется полное равенство ключа. Поэтому поиск — это O(1): один хеш и одна проверка группы.
Рост при load factor 7/8
Когда таблица заполняется в среднем больше чем на 7 из 8 слотов (load factor 7/8), карта растёт: rehash в таблицу вдвое большего размера. Большая карта — это несколько таблиц (extendible hashing), и рост затрагивает только одну таблицу за раз, а не все данные. Поэтому рост не даёт одной гигантской паузы, а размазывается по мере наполнения.
Стабильна форма, а не детали
Числа в этом разделе — восемь слотов, порог 7/8 — детали текущего runtime. Стабильна форма: хеш-таблица с control-байтами и амортизированным ростом. Отсюда и порядок итерации из прошлого урока: элементы лежат по хешу, а не в порядке вставки, поэтому «порядок» — искусственное понятие.
Вы узнаете:
- как карта была устроена до Go 1.24
- как load factor влияет на производительность поиска
Проверьте себя
Что хранит control-байт слота в Swiss Tables?
Почему рост карты на миллионах файлов не даёт одной гигантской паузы?
Почему map с одними и теми же ключами обходится в разном порядке?
На что можно опираться в коде из устройства карты?
правильных ответов
Карта — хеш-таблица Swiss Tables: группы по 8 слотов с control-байтами, рост при load factor 7/8 через rehash. Детали — реализация, форма стабильна.
10 000 ₽ · 60 минут · онлайн