Неделя 8

Семинар. Хеш-таблицы

скачать .ipynb

Семинар 8. Хеш-таблицы

Лекция 8 дала class HashTable с цепочками, хеш-функции, коэффициент заполнения и идею открытой адресации. dict и set введены как эталон интерфейса — после лекции ими можно пользоваться.

Здесь вы сначала собираете таблицу сами и исследуете, где её цена перестаёт быть $O(1)$, а потом решаете задачи, в которых словарь — это и есть ответ.

Договор пары. В блоках 1–3 таблицу собираем руками: dict и set стоят только в проверках как эталон. В контесте наоборот — dict и set готовый инструмент, решения пишутся ими.

Ноутбук — тетрадь пары. Его семинаристу не отправляйте. Зачёт пары — прорешанность задач контеста на algo.ai.msu.ru.

Заглушки возвращают неверный ответ — так и задумано, их надо переписать.

Как устроен ноутбук

Как на семинарах 1–7: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb. Отдельного файла тестов на этой неделе нет: проверка встроена в ноутбук, зачёт — контест на платформе.

Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.

Порядок работы

  • инструменты проверки: check_hash_table;
  • 1. своя class HashTable цепочками;
  • 2. исследование: распределение, плохие хеши, рост, худший случай;
  • 3. частоты и пара с суммой $k$;
  • 4. сопоставление с dict / set и «когда словарь»;
  • 5. открытая адресация — идея;
  • контест на algo.ai.msu.ru.

Блоки 1–3 — основная часть пары. Блок 5 — только идея, кода нет.

Инструменты проверки

Функция уже написана, менять её не нужно. check_hash_table гоняет вашу таблицу на случайных последовательностях put / get / contains / remove и сверяет результат со встроенным dict.

dict стоит внутри проверки, а не внутри решения: это эталон интерфейса с лекции. Сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет.

In [ ]:
import random


def check_hash_table(HashTable, trials=200, seed=0):
    """Проверяет таблицу на случайных операциях против dict-эталона.

    seed фиксирован, поэтому неудача воспроизводится.
    """
    rng = random.Random(seed)
    for _ in range(trials):
        t = HashTable(4, hash_fn=hash)   # малая ёмкость — проверим рост
        model = {}
        for _ in range(rng.randint(0, 30)):
            k = f"k{rng.randint(0, 15)}"
            v = rng.randint(-100, 100)
            t.put(k, v)
            model[k] = v
            if len(t) != len(model):
                print("len расходится:", len(t), len(model))
                return False
            if t.get(k) != model[k] or not t.contains(k):
                print("get/contains расходится для", k)
                return False
        for _ in range(30):
            k = f"k{rng.randint(0, 15)}"
            if rng.random() < 0.5:
                v = rng.randint(-100, 100)
                t.put(k, v)
                model[k] = v
            else:
                try:
                    t.remove(k)
                    if k not in model:
                        print("remove не поднял KeyError для", k)
                        return False
                    del model[k]
                except KeyError:
                    if k in model:
                        print("remove поднял KeyError, хотя ключ есть:", k)
                        return False
            if len(t) != len(model):
                print("len расходится после операции")
                return False
        for k, v in model.items():
            if t.get(k) != v:
                print("get расходится для", k)
                return False
        missing = "k-999"
        if t.contains(missing):
            print("contains истинно для отсутствующего ключа")
            return False
        try:
            t.get(missing)
        except KeyError:
            pass
        else:
            print("get отсутствующего ключа должен поднимать KeyError")
            return False
        if t.get(missing, "нет") != "нет":
            print("get с default не работает")
            return False
    print(f"ok: таблица прошла {trials} прогонов против dict")
    return True


print("инструменты готовы")

1. Своя class HashTable цепочками

Устройство: массив бакетов, в каждом бакете — список пар (ключ, значение). Ключ попадает в бакет hash_fn(key) % m; если два ключа дали один индекс — это коллизия, и обе пары лежат в одной цепочке.

Инвариант таблицы:

  1. каждый ключ лежит ровно в одном бакете;
  2. бакет ключа — это hash_fn(key) % m;
  3. size — число ключей, а не пар и не бакетов;
  4. после _resize все ключи переложены по новому модулю.

Даны __init__, _index, __len__, __repr__, describe; допишите put, get, contains, remove, _resize. _MISSING — служебная метка, чтобы отличить «default не передан» от default=None.

Внутри храните пары (key, value), а не одно значение: при обновлении ключа пару надо заменить целиком.

In [ ]:
_MISSING = object()


