Хеш-таблицы: устройство и разрешение коллизий

Как работает хеш-таблица, требования к хеш-функции, разрешение коллизий методом цепочек и открытой адресацией, коэффициент заполнения, рехеширование, сравнение с деревом.

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

  индекс = hash(ключ) mod размер_таблицы

Сложность операций:
  в среднем         вставка, поиск, удаление — O(1)
  в худшем случае   O(n), когда все ключи попали в одну ячейку

Память: O(n), но с запасом — таблицу держат заполненной не полностью.

Требования к хеш-функции

• Детерминированность: одинаковый ключ всегда даёт одинаковый хеш.
• Равномерность: значения распределяются по таблице без сгущений.
• Быстрота: вычисление должно быть дешевле, чем выигрыш от быстрого поиска.
• Чувствительность: изменение одного символа ключа должно менять хеш существенно.
• Согласованность с равенством: равные объекты обязаны иметь равные хеши. Обратное не требуется.

def hash_djb2(s: str) -> int:
    """Классическая функция Бернштейна: множитель 33 даёт хорошее рассеивание."""
    h = 5381
    for ch in s:
        h = (h * 33 + ord(ch)) & 0xFFFFFFFF
    return h

def hash_bad(s: str) -> int:
    """Плохая функция: сумма кодов. Анаграммы дают один хеш."""
    return sum(ord(c) for c in s)

print(hash_bad('abc'), hash_bad('cba'))    # одинаково — коллизия гарантирована
print(hash_djb2('abc'), hash_djb2('cba'))  # разные значения

Метод цепочек

class HashTable:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)      # обновление
                return
        bucket.append((key, value))
        self.size += 1
        if self.size / self.capacity > 0.75:  # порог заполнения
            self._rehash()

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        return default

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _rehash(self):
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)                # индексы пересчитываются заново

Открытая адресация

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

  Линейное:      i = (h + k) mod m
     просто, но образуются длинные занятые участки — кластеризация

  Квадратичное:  i = (h + k²) mod m
     кластеризация меньше, но обходятся не все ячейки

  Двойное хеширование: i = (h₁ + k·h₂) mod m
     лучшее распределение, h₂ не должно давать ноль

Коэффициент заполнения

  α = число_элементов / размер_таблицы

Среднее число сравнений при поиске:
  метод цепочек:        1 + α/2
  линейное пробирование: (1 + 1/(1−α)²)/2

При α = 0,9 линейное пробирование даёт около 50 сравнений,
метод цепочек — менее двух. Отсюда жёсткий порог рехеширования.

Что выбрать под задачу

Типовые применения

• Подсчёт частот: словарь «слово → количество» вместо вложенных циклов даёт O(n) вместо O(n²).
• Устранение дубликатов: множество на основе хеш-таблицы за один проход.
• Кэширование результатов: мемоизация рекурсивных вычислений.
• Индексы в базах данных для поиска по точному равенству.
• Проверка целостности файлов криптографическими хешами — SHA-256, где к функции добавляется требование необратимости.

from collections import Counter, defaultdict

text = 'алгоритм анализ алгоритм структура анализ алгоритм'
freq = Counter(text.split())
print(freq.most_common(2))     # [('алгоритм', 3), ('анализ', 2)]

# Группировка анаграмм: ключ — отсортированные буквы
groups = defaultdict(list)
for word in ['кот', 'ток', 'дом', 'мод', 'окт']:
    groups[''.join(sorted(word))].append(word)
print(list(groups.values()))

Что показать в курсовой

1. Реализовать таблицу обоими методами разрешения коллизий.
2. Сравнить число коллизий для хорошей и плохой хеш-функции на одинаковых данных.
3. Построить график зависимости среднего числа сравнений от коэффициента заполнения.
4. Замерить время поиска в хеш-таблице и в списке на 10, 1000 и 100 000 элементах.
5. Показать эффект рехеширования: провал производительности в момент перестроения.