Хеш-функции и разрешение коллизий

Что такое хеш-функция

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

h(key) → [0, capacity)

Для строк часто используют полиномиальный хеш:

func hashString(s string, cap int) int {
    h := 0
    for _, c := range s {
        h = (h*31 + int(c)) % cap
    }
    return h
}

Коллизии

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

Метод цепочек (Separate Chaining)

Каждая ячейка хранит связный список элементов с одинаковым хешем.

type HashTable struct {
    buckets [][]entry
    size    int
}
type entry struct{ key string; val int }

func (h *HashTable) Set(key string, val int) {
    i := hashString(key, len(h.buckets))
    for j, e := range h.buckets[i] {
        if e.key == key { h.buckets[i][j].val = val; return }
    }
    h.buckets[i] = append(h.buckets[i], entry{key, val})
    h.size++
}

Средняя сложность поиска: O(1 + α), где α = n/capacity — коэффициент загрузки.

Открытая адресация (Open Addressing)

При коллизии ищет следующую свободную ячейку. Три стратегии пробирования:

• Линейное: h(k, i) = (h(k) + i) mod m — кластеризация.
• Квадратичное: h(k, i) = (h(k) + i²) mod m — меньше кластеров.
• Двойное хеширование: h(k, i) = (h1(k) + i·h2(k)) mod m — лучшее распределение.

Коэффициент загрузки

При α > 0.7 производительность падает — нужно перехеширование (rehash): создать таблицу вдвое больше, вставить все элементы заново. Стоимость — O(n) разово.

Упражнения