Как устроены словарь и хеш-таблица?

Словарь хранит пары ключ–значение и поддерживает поиск по ключу. Хеш-таблица реализует этот интерфейс, преобразуя ключ в индекс корзины. При хорошем распределении операции выполняются за ожидаемое O(1), но совпадения индексов неизбежны и требуют корректной обработки коллизий.

Хеш-функция

Она должна всегда давать одинаковый результат для равных ключей и достаточно равномерно распределять типичные данные. Равенство ключей обязательно влечёт равенство хешей, обратное неверно. Изменяемый ключ опасен: после изменения его новая корзина не совпадёт с местом хранения.

Коллизии

В цепочках каждая корзина содержит список пар с одинаковым индексом. В открытой адресации при занятой позиции проверяют последовательность других ячеек. Удаление там требует специальной метки, иначе поиск может преждевременно остановиться на образовавшемся пустом месте.

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

Чем плотнее таблица, тем больше коллизий и проб. При достижении порога создают больший массив и заново размещают элементы по новым индексам. Перестройка дорога, но редка, поэтому средняя стоимость серии вставок остаётся близкой к постоянной.

Словарь частот

При подсчёте слов ключом служит нормализованное слово, значением — количество появлений. На каждом шаге читают прежний счётчик или ноль и увеличивают его. Итоговый порядок обхода ключей не следует считать отсортированным, если контракт конкретного языка этого не гарантирует.

Надёжный анализ

Разберите ключи с одинаковым хешем, повторную вставку существующего ключа, удаление и последующий поиск. В оценке называйте ожидаемый и худший случаи: специально подобранные коллизии способны превратить операции в O(n). Интерфейс словаря и механизм хеширования следует различать.

Частотный словарь как практический контракт

Хеш-таблица скрыта за словарём Python, но требования остаются видимыми: ключ должен иметь согласованные равенство и хеш, а средняя O(1) не является гарантией худшего случая. Нормализация текста определяет, какие слова считаются одинаковыми.

from collections import Counter

def word_frequencies(text: str) -> dict[str, int]:
    words = [
        token.casefold().strip(".,!?;:")
        for token in text.split()
    ]
    return dict(Counter(word for word in words if word))

assert word_frequencies("Код, код! Тест.") == {"код": 2, "тест": 1}

Простой split не является универсальным токенизатором: дефисы, кавычки и Unicode требуют заранее выбранного правила. Корректность результата зависит от этого правила не меньше, чем от структуры данных.

Практика: собственная таблица с цепочками

Реализуйте небольшую хеш-таблицу целых ключей с массивом корзин и цепочками. Поддержите вставку с заменой значения, поиск и удаление. Создайте ключи, специально попадающие в одну корзину, и проверьте все операции после коллизий. Измерьте длины цепочек при разных коэффициентах заполнения. Затем добавьте расширение массива и объясните, почему элементы нужно хешировать заново, а не просто копировать корзины по прежним индексам.