Хеш-таблицы

Перед началом: два указателя и скользящее окно (модуль 3). Инструменты: Go 1.27, map, slices, maps. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Тест падал через раз — его перезапускали»

Три месяца команда жила с флакующим тестом: сводка по статусам заказов собиралась как map[string]int, сериализовалась в JSON, а тест сравнивал байты с эталоном. Пока случайный порядок ключей совпадал с эталоном — зелено; в остальные прогоны — красно. Раз «иногда проходит», дежурные выработали ритуал: перезапустить пайплайн и не читать дифф.

Причина — в контракте языка: порядок обхода map в Go случаен по замыслу, итерация перемешивается между запусками. Тест сравнивал не данные, а случайность. Тот же дефект жил и в проде: отчёт для клиента печатался прямо из обхода map, и строки «прыгали» при каждом обновлении страницы — саппорт не мог сверить скриншот с предыдущим.

В модуле разберём хеш-таблицы до дна: хеш-функцию, коллизии, load factor, свою таблицу с цепочками и рехешированием — и сверим с map, чтобы случайный порядок итерации перестал быть сюрпризом.

📖 Теория

4.1 Хеш-функция, коллизии, load factor

Хеш-таблица превращает ключ в индекс бакета через хеш-функцию. Хорошая хеш-функция детерминирована, равномерно разбрасывает ключи и дешева. Если два ключа попали в один индекс — это коллизия; от неё защищаются цепочками (список на бакет) или открытой адресацией. Третья метрика — load factor: отношение записей к бакетам; при 0.75 таблица растёт, иначе цепочки удлиняются и поиск деградирует.

go
h := hash("user:42") // детерминирован: один ключ — один хеш
i := h % 4           // индекс бакета; коллизии неизбежны

4.2 Своя таблица: бакеты, цепочки, рехеширование

Запись — узел цепочки, таблица — срез голов этих цепочек. Вставка ищет ключ по цепочке: нашла — обновляет, нет — добавляет узел в голову, предварительно проверив load factor.

go
func (h *HashTable) Put(key string, val int) {
	if h.count+1 > len(h.buckets)*3/4 { // load factor 0.75 — пора расти
		h.rehash()
	}
	i := h.index(key)
	for e := h.buckets[i]; e != nil; e = e.next {
		if e.key == key {
			e.val = val // ключ уже есть — обновляем
			return
		}
	}
	h.buckets[i] = &entry{key: key, val: val, next: h.buckets[i]}
	h.count++
}

Рехеширование удваивает бакеты и раскладывает записи заново: старые индексы после смены размера недействительны. Амортизированно вставка остаётся O(1) — та же логика, что у append из модуля 1.

go
func (h *HashTable) rehash() {
	old := h.buckets
	h.buckets = make([]*entry, len(old)*2)
	h.count = 0
	for _, head := range old {
		for e := head; e != nil; e = e.next {
			h.Put(e.key, e.val) // новый размер — новые бакеты
		}
	}
}

4.3 map в Go: бакеты, порядок, zero value, delete

Внутри map — массив бакетов по 8 слотов, overflow-бакеты для лишних коллизий и случайный seed на каждую map. Отсюда главное правило: порядок обхода не определён и меняется от запуска к запуску. Это не недоделка, а защита от hash flooding: предсказуемый порядок позволил бы подобрать ключи, все попадающие в один бакет.

go
for k := range m {
	fmt.Println(k) // каждый запуск — новый порядок: так задумано
}

Остальное поведение — наизусть:

• отсутствующий ключ возвращает zero value: m["нет"] == 0 неотличимо от честного нуля, различает comma-ok v, ok := m["нет"];
• delete(m, k) — O(1) в среднем и безопасен для отсутствующего ключа;
• ключи должны быть сравнимыми: срез или map в роли ключа — ошибка компиляции;
• запись в nil-map паникует, чтение — нет;
• нужен стабильный порядок — фиксируйте явно: slices.Sorted(maps.Keys(m)).

4.4 Идиомы: сеты, частоты, подписи

Три сценария закрывают большинство задач, где раньше был вложенный цикл.

go
// Сет: значение — пустая структура, она не занимает памяти.
seen := map[string]struct{}{}
seen["x"] = struct{}{}
if _, ok := seen["x"]; ok { /* есть */ }

// Частоты: O(n) вместо O(n²) «каждый с каждым».
counts := make(map[string]int)
for _, w := range words {
	counts[w]++
}

Третий — подпись как ключ: анаграммы группируются по ключу-инварианту (отсортированные буквы), а two-sum в неотсортированном срезе решается за один проход по паре значение → индекс.

4.5 Цена: память и альтернативы

Map — самая дорогая из «постоянных» структур: каждая пара платит за слот бакета, хеш и выравнивание. Для плотного узкого диапазона ключей массив дешевле на порядок:

go
var cnt [26]int // «только латиница»: ~100 байт, ноль аллокаций
for i := 0; i < len(s); i++ {
	if c := s[i]; c >= 'a' && c <= 'z' {
		cnt[c-'a']++
	}
}

Отсортированный срез — компромисс: плотная память и O(log n) на поиск, но вставка O(n) на сдвиг.

4.6 Компромиссы

Правило: map — когда ключи разрежены или неизвестны заранее; массив — когда диапазон плотный и маленький; сортировка ключей — когда результат видит человек или тест. Случайный порядок итерации — часть контракта.

💻 Практика

1. Своя таблица целиком. Реализуйте Put, Get, Delete и рехеширование при 0.75. Тесты: вставка и чтение, обновление ключа, удаление из середины цепочки, рост с 4 до 16 бакетов. Напечатайте раскладку до и после роста: какие ключи переехали и почему.
2. two-sum с индексами. Один проход, тесты: [2,7,11,15], 9 → 0,1; [-3,4,3,90], 0 → 0,2; пары нет; пустой срез. Объясните, почему нельзя сначала сложить все числа в map: что сломается на [3,3] и target 6?
3. Группировка анаграмм. Подпись-ключ плюс детерминированный порядок групп и слов (сортировка). Тесты: пример из сниппета, пустой вход, все слова уникальны.
4. Первый уникальный. firstUnique(s string) (rune, bool): частоты map, затем второй обход. Тесты: "aabbc" → c, "aabb" → false, "😀😀x" → x (руны, не байты).
5. map против массива. Частоты 1 000 000 чисел из 0..999 через map[int]int и через [1000]int. Бенчмарк -benchmem: сравните ns/op, allocs/op, B/op. При какой плотности диапазона массив перестаёт выигрывать?

🧩 Quiz

✅ Итоги модуля

• Хеш-таблица — это хеш-функция, бакеты, коллизии и load factor; при 0.75 таблица удваивается и раскладывается заново.
• Своя таблица с цепочками объясняет, откуда у map O(1) в среднем и сколько он ест памяти.
• Порядок обхода map случаен по замыслу; стабильный вывод задаётся явно — slices.Sorted(maps.Keys(m)).
• Zero value вместо ошибки плюс comma-ok для честной проверки; delete безопасен для отсутствующих ключей.
• Идиомы: сет map[K]struct{}, частоты, подпись как ключ.

🔗 Мостик к Модулю 5

Хеш-таблица — «вещь без порядка»: она отвечает «есть ли ключ», но не «что было последним». Дальше — структуры, где порядок и есть суть: стек, очередь, дек и монотонный стек для задач «следующий больший».