class HashTable:
    LOAD_LIMIT = 0.75

    def __init__(self, capacity=8, hash_fn=hash):
        self.data = [[] for _ in range(capacity)]
        self.size = 0
        self.hash_fn = hash_fn

    def _index(self, key):
        return self.hash_fn(key) % len(self.data)

    def put(self, key, value):
        """Вставить пару; если ключ уже есть — обновить значение."""
        return None

    def get(self, key, default=_MISSING):
        """Значение по ключу; для отсутствующего — KeyError или default."""
        if default is not _MISSING:
            return default
        return None

    def contains(self, key):
        """Есть ли ключ."""
        return False

    def remove(self, key):
        """Удалить пару; для отсутствующего ключа — KeyError."""
        return None

    def _resize(self):
        """Удвоить ёмкость и переложить все пары по новому модулю."""
        return None

    def __len__(self):
        return self.size

    def __repr__(self):
        return f"HashTable({len(self.data)} бакетов, {self.size} ключей)"

    def describe(self):
        lengths = [len(bucket) for bucket in self.data]
        used = sum(1 for n in lengths if n)
        print(f"m = {len(lengths):>5}, n = {self.size:>5}, "
              f"alpha = {self.size / len(lengths):.2f}, "
              f"занято {used:>5}, max цепочка = {max(lengths)}")


t = HashTable(8, hash_fn=hash)
for k, v in [("яблоко", 3), ("банан", 5), ("вишня", 7)]:
    t.put(k, v)
t.put("яблоко", 10)                # обновление, а не вторая пара
print(t.get("яблоко"))             # ожидается 10
print(t.contains("вишня"))         # ожидается True
t.remove("банан")
print(t, "| есть банан:", t.contains("банан"))   # ожидается False

check_hash_table(HashTable)

2. Коллизии и коэффициент заполнения: исследование

Это не новый код, а эксперименты на вашей таблице. Сначала — распределение: где «равномерно», а где «свалено в одну цепочку».

hash_str — полиномиальная свёртка с лекции. Она возвращает хеш-код (большое число), а индекс бакета получается отдельно — % m.

In [ ]:
import random

MOD = 2**31 - 1


def hash_str(s, m=MOD):
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % m
    return h


def distribution(hash_fn, words, m):
    """Раскладывает слова по m бакетам; возвращает (занято, максимум)."""
    buckets = [[] for _ in range(m)]
    for w in words:
        buckets[hash_fn(w) % m].append(w)
    lengths = [len(b) for b in buckets]
    used = sum(1 for n in lengths if n)
    return used, max(lengths)


rng = random.Random(0)
words = ["".join(rng.choices("абвгдежзи", k=rng.randint(3, 6))) for _ in range(1000)]

for name, fn in [("полиномиальная", hash_str),
                 ("длина слова", lambda s: len(s)),
                 ("первая буква", lambda s: ord(s[0]))]:
    used, mx = distribution(fn, words, 101)
    print(f"{name:>16}: занято {used:>3} из 101, максимум {mx:>4}")

# Ваш эксперимент: средняя длина цепочки у всех трёх функций одинакова.
# Почему по ней нельзя судить о равномерности? На что смотреть?
In [ ]:
# Рост и коэффициент заполнения: вставьте 20 000 ключей и смотрите describe().
t = HashTable(4, hash_fn=hash_str)
milestones = {1, 10, 100, 1000, 5000, 10000, 20000}
for i in range(1, 20_001):
    t.put(f"key-{i}", i)
    if t.size in milestones:
        t.describe()

# Ваш эксперимент: что происходит с alpha сразу после _resize и прямо перед ним?
# Почему максимальная цепочка при 20 000 ключей — единицы, а не сотни?
In [ ]:
# Худший случай: все ключи кратны ёмкости m. Для целых hash(x) == x, поэтому
# при m = 1024 (степень двойки) все такие ключи окажутся в одном бакете.
worst = HashTable(1024, hash_fn=hash)
for k in range(0, 512_000, 1024):
    worst.put(k, k)
worst.describe()          # alpha ~0.5, но max цепочка — 500
print("поиск отсутствующего:", worst.contains(-1024))   # тот же бакет, ключа нет

# Ваш эксперимент: замените 1024 на 1021 (простое) и повторите вставку
# ключей, кратных 1024. Что изменилось и почему?

3. Частоты и пара с суммой $k$

Два приёма, которые и есть «словарь в бою». Сначала частоты — на своей таблице, затем на встроенном dict: это один и тот же код, только готовым инструментом.

In [ ]:
text = "абракадабра"

# на своей таблице
t = HashTable(hash_fn=hash_str)
for ch in text:
    t.put(ch, t.get(ch, 0) + 1)

# на встроенном dict — тот же приём
freq = {}
for ch in text:
    freq[ch] = freq.get(ch, 0) + 1

print("своя таблица:", [(ch, t.get(ch)) for ch in "абркд"])
print("dict:        ", freq)

# Ваш эксперимент: почему выгоднее один проход с get(x, 0) + 1,
# чем собрать все элементы, а потом считать каждый отдельно?

Пара с суммой $k$. Не сортируем: проходим один раз и для каждого $x$ спрашиваем, встречалось ли уже дополнение $k - x$. Это $O(n)$ в среднем против $O(n\log n)$ у «отсортировать + два указателя».

