{ "cells": [ { "cell_type": "markdown", "id": "intro", "metadata": {}, "source": [ "# Семинар 8. Хеш-таблицы\n", "\n", "Лекция 8 дала `class HashTable` с цепочками, хеш-функции, коэффициент заполнения и идею открытой адресации. `dict` и `set` введены как эталон интерфейса — после лекции ими можно пользоваться.\n", "\n", "Здесь вы сначала собираете таблицу сами и **исследуете**, где её цена перестаёт быть $O(1)$, а потом решаете задачи, в которых словарь — это и есть ответ.\n", "\n", "**Договор пары.** В блоках 1–3 таблицу собираем руками: `dict` и `set` стоят только в проверках как эталон. В контесте наоборот — `dict` и `set` готовый инструмент, решения пишутся ими.\n", "\n", "Ноутбук — тетрадь пары. **Его семинаристу не отправляйте.** Зачёт пары — прорешанность задач контеста на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n", "\n", "Заглушки возвращают неверный ответ — так и задумано, их надо переписать.\n" ] }, { "cell_type": "markdown", "id": "jupyter", "metadata": {}, "source": [ "## Как устроен ноутбук\n", "\n", "Как на семинарах 1–7: ячейки **Markdown** и **Code**; командный режим — `Esc`, правка — `Enter`; `Shift+Enter` выполняет ячейку.\n", "\n", "Скачайте с сайта курса [этот файл `.ipynb`](https://learn.ai.msu.ru/algo/1/08/seminar.ipynb). Отдельного файла тестов на этой неделе нет: проверка встроена в ноутбук, зачёт — контест на платформе.\n", "\n", "Ячейки с комментарием «Ваш эксперимент» никто автоматически не проверяет.\n" ] }, { "cell_type": "markdown", "id": "roadmap", "metadata": {}, "source": [ "## Порядок работы\n", "\n", "- инструменты проверки: `check_hash_table`;\n", "- **1.** своя `class HashTable` цепочками;\n", "- **2.** исследование: распределение, плохие хеши, рост, худший случай;\n", "- **3.** частоты и пара с суммой $k$;\n", "- **4.** сопоставление с `dict` / `set` и «когда словарь»;\n", "- **5.** открытая адресация — идея;\n", "- контест на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n", "\n", "Блоки 1–3 — основная часть пары. Блок 5 — только идея, кода нет.\n" ] }, { "cell_type": "markdown", "id": "tools_md", "metadata": {}, "source": [ "## Инструменты проверки\n", "\n", "Функция уже написана, менять её не нужно. `check_hash_table` гоняет вашу таблицу на случайных последовательностях `put` / `get` / `contains` / `remove` и сверяет результат со встроенным `dict`.\n", "\n", "`dict` стоит **внутри проверки**, а не внутри решения: это эталон интерфейса с лекции. Сравнивать свой ответ с эталоном — нормальная практика, сдавать эталон вместо решения — нет.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "tools_code", "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "\n", "def check_hash_table(HashTable, trials=200, seed=0):\n", " \"\"\"Проверяет таблицу на случайных операциях против dict-эталона.\n", "\n", " seed фиксирован, поэтому неудача воспроизводится.\n", " \"\"\"\n", " rng = random.Random(seed)\n", " for _ in range(trials):\n", " t = HashTable(4, hash_fn=hash) # малая ёмкость — проверим рост\n", " model = {}\n", " for _ in range(rng.randint(0, 30)):\n", " k = f\"k{rng.randint(0, 15)}\"\n", " v = rng.randint(-100, 100)\n", " t.put(k, v)\n", " model[k] = v\n", " if len(t) != len(model):\n", " print(\"len расходится:\", len(t), len(model))\n", " return False\n", " if t.get(k) != model[k] or not t.contains(k):\n", " print(\"get/contains расходится для\", k)\n", " return False\n", " for _ in range(30):\n", " k = f\"k{rng.randint(0, 15)}\"\n", " if rng.random() < 0.5:\n", " v = rng.randint(-100, 100)\n", " t.put(k, v)\n", " model[k] = v\n", " else:\n", " try:\n", " t.remove(k)\n", " if k not in model:\n", " print(\"remove не поднял KeyError для\", k)\n", " return False\n", " del model[k]\n", " except KeyError:\n", " if k in model:\n", " print(\"remove поднял KeyError, хотя ключ есть:\", k)\n", " return False\n", " if len(t) != len(model):\n", " print(\"len расходится после операции\")\n", " return False\n", " for k, v in model.items():\n", " if t.get(k) != v:\n", " print(\"get расходится для\", k)\n", " return False\n", " missing = \"k-999\"\n", " if t.contains(missing):\n", " print(\"contains истинно для отсутствующего ключа\")\n", " return False\n", " try:\n", " t.get(missing)\n", " except KeyError:\n", " pass\n", " else:\n", " print(\"get отсутствующего ключа должен поднимать KeyError\")\n", " return False\n", " if t.get(missing, \"нет\") != \"нет\":\n", " print(\"get с default не работает\")\n", " return False\n", " print(f\"ok: таблица прошла {trials} прогонов против dict\")\n", " return True\n", "\n", "\n", "print(\"инструменты готовы\")\n" ] }, { "cell_type": "markdown", "id": "ht_md", "metadata": {}, "source": [ "## 1. Своя `class HashTable` цепочками\n", "\n", "Устройство: массив **бакетов**, в каждом бакете — список пар `(ключ, значение)`. Ключ попадает в бакет `hash_fn(key) % m`; если два ключа дали один индекс — это коллизия, и обе пары лежат в одной цепочке.\n", "\n", "**Инвариант таблицы:**\n", "\n", "1. каждый ключ лежит ровно в одном бакете;\n", "2. бакет ключа — это `hash_fn(key) % m`;\n", "3. `size` — число ключей, а не пар и не бакетов;\n", "4. после `_resize` все ключи переложены по новому модулю.\n", "\n", "Даны `__init__`, `_index`, `__len__`, `__repr__`, `describe`; допишите `put`, `get`, `contains`, `remove`, `_resize`. `_MISSING` — служебная метка, чтобы отличить «`default` не передан» от `default=None`.\n", "\n", "Внутри храните пары `(key, value)`, а не одно значение: при обновлении ключа пару надо заменить целиком.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "ht_code", "metadata": {}, "outputs": [], "source": [ "_MISSING = object()\n", "\n", "\n", "class HashTable:\n", " LOAD_LIMIT = 0.75\n", "\n", " def __init__(self, capacity=8, hash_fn=hash):\n", " self.data = [[] for _ in range(capacity)]\n", " self.size = 0\n", " self.hash_fn = hash_fn\n", "\n", " def _index(self, key):\n", " return self.hash_fn(key) % len(self.data)\n", "\n", " def put(self, key, value):\n", " \"\"\"Вставить пару; если ключ уже есть — обновить значение.\"\"\"\n", " return None\n", "\n", " def get(self, key, default=_MISSING):\n", " \"\"\"Значение по ключу; для отсутствующего — KeyError или default.\"\"\"\n", " if default is not _MISSING:\n", " return default\n", " return None\n", "\n", " def contains(self, key):\n", " \"\"\"Есть ли ключ.\"\"\"\n", " return False\n", "\n", " def remove(self, key):\n", " \"\"\"Удалить пару; для отсутствующего ключа — KeyError.\"\"\"\n", " return None\n", "\n", " def _resize(self):\n", " \"\"\"Удвоить ёмкость и переложить все пары по новому модулю.\"\"\"\n", " return None\n", "\n", " def __len__(self):\n", " return self.size\n", "\n", " def __repr__(self):\n", " return f\"HashTable({len(self.data)} бакетов, {self.size} ключей)\"\n", "\n", " def describe(self):\n", " lengths = [len(bucket) for bucket in self.data]\n", " used = sum(1 for n in lengths if n)\n", " print(f\"m = {len(lengths):>5}, n = {self.size:>5}, \"\n", " f\"alpha = {self.size / len(lengths):.2f}, \"\n", " f\"занято {used:>5}, max цепочка = {max(lengths)}\")\n", "\n", "\n", "t = HashTable(8, hash_fn=hash)\n", "for k, v in [(\"яблоко\", 3), (\"банан\", 5), (\"вишня\", 7)]:\n", " t.put(k, v)\n", "t.put(\"яблоко\", 10) # обновление, а не вторая пара\n", "print(t.get(\"яблоко\")) # ожидается 10\n", "print(t.contains(\"вишня\")) # ожидается True\n", "t.remove(\"банан\")\n", "print(t, \"| есть банан:\", t.contains(\"банан\")) # ожидается False\n", "\n", "check_hash_table(HashTable)\n" ] }, { "cell_type": "markdown", "id": "collisions_md", "metadata": {}, "source": [ "## 2. Коллизии и коэффициент заполнения: исследование\n", "\n", "Это не новый код, а эксперименты на вашей таблице. Сначала — распределение: где «равномерно», а где «свалено в одну цепочку».\n", "\n", "`hash_str` — полиномиальная свёртка с лекции. Она возвращает **хеш-код** (большое число), а индекс бакета получается отдельно — `% m`.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "collisions_dist_code", "metadata": {}, "outputs": [], "source": [ "import random\n", "\n", "MOD = 2**31 - 1\n", "\n", "\n", "def hash_str(s, m=MOD):\n", " h = 0\n", " for ch in s:\n", " h = (h * 31 + ord(ch)) % m\n", " return h\n", "\n", "\n", "def distribution(hash_fn, words, m):\n", " \"\"\"Раскладывает слова по m бакетам; возвращает (занято, максимум).\"\"\"\n", " buckets = [[] for _ in range(m)]\n", " for w in words:\n", " buckets[hash_fn(w) % m].append(w)\n", " lengths = [len(b) for b in buckets]\n", " used = sum(1 for n in lengths if n)\n", " return used, max(lengths)\n", "\n", "\n", "rng = random.Random(0)\n", "words = [\"\".join(rng.choices(\"абвгдежзи\", k=rng.randint(3, 6))) for _ in range(1000)]\n", "\n", "for name, fn in [(\"полиномиальная\", hash_str),\n", " (\"длина слова\", lambda s: len(s)),\n", " (\"первая буква\", lambda s: ord(s[0]))]:\n", " used, mx = distribution(fn, words, 101)\n", " print(f\"{name:>16}: занято {used:>3} из 101, максимум {mx:>4}\")\n", "\n", "# Ваш эксперимент: средняя длина цепочки у всех трёх функций одинакова.\n", "# Почему по ней нельзя судить о равномерности? На что смотреть?\n" ] }, { "cell_type": "code", "execution_count": null, "id": "collisions_growth_code", "metadata": {}, "outputs": [], "source": [ "# Рост и коэффициент заполнения: вставьте 20 000 ключей и смотрите describe().\n", "t = HashTable(4, hash_fn=hash_str)\n", "milestones = {1, 10, 100, 1000, 5000, 10000, 20000}\n", "for i in range(1, 20_001):\n", " t.put(f\"key-{i}\", i)\n", " if t.size in milestones:\n", " t.describe()\n", "\n", "# Ваш эксперимент: что происходит с alpha сразу после _resize и прямо перед ним?\n", "# Почему максимальная цепочка при 20 000 ключей — единицы, а не сотни?\n" ] }, { "cell_type": "code", "execution_count": null, "id": "collisions_worst_code", "metadata": {}, "outputs": [], "source": [ "# Худший случай: все ключи кратны ёмкости m. Для целых hash(x) == x, поэтому\n", "# при m = 1024 (степень двойки) все такие ключи окажутся в одном бакете.\n", "worst = HashTable(1024, hash_fn=hash)\n", "for k in range(0, 512_000, 1024):\n", " worst.put(k, k)\n", "worst.describe() # alpha ~0.5, но max цепочка — 500\n", "print(\"поиск отсутствующего:\", worst.contains(-1024)) # тот же бакет, ключа нет\n", "\n", "# Ваш эксперимент: замените 1024 на 1021 (простое) и повторите вставку\n", "# ключей, кратных 1024. Что изменилось и почему?\n" ] }, { "cell_type": "markdown", "id": "freq_md", "metadata": {}, "source": [ "## 3. Частоты и пара с суммой $k$\n", "\n", "Два приёма, которые и есть «словарь в бою». Сначала частоты — на своей таблице, затем на встроенном `dict`: это один и тот же код, только готовым инструментом.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "freq_code", "metadata": {}, "outputs": [], "source": [ "text = \"абракадабра\"\n", "\n", "# на своей таблице\n", "t = HashTable(hash_fn=hash_str)\n", "for ch in text:\n", " t.put(ch, t.get(ch, 0) + 1)\n", "\n", "# на встроенном dict — тот же приём\n", "freq = {}\n", "for ch in text:\n", " freq[ch] = freq.get(ch, 0) + 1\n", "\n", "print(\"своя таблица:\", [(ch, t.get(ch)) for ch in \"абркд\"])\n", "print(\"dict: \", freq)\n", "\n", "# Ваш эксперимент: почему выгоднее один проход с get(x, 0) + 1,\n", "# чем собрать все элементы, а потом считать каждый отдельно?\n" ] }, { "cell_type": "markdown", "id": "pairsum_md", "metadata": {}, "source": [ "**Пара с суммой $k$.** Не сортируем: проходим один раз и для каждого $x$ спрашиваем, встречалось ли уже дополнение $k - x$. Это $O(n)$ в среднем против $O(n\\log n)$ у «отсортировать + два указателя».\n" ] }, { "cell_type": "code", "execution_count": null, "id": "pairsum_code", "metadata": {}, "outputs": [], "source": [ "def pair_sum(a, k):\n", " \"\"\"Есть ли пара элементов с суммой k? Ожидаемое время O(n).\"\"\"\n", " seen = set()\n", " for x in a:\n", " if k - x in seen:\n", " return True\n", " seen.add(x)\n", " return False\n", "\n", "\n", "print(pair_sum([1, 2, 3, 4], 5)) # True: 1 + 4\n", "print(pair_sum([1, 2, 3, 4], 10)) # False\n", "print(pair_sum([3, 3], 6)) # True: 3 + 3\n", "\n", "# Ваш эксперимент: перепишите pair_sum так, чтобы она возвращала ИНДЕКСЫ\n", "# пары. Почему set уже недостаточно и нужен dict (значение -> индекс)?\n", "# Это мост к задаче № 3 (Two Sum).\n" ] }, { "cell_type": "markdown", "id": "dictset_md", "metadata": {}, "source": [ "## 4. Сопоставление с `dict` / `set` и «когда словарь»\n", "\n", "Один и тот же приём — три инструмента, и выбрать надо по условию:\n", "\n", "| Нужно | Инструмент |\n", "| --- | --- |\n", "| только «видели раньше» | `set` |\n", "| счётчики, ключ → значение | `dict` |\n", "| ключ — маленькое целое | массив (частотный массив) |\n", "| порядок ключей | `sorted` |\n", "| минимум/максимум по приоритету | куча (неделя 9) |\n", "\n", "Если вы писали на C++ в школе: `dict` — это `unordered_map`, `set` — `unordered_set`. В курсе пишем на Python, так что это только для узнавания.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "dictset_code", "metadata": {}, "outputs": [], "source": [ "xs = [3, 1, 2, 3, 2]\n", "\n", "s = set(xs) # принадлежность\n", "print(\"set:\", s, \"| 2 in s:\", 2 in s)\n", "\n", "c = {}\n", "for x in xs: # счётчик\n", " c[x] = c.get(x, 0) + 1\n", "print(\"dict:\", c)\n", "\n", "freq = [0] * 4 # ключи 0..3 — частотный массив\n", "for x in xs:\n", " freq[x] += 1\n", "print(\"массив:\", freq)\n", "\n", "# Ваш эксперимент: какой инструмент для значений от 0 до 10^6? Для строк-ключей?\n", "# Когда словарь хуже массива и почему?\n" ] }, { "cell_type": "markdown", "id": "openaddr_md", "metadata": {}, "source": [ "## 5. Открытая адресация: идея\n", "\n", "Без кода — картинка с лекции. Ячейка `h(key) % m` занята → идём дальше `(h(key) + i) % m`; так образуются **кластеры**. Удаление — ловушка: просто очистить ячейку нельзя, нужен **tombstone**.\n", "\n", "Почему это относится к «когда словарь»: открытая адресация компактнее и лучше по локальности, поэтому так устроен `dict` в Python. Но в задачах это деталь реализации, а не то, что вы пишете сами.\n" ] }, { "cell_type": "markdown", "id": "contest", "metadata": {}, "source": [ "## Контест\n", "\n", "Задачи сдавайте в контест недели 8 на [algo.ai.msu.ru](https://algo.ai.msu.ru). Номера LeetCode помогают найти условие.\n", "\n", "**Для зачёта семинара обязательны № 3 (1. Two Sum) и № 4 (49. Group Anagrams).** Разминка и звёздочка их не заменяют.\n", "\n", "| № | Задача | Статус | Сигнал «нужен словарь» |\n", "| --- | --- | --- | --- |\n", "| 1 | 217. Contains Duplicate | Разминка | «видели раньше» → `set` |\n", "| 2 | 242. Valid Anagram | Разминка | «частоты» → `dict` |\n", "| 3 | 1. Two Sum | **Обязательная** | «дополнение до суммы» + индексы → `dict` |\n", "| 4 | 49. Group Anagrams | **Обязательная** | «канонический ключ → группа» → `dict` списков |\n", "| 5 | 128. Longest Consecutive Sequence ★ | Звёздочка | «членство за $O(1)$» → `set` |\n", "\n", "**Порядок работы.** Разминку № 1–2 закрывайте быстро. Главная — № 3: там сортировка ломает исходные индексы, а `dict` хранит `значение → индекс`. Дальше № 4. № 5 — для тех, кто закрыл № 3–4.\n", "\n", "Типичный **WA**: в № 3 сортируют массив и возвращают индексы переставленного массива; в № 4 используют `list` как ключ (он нехешируем — берите `tuple`); в № 5 считают последовательность заново для каждого элемента ($O(n^2)$).\n", "\n", "**Про словарь и сортировку.** В № 1 и № 2 можно отсортировать, и это пройдёт тесты, но на паре просим решение за ожидаемое $O(n)$: именно оно показывает, зачем словарь. Тестер это не проверяет, поэтому спрашиваем у доски.\n" ] }, { "cell_type": "markdown", "id": "when_dict", "metadata": {}, "source": [ "## Шпаргалка: когда нужен словарь\n", "\n", "**Сигналы «нужен `dict` / `set`»:**\n", "\n", "- «видели раньше», удаление дубликатов → `set`;\n", "- частоты → `dict` (`d[x] = d.get(x, 0) + 1`);\n", "- дополнение до суммы $k$ → `dict` / `set` за один проход;\n", "- ключ → что-то (группа, индекс, каноническая форма, кэш) → `dict`;\n", "- доступ по произвольному ключу за $O(1)$.\n", "\n", "**Когда НЕ словарь:**\n", "\n", "- ключ — маленькое целое → массив (частотный массив недели 2);\n", "- порядок ключей → сортировка;\n", "- приоритет → куча (неделя 9);\n", "- позиция → список.\n", "\n", "**Плата.** Память $\\Theta(n+m)$; $O(1)$ только в среднем, худший случай $\\Theta(n)$.\n", "\n", "Своя таблица и её проверка:\n", "\n", "- бакет — список пар, индекс `hash_fn(key) % m`;\n", "- `put` обновляет, а не добавляет вторую пару; `_resize` перекладывает по новому модулю;\n", "- «$O(1)$ в среднем» — предположение о равномерном хеше; подбор ключей даёт $\\Theta(n)$.\n" ] }, { "cell_type": "markdown", "id": "submit", "metadata": {}, "source": [ "## Сдача\n", "\n", "- **Этот** `.ipynb` семинаристу отправлять не нужно.\n", "- Для зачёта выполните **№ 3 — 1. Two Sum** и **№ 4 — 49. Group Anagrams** в контесте на [algo.ai.msu.ru](https://algo.ai.msu.ru).\n", "- Разминка № 1–2 и звёздочка № 5 — по желанию, для зачёта не требуются.\n", "- Если обязательные задачи не закончены на паре, дорешайте их в том же контесте после занятия.\n", "- Хеш-функция, коллизии и среднее против наихудшего входят в коллоквиум 2.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.13" } }, "nbformat": 4, "nbformat_minor": 5 }