Hash table

Определение#

Хеш-таблица (Hash Table) — это структура данных, которая хранит пары ключ → значение и обеспечивает быстрый доступ к элементам по ключу за счёт вычисления хеша и индекса в массиве.

Как она работает#

Хеш-функция берёт ключ (например, "apple") и превращает его в число, по которому выбирается индекс внутри массива бакетов (ячеек).

Схема:

Вычисляем hash(key)
Превращаем хеш в индекс массива: index = hash(key) % size
В ячейке index храним (или находим) значение

Если разные ключи дали один и тот же индекс, возникает collision (коллизия), и её нужно разрешать (иначе непонятно, где хранить данные).

Коллизии#

Коллизия — ситуация, когда разные ключи попадают в один и тот же индекс.

Основные способы разрешения коллизий:

Chaining (цепочки): в одной ячейке хранится список/цепочка элементов.
Open Addressing (открытая адресация): при коллизии ищется другая свободная ячейка по правилу «пробирования».

Способ	Идея	Пример
Chaining	В бакете хранится коллекция элементов	`bucket[i] = [k1, k2, k3]`
Open Addressing	Элемент кладётся в следующую подходящую свободную ячейку	`i -> i+1 -> i+2 ...`

Когда используют#

Hash Table выбирают, когда нужен быстрый доступ к данным по ключу: поиск, вставка и удаление обычно стремятся к O(1) в среднем.
Она хорошо подходит для кэшей, частотных словарей, индексов, быстрых проверок «есть ли элемент».

Типичный кейс: «по id получить объект» или «посчитать частоты слов».

Хеш-таблица в Python#

В Python основная хеш-структура — это dict (словарь): он хранит пары ключ–значение и реализует быстрый доступ по ключу.

Важно про ключи:

Ключ должен быть хешируемым (hashable), то есть иметь стабильный __hash__() и корректный __eq__().
Обычно ключи — это str, int, tuple (если внутри тоже hashable), frozenset.

Пример#

Частоты слов#

    text = "spam spam eggs spam"
    freq = {}

    for word in text.split():
        freq[word] = freq.get(word, 0) + 1

    print(freq) # {'spam': 3, 'eggs': 1}
    ### Свой ключ (важно: __hash__ + __eq__)
    class UserId:
        def __init__(self, value: int):
            self.value = value
        def __hash__(self):
            return hash(self.value)
        def __eq__(self, other):
            return isinstance(other, UserId) and self.value == other.value

    users = {}
    users[UserId(1)] = "Alice"
    users[UserId(2)] = "Bob"

    print(users[UserId(1)]) # Alice

Ключевые мысли#

Хеш-таблица — это «массив + хеш-функция», который даёт быстрый доступ по ключу.
O(1) работает в среднем, потому что эффективность зависит от коллизий и размера таблицы.
В Python словари — базовый инструмент для задач «по ключу быстро найти значение».