{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "lec08-000",
   "metadata": {},
   "source": [
    "# Лекция 8. Хеш-таблицы и хеш-функции\n",
    "\n",
    "На прошлой лекции мы собирали стек, очередь и дек: один интерфейс — разные реализации. Сегодня то же самое для **словаря** и **множества**, но цена операций важнее: хочется, чтобы и вставка, и поиск стоили $O(1)$ **в среднем**.\n",
    "\n",
    "Опираемся на лекцию 7 (ADT, `class`, `Stack`, `RingQueue`) и семинар 4 (`lower_bound`). Частотный массив из недели 2 — тот же приём «значение как индекс»; теперь ключ не обязан быть маленьким целым.\n",
    "\n",
    "`dict` и `set` в общем пользовании до этой пары нет: словарь собираем сами. Встроенные `dict` / `set` показываем в конце как эталон интерфейса — после пары ими можно пользоваться как рабочим инструментом.\n",
    "\n",
    "## План\n",
    "\n",
    "0. Множество на неупорядоченном и упорядоченном списке: таблица цен.\n",
    "1. Словарь как ADT: интерфейс, контракт, хешируемость; множество как частный случай.\n",
    "2. Хеш-функции: требования, примеры для чисел и строк, равномерность, плохие функции.\n",
    "3. Своя `class HashTable`: метод цепочек, инвариант, цена $O(1+\\alpha)$.\n",
    "4. Коэффициент заполнения $\\alpha$: перехеширование, амортизация, среднее против худшего.\n",
    "5. Открытая адресация: линейное пробирование, кластеры, tombstone — идея.\n",
    "6. `dict` / `set` как эталон интерфейса и мост к семинару 8.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-001",
   "metadata": {},
   "source": [
    "## 0. Проблематизация: множество на списке\n",
    "\n",
    "**ADT «множество»**: `add(x)`, `contains(x)`, `remove(x)`. Контракт простой: элемент либо есть, либо нет; повторное добавление ничего не меняет.\n",
    "\n",
    "Сначала честный неупорядоченный список. Все три операции просматривают данные целиком — в худшем случае $\\Theta(n)$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "lec08-002",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.410977Z",
     "iopub.status.busy": "2026-10-19T08:30:51.410869Z",
     "iopub.status.idle": "2026-10-19T08:30:51.414481Z",
     "shell.execute_reply": "2026-10-19T08:30:51.414081Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SetOnList([3, 1, 2])\n",
      "True\n",
      "SetOnList([3, 2])\n"
     ]
    }
   ],
   "source": [
    "class SetOnList:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.data:      # проверка дубликата — O(n)\n",
    "            self.data.append(x)\n",
    "\n",
    "    def contains(self, x):\n",
    "        return x in self.data       # O(n)\n",
    "\n",
    "    def remove(self, x):\n",
    "        self.data.remove(x)         # O(n)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"SetOnList({self.data!r})\"\n",
    "\n",
    "\n",
    "s = SetOnList()\n",
    "for x in (3, 1, 3, 2):\n",
    "    s.add(x)\n",
    "print(s)                 # повтор 3 не добавился\n",
    "print(s.contains(2))     # True\n",
    "s.remove(1)\n",
    "print(s)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-003",
   "metadata": {},
   "source": [
    "Теперь тот же ADT, но данные поддерживаются **упорядоченными**. Поиск идёт бинарным поиском через `lower_bound` с семинара 4, зато `add` обязан найти позицию и **сдвинуть хвост**.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "lec08-004",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.415465Z",
     "iopub.status.busy": "2026-10-19T08:30:51.415359Z",
     "iopub.status.idle": "2026-10-19T08:30:51.419035Z",
     "shell.execute_reply": "2026-10-19T08:30:51.418686Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "SortedSetOnList([1, 2, 3])\n",
      "True\n",
      "SortedSetOnList([2, 3])\n"
     ]
    }
   ],
   "source": [
    "class SortedSetOnList:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "\n",
    "    def _lower_bound(self, x):\n",
    "        lo, hi = 0, len(self.data)\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if self.data[mid] < x:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "\n",
    "    def contains(self, x):\n",
    "        i = self._lower_bound(x)\n",
    "        return i < len(self.data) and self.data[i] == x\n",
    "\n",
    "    def add(self, x):\n",
    "        i = self._lower_bound(x)\n",
    "        if i == len(self.data) or self.data[i] != x:\n",
    "            self.data.insert(i, x)  # сдвиг хвоста — Θ(n)\n",
    "\n",
    "    def remove(self, x):\n",
    "        i = self._lower_bound(x)\n",
    "        if i < len(self.data) and self.data[i] == x:\n",
    "            self.data.pop(i)        # сдвиг хвоста — Θ(n)\n",
    "        else:\n",
    "            raise KeyError(x)\n",
    "\n",
    "    def __repr__(self):\n",
    "        return f\"SortedSetOnList({self.data!r})\"\n",
    "\n",
    "\n",
    "s = SortedSetOnList()\n",
    "for x in (3, 1, 2, 1):\n",
    "    s.add(x)\n",
    "print(s)                 # данные упорядочены, повтор 1 не добавлен\n",
    "print(s.contains(2))     # True\n",
    "s.remove(1)\n",
    "print(s)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-005",
   "metadata": {},
   "source": [
    "Таблица цен — из неё весь дальнейший сюжет:\n",
    "\n",
    "| Операция | Неупорядоченный список | Упорядоченный список |\n",
    "| --- | --- | --- |\n",
    "| `add` | $O(1)$ без проверки дубликата, $O(n)$ с проверкой | $O(n)$: поиск $O(\\log n)$, но сдвиг $\\Theta(n)$ |\n",
    "| `contains` | $O(n)$ | $O(\\log n)$ |\n",
    "| `remove` | $O(n)$ | $O(n)$: поиск $O(\\log n)$, но сдвиг $\\Theta(n)$ |\n",
    "\n",
    "Одна операция быстрая, другая дорогая. Хочется $O(1)$ **в среднем** на обе — за этим и идём к хеш-таблице.\n",
    "\n",
    "Та же дилемма была на неделе 7: у стека и очереди один интерфейс и разные реализации, и цена операции зависела от реализации. Здесь сравниваем две реализации одного ADT.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-006",
   "metadata": {},
   "source": [
    "## 1. Словарь как ADT\n",
    "\n",
    "**Словарь** (ассоциативный массив, map) хранит пары «ключ → значение». Интерфейс:\n",
    "\n",
    "- `put(key, value)` — вставить или обновить;\n",
    "- `get(key)` — вернуть значение, при отсутствии — `KeyError`;\n",
    "- `contains(key)` — есть ли ключ;\n",
    "- `remove(key)` — удалить пару;\n",
    "- `len(table)` — число ключей.\n",
    "\n",
    "**Контракт.** Ключи уникальны; `put` по существующему ключу **обновляет** значение, а не добавляет вторую пару; множество — частный случай, где значение не нужно.\n",
    "\n",
    "В Python у встроенного словаря тот же интерфейс, только короче: `d[k]`, `d.get(k)`, `k in d`, `del d[k]`. Наша таблица повторяет смысл, а не синтаксис.\n",
    "\n",
    "Та же мысль, что на лекции 7: ADT — это интерфейс и контракт, представление выбираем сами. Сегодня интерфейс словаря, представление — хеш-таблица.\n",
    "\n",
    "**Ключ обязан быть хешируемым.** `int`, `str`, `tuple` из хешируемых — да; `list`, `dict`, `set` — нет. Причина: таблица опирается на неизменность ключа. Если ключ изменить после вставки, он окажется не в своём бакете, и найти его будет нельзя.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-007",
   "metadata": {},
   "source": [
    "## 2. Хеш-функции\n",
    "\n",
    "Идея: превратить ключ в индекс массива. **Хеш-функция** $h(key)$ отображает ключ в число, индекс бакета — $h(key) \\bmod m$.\n",
    "\n",
    "Требования:\n",
    "\n",
    "1. **Детерминизм** — одинаковый ключ даёт одинаковый индекс.\n",
    "2. **Быстрота** — не зависит от числа элементов таблицы; от длины ключа зависит линейно, и это единственная плата.\n",
    "3. **Равномерность** — похожие ключи попадают в разные бакеты.\n",
    "4. **Согласованность с равенством** — если `a == b`, то `h(a) == h(b)`; обратное не требуется.\n",
    "\n",
    "Для целых напрашивается само число по модулю $m$. Для строк — **полиномиальная свёртка**: считаем строку числом в системе счисления с основанием 31.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "lec08-008",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.420070Z",
     "iopub.status.busy": "2026-10-19T08:30:51.419967Z",
     "iopub.status.idle": "2026-10-19T08:30:51.422353Z",
     "shell.execute_reply": "2026-10-19T08:30:51.421989Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "кот: хеш =    1074558, индекс при m = 101:  19\n",
      "ток: хеш =    1082238, индекс при m = 101:  23\n",
      "кто: хеш =    1074678, индекс при m = 101:  38\n"
     ]
    }
   ],
   "source": [
    "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",
    "for word in (\"кот\", \"ток\", \"кто\"):\n",
    "    code = hash_str(word)\n",
    "    print(f\"{word}: хеш = {code:>10}, индекс при m = 101: {code % 101:>3}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-009",
   "metadata": {},
   "source": [
    "`hash_str` возвращает **хеш-код** — большое число. Индекс бакета получается из него отдельно: `hash_str(key) % m`. Внутри многочлена остаток берётся по большому простому модулю, иначе число растёт с длиной строки и длинная арифметика съедает выигрыш.\n",
    "\n",
    "**Почему 31?** Традиция: множитель не 1 и не чётный; 31 хорошо перемешивает соседние коды символов. Другие нечётные основания (37, 131) работают так же.\n",
    "\n",
    "**Почему порядок символов важен?** В свёртке каждый следующий символ умножается на основание в своей степени, поэтому анаграммы дают разные хеши: `кот`, `ток` и `кто` — три разных числа. На этом и стоит равномерность.\n",
    "\n",
    "Хеш-код и индекс — разные вещи: одинаковый хеш-код при разных $m$ даёт разные индексы, а разные хеш-коды могут дать один индекс. Коллизия индексов — нормальная ситуация, а не ошибка.\n",
    "\n",
    "Полезное следствие: если `h(a) != h(b)`, ключи точно разные. А `h(a) == h(b)` ничего не говорит о равенстве — это коллизия.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "lec08-010",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.423272Z",
     "iopub.status.busy": "2026-10-19T08:30:51.423171Z",
     "iopub.status.idle": "2026-10-19T08:30:51.433987Z",
     "shell.execute_reply": "2026-10-19T08:30:51.433582Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1000 слов по 101 бакетам, alpha = 9.9\n",
      "полиномиальная     занято 101 из 101, средняя непустого    9.9, максимум   18\n",
      "len(s)             занято   1 из 101, средняя непустого 1000.0, максимум 1000\n",
      "ord(s[0])          занято  26 из 101, средняя непустого   38.5, максимум   48\n",
      "константа          занято   1 из 101, средняя непустого 1000.0, максимум 1000\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "import string\n",
    "\n",
    "\n",
    "def hash_len(s):\n",
    "    return len(s)\n",
    "\n",
    "\n",
    "def hash_first(s):\n",
    "    return ord(s[0])\n",
    "\n",
    "\n",
    "def hash_const(s):\n",
    "    return 0\n",
    "\n",
    "\n",
    "random.seed(42)\n",
    "words = []\n",
    "while len(words) < 1000:\n",
    "    word = \"\".join(random.choice(string.ascii_lowercase) for _ in range(5))\n",
    "    if word not in words:\n",
    "        words.append(word)\n",
    "\n",
    "M = 101      # простое число: распределение видно, цепочки короткие\n",
    "\n",
    "\n",
    "def report(name, keys, hash_fn, m):\n",
    "    counts = [0] * m\n",
    "    for key in keys:\n",
    "        counts[hash_fn(key) % m] += 1\n",
    "    used = 0\n",
    "    for c in counts:\n",
    "        if c:\n",
    "            used += 1\n",
    "    average = sum(counts) / used\n",
    "    print(f\"{name:<18} занято {used:>3} из {m}, \"\n",
    "          f\"средняя непустого {average:>6.1f}, максимум {max(counts):>4}\")\n",
    "\n",
    "\n",
    "print(f\"1000 слов по {M} бакетам, alpha = {1000 / M:.1f}\")\n",
    "report(\"полиномиальная\", words, hash_str, M)\n",
    "report(\"len(s)\", words, hash_len, M)\n",
    "report(\"ord(s[0])\", words, hash_first, M)\n",
    "report(\"константа\", words, hash_const, M)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-011",
   "metadata": {},
   "source": [
    "Числа показывают, что «равномерно» — свойство распределения, а не лозунг:\n",
    "\n",
    "- полиномиальная функция занимает все 101 бакет, максимум 18 при среднем 9.9;\n",
    "- `len(s)` сваливает все слова длины 5 в одну цепочку из 1000;\n",
    "- `ord(s[0])` использует только первую букву: занято 26 бакетов, максимум 48;\n",
    "- константа — вся таблица в одной цепочке, это худший случай.\n",
    "\n",
    "Средняя длина по **всем** бакетам всегда равна $n/m \\approx 9.9$ — по ней равномерность не проверишь. Смотрим на занятость, максимум и разброс.\n",
    "\n",
    "Бакетов 101, а не 10: при малом $m$ средняя цепочка $n/m$ велика, и различия между функциями смазаны. На большом $m$ видно, что `len(s)` и `ord(s[0])` теряют информацию о ключе.\n",
    "\n",
    "Подбор ключей под известную хеш-функцию сваливает всё в одну цепочку. Поэтому в Python хеши строк рандомизированы при запуске: подбирать под них ключи заранее нельзя.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "lec08-012",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.435018Z",
     "iopub.status.busy": "2026-10-19T08:30:51.434911Z",
     "iopub.status.idle": "2026-10-19T08:30:51.472733Z",
     "shell.execute_reply": "2026-10-19T08:30:51.472339Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "в текущем процессе: -2543911540180361055\n",
      "в новом процессе: 4637504618212963118\n",
      "в новом процессе: -8958671136431960088\n",
      "в новом процессе: 2924240912931008508\n"
     ]
    }
   ],
   "source": [
    "import subprocess\n",
    "import sys\n",
    "\n",
    "print(\"в текущем процессе:\", hash(\"строка\"))\n",
    "\n",
    "for _ in range(3):\n",
    "    result = subprocess.run(\n",
    "        [sys.executable, \"-c\", \"print(hash('строка'))\"],\n",
    "        capture_output=True,\n",
    "        text=True,\n",
    "    )\n",
    "    print(\"в новом процессе:\", result.stdout.strip())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-013",
   "metadata": {},
   "source": [
    "Встроенный `hash()` для строк **рандомизирован** при запуске (`PYTHONHASHSEED`): в одном процессе значение постоянно, в новом — другое. Для таблицы это нормально и защищает от подбора ключей; для воспроизводимых демонстраций — нет. Поэтому в ноутбуке хеш-функция передаётся в таблицу **параметром**: `HashTable(hash_fn=hash_str)`.\n",
    "\n",
    "Для целых `hash(x) == x`, поэтому в демонстрациях ниже это удобно. Но именно поэтому степень двойки в $m$ опасна: номер бакета определяется младшими битами.\n",
    "\n",
    "`id()` как хеш не подходит: у равных строк адреса разные, и требование `a == b ⇒ h(a) == h(b)` нарушается.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-014",
   "metadata": {},
   "source": [
    "## 3. Своя `class HashTable`: метод цепочек\n",
    "\n",
    "Устройство: массив **бакетов**, в каждом бакете — список пар `(ключ, значение)`. Ключ попадает в бакет с номером `hash_fn(key) % m`. Если два ключа дали один индекс — это **коллизия**, и она не ошибка: обе пары лежат в одном бакете, а поиск идёт по цепочке.\n",
    "\n",
    "Параметр `hash_fn` нужен для демонстраций: таблица не зависит от конкретной хеш-функции. По умолчанию — встроенный `hash`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "lec08-015",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.473799Z",
     "iopub.status.busy": "2026-10-19T08:30:51.473689Z",
     "iopub.status.idle": "2026-10-19T08:30:51.479578Z",
     "shell.execute_reply": "2026-10-19T08:30:51.479114Z"
    }
   },
   "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",
    "        bucket = self.data[self._index(key)]\n",
    "        for i in range(len(bucket)):\n",
    "            k = bucket[i][0]\n",
    "            if k == key:                 # ключ уже есть — обновляем\n",
    "                bucket[i] = (key, value)\n",
    "                return\n",
    "        bucket.append((key, value))\n",
    "        self.size += 1\n",
    "        if self.size > self.LOAD_LIMIT * len(self.data):\n",
    "            self._resize()\n",
    "\n",
    "    def get(self, key, default=_MISSING):\n",
    "        bucket = self.data[self._index(key)]\n",
    "        for k, v in bucket:  # O(len(bucket))\n",
    "            if k == key:\n",
    "                return v\n",
    "        if default is not _MISSING:      # второй аргумент передан явно\n",
    "            return default\n",
    "        raise KeyError(key)\n",
    "\n",
    "    def contains(self, key):\n",
    "        for k, _ in self.data[self._index(key)]:\n",
    "            if k == key:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "    def remove(self, key):\n",
    "        bucket = self.data[self._index(key)]\n",
    "        for i, (k, _) in enumerate(bucket):\n",
    "            if k == key:\n",
    "                bucket.pop(i)  # O(len(bucket))\n",
    "                self.size -= 1\n",
    "                return\n",
    "        raise KeyError(key)\n",
    "\n",
    "    def _resize(self):\n",
    "        old = self.data\n",
    "        self.data = [[] for _ in range(2 * len(old))]\n",
    "        self.size = 0\n",
    "        for bucket in old:\n",
    "            for k, v in bucket:\n",
    "                self.put(k, v)\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 = 0\n",
    "        for length in lengths:\n",
    "            if length:\n",
    "                used += 1\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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-016",
   "metadata": {},
   "source": [
    "**Инвариант таблицы:**\n",
    "\n",
    "1. каждый ключ лежит ровно в одном бакете;\n",
    "2. бакет ключа — это `hash_fn(key) % m`;\n",
    "3. `size` — число ключей, а не пар и не бакетов;\n",
    "4. после `_resize` все ключи переложены по новому модулю.\n",
    "\n",
    "Пара в бакете — кортеж `(ключ, значение)`, поэтому при обновлении заменяем её целиком: `bucket[i] = (key, value)`.\n",
    "\n",
    "`_MISSING` — служебная метка: она позволяет отличить «второй аргумент не передан» от `default=None`. Иначе отсутствие ключа и сохранённое значение `None` были бы неразличимы.\n",
    "\n",
    "`describe` — вспомогательный метод для печати статистики; к интерфейсу словаря он не относится.\n",
    "\n",
    "Посмотрим на примере: $m = 8$, несколько ключей, обновление, `KeyError`, удаление из середины цепочки.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "8dbe6eb7-f40c-445f-b539-46851fbd2589",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.480689Z",
     "iopub.status.busy": "2026-10-19T08:30:51.480484Z",
     "iopub.status.idle": "2026-10-19T08:30:51.483657Z",
     "shell.execute_reply": "2026-10-19T08:30:51.483262Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "HashTable(8 бакетов, 6 ключей)\n",
      "[[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 3), ('слива', 5), ('киви', 6)], [], [('груша', 4)], []]\n",
      "get('вишня') = 3\n"
     ]
    }
   ],
   "source": [
    "t = HashTable(8, hash_fn=hash_str)\n",
    "for i, key in enumerate((\"яблоко\", \"банан\", \"вишня\", \"груша\", \"слива\", \"киви\")):\n",
    "    t.put(key, i + 1)\n",
    "\n",
    "print(t)\n",
    "print(t.data)                 # видно, какие ключи попали в один бакет\n",
    "print(\"get('вишня') =\", t.get(\"вишня\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4359b2d9-5728-4207-8d35-f839663fe8d6",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.484576Z",
     "iopub.status.busy": "2026-10-19T08:30:51.484468Z",
     "iopub.status.idle": "2026-10-19T08:30:51.486428Z",
     "shell.execute_reply": "2026-10-19T08:30:51.486052Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "после put('вишня', 100): [[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 100), ('слива', 5), ('киви', 6)], [], [('груша', 4)], []]\n"
     ]
    }
   ],
   "source": [
    "t.put(\"вишня\", 100)           # обновление, а не вторая пара\n",
    "print(\"после put('вишня', 100):\", t.data)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "eb63461c-db5c-4ea4-92d8-1e2d8214533e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.487314Z",
     "iopub.status.busy": "2026-10-19T08:30:51.487213Z",
     "iopub.status.idle": "2026-10-19T08:30:51.489348Z",
     "shell.execute_reply": "2026-10-19T08:30:51.488970Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "contains('айва') = False\n",
      "get('айва', 0) = 0\n",
      "KeyError: 'айва'\n"
     ]
    }
   ],
   "source": [
    "print(\"contains('айва') =\", t.contains(\"айва\"))\n",
    "print(\"get('айва', 0) =\", t.get(\"айва\", 0))\n",
    "try:\n",
    "    t.get(\"айва\")\n",
    "except KeyError as err:\n",
    "    print(\"KeyError:\", err)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "lec08-017",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.490259Z",
     "iopub.status.busy": "2026-10-19T08:30:51.490106Z",
     "iopub.status.idle": "2026-10-19T08:30:51.492361Z",
     "shell.execute_reply": "2026-10-19T08:30:51.491885Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "после remove('слива'): [[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 100), ('киви', 6)], [], [('груша', 4)], []]\n",
      "len(t) = 5\n"
     ]
    }
   ],
   "source": [
    "t.remove(\"слива\")\n",
    "print(\"после remove('слива'):\", t.data)\n",
    "print(\"len(t) =\", len(t))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-018",
   "metadata": {},
   "source": [
    "Цена: `put`, `get`, `remove` стоят $O(1 + \\text{длина цепочки})$. При равномерном хеше и коэффициенте заполнения $\\alpha = n/m$ средняя длина цепочки — $\\alpha$, итого $O(1+\\alpha)$.\n",
    "\n",
    "**Почему $m$ лучше брать простым?** Если $m$ — степень двойки, номер бакета определяется только младшими битами хеша. Любая закономерность в них (например, все ключи кратны 8) сваливает ключи в один бакет. Простое $m$ перемешивает все биты. Степень двойки тоже годится, но тогда хеш нужно дополнительно перемешивать — так и сделано в `dict` Python.\n",
    "\n",
    "Ключи сравниваем через `==`, а не `is`: равные строки не обязаны быть одним объектом. В Python `%` от отрицательного числа неотрицателен, поэтому индекс бакета не уйдёт в минус.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "lec08-019",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.493732Z",
     "iopub.status.busy": "2026-10-19T08:30:51.493565Z",
     "iopub.status.idle": "2026-10-19T08:30:51.496413Z",
     "shell.execute_reply": "2026-10-19T08:30:51.496036Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m =   8: занято   1 бакетов, max = 100\n",
      "m =  97: занято  97 бакетов, max = 2\n"
     ]
    }
   ],
   "source": [
    "keys = [8 * i for i in range(100)]      # кратны 8; для целых hash(key) == key\n",
    "\n",
    "for m in (8, 97):\n",
    "    counts = [0] * m\n",
    "    for key in keys:\n",
    "        counts[key % m] += 1\n",
    "    used = 0\n",
    "    for c in counts:\n",
    "        if c:\n",
    "            used += 1\n",
    "    print(f\"m = {m:>3}: занято {used:>3} бакетов, max = {max(counts)}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-020",
   "metadata": {},
   "source": [
    "## 4. Коэффициент заполнения и перехеширование\n",
    "\n",
    "**Коэффициент заполнения** $\\alpha = n/m$: сколько в среднем пар приходится на бакет. Ожидаемое время операции — $O(1+\\alpha)$; при $\\alpha$, близком к единице, цепочки растут, и константа в оценке перестаёт быть константой.\n",
    "\n",
    "Правило: когда $\\alpha$ превышает порог (в коде `LOAD_LIMIT = 0.75`), удваиваем $m$ и **перекладываем** все пары заново. Старые индексы недействительны: изменился модуль. Это `_resize`.\n",
    "\n",
    "Стоимость: одна операция `put` в момент роста стоит $\\Theta(n)$, но такие операции редки. **Амортизированно** выходит $O(1)$ — та же логика, что у `list.append` на лекции 2.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "lec08-021",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.497723Z",
     "iopub.status.busy": "2026-10-19T08:30:51.497516Z",
     "iopub.status.idle": "2026-10-19T08:30:51.529478Z",
     "shell.execute_reply": "2026-10-19T08:30:51.529085Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m =    16, n =     7, alpha = 0.44, занято     5, max цепочка = 2\n",
      "m =    32, n =    13, alpha = 0.41, занято    11, max цепочка = 2\n",
      "m =    64, n =    25, alpha = 0.39, занято    20, max цепочка = 2\n",
      "m =   128, n =    49, alpha = 0.38, занято    41, max цепочка = 2\n",
      "m =   256, n =    97, alpha = 0.38, занято    81, max цепочка = 2\n",
      "m =   512, n =   193, alpha = 0.38, занято   164, max цепочка = 4\n",
      "m =  1024, n =   385, alpha = 0.38, занято   321, max цепочка = 3\n",
      "m =  2048, n =   769, alpha = 0.38, занято   638, max цепочка = 4\n",
      "m =  4096, n =  1537, alpha = 0.38, занято  1281, max цепочка = 4\n",
      "m =  8192, n =  3073, alpha = 0.38, занято  2574, max цепочка = 4\n",
      "m = 16384, n =  6145, alpha = 0.38, занято  5154, max цепочка = 5\n",
      "итог:\n",
      "m = 16384, n = 10000, alpha = 0.61, занято  7530, max цепочка = 6\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "random.seed(42)\n",
    "keys = random.sample(range(1_000_000), 10_000)\n",
    "\n",
    "t = HashTable(hash_fn=hash)\n",
    "last_m = len(t.data)\n",
    "for key in keys:\n",
    "    t.put(key, key * key)\n",
    "    if len(t.data) != last_m:       # таблица только что выросла\n",
    "        last_m = len(t.data)\n",
    "        t.describe()\n",
    "\n",
    "print(\"итог:\")\n",
    "t.describe()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-022",
   "metadata": {},
   "source": [
    "$\\alpha$ держится ниже 0.75: сразу после удвоения она около 0.4, к следующему росту поднимается к 0.75. Максимальная цепочка — единицы: на 10 000 ключей она не больше 6. Это и есть «$O(1)$ в среднем» на практике: не потому, что коллизий нет, а потому, что их немного и они короткие.\n",
    "\n",
    "**Среднее против худшего:**\n",
    "\n",
    "| | Среднее (равномерный хеш) | Худшее |\n",
    "| --- | --- | --- |\n",
    "| `put` / `get` / `remove` | $O(1+\\alpha)$, амортизированно $O(1)$ | $\\Theta(n)$: все ключи в одной цепочке |\n",
    "| Память | $\\Theta(n+m)$ | $\\Theta(n+m)$ |\n",
    "\n",
    "Худший случай достигается не «плохим Python», а плохой хеш-функцией или подбором ключей. Именно поэтому нельзя говорить «хеш-таблица работает за $O(1)$» без слова «в среднем».\n",
    "\n",
    "Худший случай: ёмкость $m = 1024$, все ключи кратны 1024. Формально $\\alpha \\approx 0.5$, а фактически вся таблица — одна цепочка.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "lec08-023",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.530667Z",
     "iopub.status.busy": "2026-10-19T08:30:51.530525Z",
     "iopub.status.idle": "2026-10-19T08:30:51.536072Z",
     "shell.execute_reply": "2026-10-19T08:30:51.535682Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "m =  1024, n =   500, alpha = 0.49, занято     1, max цепочка = 500\n",
      "длина первой цепочки: 500\n"
     ]
    }
   ],
   "source": [
    "worst = HashTable(1024, hash_fn=hash)\n",
    "for i in range(500):\n",
    "    worst.put(1024 * i, i)\n",
    "\n",
    "worst.describe()\n",
    "print(\"длина первой цепочки:\", len(worst.data[0]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-024",
   "metadata": {},
   "source": [
    "$\\alpha$ маленькая, но это не спасает: все 500 ключей лежат в одной цепочке, и каждый поиск просматривает до 500 пар, хотя формально $\\alpha \\approx 0.5$. Оценка $O(1+\\alpha)$ держится **в предположении равномерного хеша**; при подборе ключей предположение нарушено.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-025",
   "metadata": {},
   "source": [
    "## 5. Открытая адресация\n",
    "\n",
    "Другой способ разрешения коллизий: цепочек нет, все пары лежат в самом массиве. Если ячейка `h(key) % m` занята, идём дальше по правилу, например `(h(key) + i) % m` — **линейное пробирование**. Поиск идёт той же последовательностью, пока не найдёт ключ или пустую ячейку.\n",
    "\n",
    "В примере ниже храним только ключи: для картинки коллизий этого достаточно. Массив из 8 ячеек заполняется несколькими вставками — видно, как образуются **кластеры**, подряд занятые ячейки. Чем выше $\\alpha$, тем длиннее пробы; при $\\alpha \\to 1$ линейное пробирование деградирует.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "lec08-026",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.537047Z",
     "iopub.status.busy": "2026-10-19T08:30:51.536941Z",
     "iopub.status.idle": "2026-10-19T08:30:51.540164Z",
     "shell.execute_reply": "2026-10-19T08:30:51.539808Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ключ   0: старт  0, проб 1, слот  0\n",
      "ключ   8: старт  0, проб 2, слот  1\n",
      "ключ  16: старт  0, проб 3, слот  2\n",
      "ключ  24: старт  0, проб 4, слот  3\n",
      "ключ   7: старт  7, проб 1, слот  7\n",
      "ключ  15: старт  7, проб 6, слот  4\n",
      "ключ  23: старт  7, проб 7, слот  5\n",
      "[0, 8, 16, 24, 15, 23, None, 7]\n",
      "ищем 16: 2\n",
      "ищем 5: None\n"
     ]
    }
   ],
   "source": [
    "M = 8\n",
    "slots = [None] * M\n",
    "\n",
    "\n",
    "def insert_linear(key):\n",
    "    start = key % M\n",
    "    for step in range(M):\n",
    "        pos = (start + step) % M\n",
    "        if slots[pos] is None:\n",
    "            slots[pos] = key\n",
    "            print(f\"ключ {key:>3}: старт {start:>2}, проб {step + 1}, слот {pos:>2}\")\n",
    "            return pos\n",
    "    raise OverflowError(\"таблица заполнена\")\n",
    "\n",
    "\n",
    "def find_linear(key):\n",
    "    start = key % M\n",
    "    for step in range(M):\n",
    "        pos = (start + step) % M\n",
    "        if slots[pos] is None:\n",
    "            return None\n",
    "        if slots[pos] == key:\n",
    "            return pos\n",
    "    return None\n",
    "\n",
    "\n",
    "for key in (0, 8, 16, 24, 7, 15, 23):\n",
    "    insert_linear(key)\n",
    "print(slots)\n",
    "print(\"ищем 16:\", find_linear(16))\n",
    "print(\"ищем 5:\", find_linear(5))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-027",
   "metadata": {},
   "source": [
    "**Удаление — ловушка.** Просто очистить ячейку нельзя: она была частью пробы, и поиск за ней остановится раньше времени. Нужен **tombstone** — метка «здесь был ключ»: поиск её проходит, вставка может занять. Полная реализация с tombstone выходит за рамки этой пары.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "lec08-028",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.541148Z",
     "iopub.status.busy": "2026-10-19T08:30:51.541033Z",
     "iopub.status.idle": "2026-10-19T08:30:51.543473Z",
     "shell.execute_reply": "2026-10-19T08:30:51.542934Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "удаляем 8: просто очищаем ячейку 1\n",
      "ищем 16 после удаления: None\n",
      "[0, None, 16, 24, 15, 23, None, 7]\n"
     ]
    }
   ],
   "source": [
    "print(\"удаляем 8: просто очищаем ячейку 1\")\n",
    "slots[1] = None\n",
    "print(\"ищем 16 после удаления:\", find_linear(16))\n",
    "print(slots)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-029",
   "metadata": {},
   "source": [
    "`16` лежит в ячейке 2, но поиск стартует с 0, видит пустую ячейку 1 и делает вывод «ключа нет». С tombstone ячейка 1 осталась бы помеченной, поиск прошёл бы дальше и нашёл 16.\n",
    "\n",
    "**Сравнение с цепочками:**\n",
    "\n",
    "| | Цепочки | Открытая адресация |\n",
    "| --- | --- | --- |\n",
    "| Коллизии | пары в одном бакете | пробы по массиву |\n",
    "| $\\alpha$ | может быть $>1$ | обязана быть $<1$ |\n",
    "| Удаление | просто убрать из списка | нужен tombstone |\n",
    "| Память | список в каждом бакете и пары | только массив ячеек |\n",
    "| Локальность | хуже | лучше |\n",
    "\n",
    "В Python `dict` устроен как открытая адресация с перемешиванием, но это деталь реализации, а не интерфейса.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-030",
   "metadata": {},
   "source": [
    "## 6. `dict` / `set` как эталон и к семинару 8\n",
    "\n",
    "Сопоставим интерфейс:\n",
    "\n",
    "| Наша таблица | Встроенный `dict` |\n",
    "| --- | --- |\n",
    "| `put(k, v)` | `d[k] = v` |\n",
    "| `get(k)` / `get(k, default)` | `d[k]` / `d.get(k, default)` |\n",
    "| `contains(k)` | `k in d` |\n",
    "| `remove(k)` | `del d[k]` |\n",
    "| `len(t)` | `len(d)` |\n",
    "\n",
    "`set` — то же самое без значений. У встроенного словаря есть ещё итерация, `keys` / `values` / `items` и **порядок вставки**; наша таблица этого не обещает.\n",
    "\n",
    "Правило курса: `dict` и `set` — **эталон интерфейса** и рабочий инструмент после этой пары, но не замена собственной реализации в упражнениях семинара.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "lec08-031",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.544530Z",
     "iopub.status.busy": "2026-10-19T08:30:51.544411Z",
     "iopub.status.idle": "2026-10-19T08:30:51.547439Z",
     "shell.execute_reply": "2026-10-19T08:30:51.547053Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "d = {'яблоко': 3, 'банан': 5}\n",
      "d['яблоко'] = 3\n",
      "d.get('вишня') = None\n",
      "d.get('вишня', 0) = 0\n",
      "'банан' in d: True  len(d) = 2\n",
      "после обновления: {'яблоко': 10, 'банан': 5}\n",
      "после del: {'яблоко': 10}\n",
      "s = {1, 2, 3}  1 in s: True  len(s) = 3\n",
      "после discard(1): {2, 3}\n"
     ]
    }
   ],
   "source": [
    "d = {}\n",
    "d[\"яблоко\"] = 3\n",
    "d[\"банан\"] = 5\n",
    "print(\"d =\", d)\n",
    "print(\"d['яблоко'] =\", d[\"яблоко\"])\n",
    "print(\"d.get('вишня') =\", d.get(\"вишня\"))\n",
    "print(\"d.get('вишня', 0) =\", d.get(\"вишня\", 0))\n",
    "print(\"'банан' in d:\", \"банан\" in d, \" len(d) =\", len(d))\n",
    "\n",
    "d[\"яблоко\"] = 10\n",
    "print(\"после обновления:\", d)\n",
    "del d[\"банан\"]\n",
    "print(\"после del:\", d)\n",
    "\n",
    "s = {3, 1, 2}\n",
    "s.add(3)\n",
    "print(\"s =\", s, \" 1 in s:\", 1 in s, \" len(s) =\", len(s))\n",
    "s.discard(1)\n",
    "print(\"после discard(1):\", s)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-031a",
   "metadata": {},
   "source": [
    "Порядок в `set` не обещан: `{3, 1, 2}` печатается как `{1, 2, 3}` — это не сортировка, а деталь реализации. У `dict` порядок вставки гарантирован, у множества — нет.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "lec08-032",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-10-19T08:30:51.548494Z",
     "iopub.status.busy": "2026-10-19T08:30:51.548385Z",
     "iopub.status.idle": "2026-10-19T08:30:51.551755Z",
     "shell.execute_reply": "2026-10-19T08:30:51.551402Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "наша таблица: [('а', 5), ('б', 2), ('р', 2), ('к', 1), ('д', 1)]\n",
      "dict:         {'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1}\n"
     ]
    }
   ],
   "source": [
    "# Частоты: наша таблица и встроенный словарь делают одно и то же.\n",
    "text = \"абракадабра\"\n",
    "\n",
    "t = HashTable(hash_fn=hash_str)\n",
    "for ch in text:\n",
    "    t.put(ch, t.get(ch, 0) + 1)\n",
    "\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"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-034",
   "metadata": {},
   "source": [
    "**Итог.** Словарь и множество дают $O(1)$ в среднем на `put`, `get` и `remove`. Плата — память $\\Theta(n+m)$ и зависимость от равномерности хеша: в худшем случае одна цепочка даёт $\\Theta(n)$.\n",
    "\n",
    "Частоты элементов — уже собранный пример: `put(x, get(x, 0) + 1)`. Пару с суммой $k$ и сравнение с встроенным словарём разберём на семинаре 8.\n",
    "\n",
    "В коллоквиуме 2 спрашиваются хеш-функция, коллизии и разница между средним и наихудшим временем.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "lec08-036",
   "metadata": {},
   "source": [
    "## Материалы\n",
    "\n",
    "- Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, гл. 11 «Hash Tables» — цепочки, открытая адресация, коэффициент заполнения.\n",
    "- Goodrich M. T., Tamassia R., Goldwasser M. H. Data Structures and Algorithms in Python. Wiley, 2013 — ADT словаря и хеш-таблицы.\n",
    "- Документация Python: `dict`, `set`, `hash()`; примечание о рандомизации хешей строк и `PYTHONHASHSEED`.\n",
    "- Опираемся на лекцию 7 (`sem1/07/lecture.ipynb`) и семинар 4 (`sem1/04/seminar.ipynb`).\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
}