In [ ]:
def pair_sum(a, k):
    """Есть ли пара элементов с суммой k? Ожидаемое время O(n)."""
    seen = set()
    for x in a:
        if k - x in seen:
            return True
        seen.add(x)
    return False


print(pair_sum([1, 2, 3, 4], 5))   # True: 1 + 4
print(pair_sum([1, 2, 3, 4], 10))  # False
print(pair_sum([3, 3], 6))         # True: 3 + 3

# Ваш эксперимент: перепишите pair_sum так, чтобы она возвращала ИНДЕКСЫ
# пары. Почему set уже недостаточно и нужен dict (значение -> индекс)?
# Это мост к задаче № 3 (Two Sum).

4. Сопоставление с dict / set и «когда словарь»

Один и тот же приём — три инструмента, и выбрать надо по условию:

НужноИнструмент
только «видели раньше»set
счётчики, ключ → значениеdict
ключ — маленькое целоемассив (частотный массив)
порядок ключейsorted
минимум/максимум по приоритетукуча (неделя 9)

Если вы писали на C++ в школе: dict — это unordered_map, set — unordered_set. В курсе пишем на Python, так что это только для узнавания.

In [ ]:
xs = [3, 1, 2, 3, 2]

s = set(xs)                       # принадлежность
print("set:", s, "| 2 in s:", 2 in s)

c = {}
for x in xs:                      # счётчик
    c[x] = c.get(x, 0) + 1
print("dict:", c)

freq = [0] * 4                    # ключи 0..3 — частотный массив
for x in xs:
    freq[x] += 1
print("массив:", freq)

# Ваш эксперимент: какой инструмент для значений от 0 до 10^6? Для строк-ключей?
# Когда словарь хуже массива и почему?

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

Без кода — картинка с лекции. Ячейка h(key) % m занята → идём дальше (h(key) + i) % m; так образуются кластеры. Удаление — ловушка: просто очистить ячейку нельзя, нужен tombstone.

Почему это относится к «когда словарь»: открытая адресация компактнее и лучше по локальности, поэтому так устроен dict в Python. Но в задачах это деталь реализации, а не то, что вы пишете сами.

Контест

Задачи сдавайте в контест недели 8 на algo.ai.msu.ru. Номера LeetCode помогают найти условие.

Для зачёта семинара обязательны № 3 (1. Two Sum) и № 4 (49. Group Anagrams). Разминка и звёздочка их не заменяют.

№ЗадачаСтатусСигнал «нужен словарь»
1217. Contains DuplicateРазминка«видели раньше» → set
2242. Valid AnagramРазминка«частоты» → dict
31. Two SumОбязательная«дополнение до суммы» + индексы → dict
449. Group AnagramsОбязательная«канонический ключ → группа» → dict списков
5128. Longest Consecutive Sequence ★Звёздочка«членство за $O(1)$» → set

Порядок работы. Разминку № 1–2 закрывайте быстро. Главная — № 3: там сортировка ломает исходные индексы, а dict хранит значение → индекс. Дальше № 4. № 5 — для тех, кто закрыл № 3–4.

Типичный WA: в № 3 сортируют массив и возвращают индексы переставленного массива; в № 4 используют list как ключ (он нехешируем — берите tuple); в № 5 считают последовательность заново для каждого элемента ($O(n^2)$).

Про словарь и сортировку. В № 1 и № 2 можно отсортировать, и это пройдёт тесты, но на паре просим решение за ожидаемое $O(n)$: именно оно показывает, зачем словарь. Тестер это не проверяет, поэтому спрашиваем у доски.

Шпаргалка: когда нужен словарь

Сигналы «нужен dict / set»:

  • «видели раньше», удаление дубликатов → set;
  • частоты → dict (d[x] = d.get(x, 0) + 1);
  • дополнение до суммы $k$ → dict / set за один проход;
  • ключ → что-то (группа, индекс, каноническая форма, кэш) → dict;
  • доступ по произвольному ключу за $O(1)$.

Когда НЕ словарь:

  • ключ — маленькое целое → массив (частотный массив недели 2);
  • порядок ключей → сортировка;
  • приоритет → куча (неделя 9);
  • позиция → список.

Плата. Память $\Theta(n+m)$; $O(1)$ только в среднем, худший случай $\Theta(n)$.

Своя таблица и её проверка:

  • бакет — список пар, индекс hash_fn(key) % m;
  • put обновляет, а не добавляет вторую пару; _resize перекладывает по новому модулю;
  • «$O(1)$ в среднем» — предположение о равномерном хеше; подбор ключей даёт $\Theta(n)$.

Сдача

  • Этот .ipynb семинаристу отправлять не нужно.
  • Для зачёта выполните № 3 — 1. Two Sum и № 4 — 49. Group Anagrams в контесте на algo.ai.msu.ru.
  • Разминка № 1–2 и звёздочка № 5 — по желанию, для зачёта не требуются.
  • Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.
  • Хеш-функция, коллизии и среднее против наихудшего входят в коллоквиум 2.