Неделя 8

Лекция. Хеш-таблицы и хеш-функции

скачать .ipynb

Лекция 8. Хеш-таблицы и хеш-функции

На прошлой лекции мы собирали стек, очередь и дек: один интерфейс — разные реализации. Сегодня то же самое для словаря и множества, но цена операций важнее: хочется, чтобы и вставка, и поиск стоили $O(1)$ в среднем.

Опираемся на лекцию 7 (ADT, class, Stack, RingQueue) и семинар 4 (lower_bound). Частотный массив из недели 2 — тот же приём «значение как индекс»; теперь ключ не обязан быть маленьким целым.

dict и set в общем пользовании до этой пары нет: словарь собираем сами. Встроенные dict / set показываем в конце как эталон интерфейса — после пары ими можно пользоваться как рабочим инструментом.

План

  1. Множество на неупорядоченном и упорядоченном списке: таблица цен.
  2. Словарь как ADT: интерфейс, контракт, хешируемость; множество как частный случай.
  3. Хеш-функции: требования, примеры для чисел и строк, равномерность, плохие функции.
  4. Своя class HashTable: метод цепочек, инвариант, цена $O(1+\alpha)$.
  5. Коэффициент заполнения $\alpha$: перехеширование, амортизация, среднее против худшего.
  6. Открытая адресация: линейное пробирование, кластеры, tombstone — идея.
  7. dict / set как эталон интерфейса и мост к семинару 8.

0. Проблематизация: множество на списке

ADT «множество»: add(x), contains(x), remove(x). Контракт простой: элемент либо есть, либо нет; повторное добавление ничего не меняет.

Сначала честный неупорядоченный список. Все три операции просматривают данные целиком — в худшем случае $\Theta(n)$.

In [1]:
class SetOnList:
    def __init__(self):
        self.data = []

    def add(self, x):
        if x not in self.data:      # проверка дубликата — O(n)
            self.data.append(x)

    def contains(self, x):
        return x in self.data       # O(n)

    def remove(self, x):
        self.data.remove(x)         # O(n)

    def __repr__(self):
        return f"SetOnList({self.data!r})"


s = SetOnList()
for x in (3, 1, 3, 2):
    s.add(x)
print(s)                 # повтор 3 не добавился
print(s.contains(2))     # True
s.remove(1)
print(s)

SetOnList([3, 1, 2])
True
SetOnList([3, 2])

Теперь тот же ADT, но данные поддерживаются упорядоченными. Поиск идёт бинарным поиском через lower_bound с семинара 4, зато add обязан найти позицию и сдвинуть хвост.

In [2]:
class SortedSetOnList:
    def __init__(self):
        self.data = []

    def _lower_bound(self, x):
        lo, hi = 0, len(self.data)
        while lo < hi:
            mid = (lo + hi) // 2
            if self.data[mid] < x:
                lo = mid + 1
            else:
                hi = mid
        return lo

    def contains(self, x):
        i = self._lower_bound(x)
        return i < len(self.data) and self.data[i] == x

    def add(self, x):
        i = self._lower_bound(x)
        if i == len(self.data) or self.data[i] != x:
            self.data.insert(i, x)  # сдвиг хвоста — Θ(n)

    def remove(self, x):
        i = self._lower_bound(x)
        if i < len(self.data) and self.data[i] == x:
            self.data.pop(i)        # сдвиг хвоста — Θ(n)
        else:
            raise KeyError(x)

    def __repr__(self):
        return f"SortedSetOnList({self.data!r})"


s = SortedSetOnList()
for x in (3, 1, 2, 1):
    s.add(x)
print(s)                 # данные упорядочены, повтор 1 не добавлен
print(s.contains(2))     # True
s.remove(1)
print(s)

SortedSetOnList([1, 2, 3])
True
SortedSetOnList([2, 3])

Таблица цен — из неё весь дальнейший сюжет:

ОперацияНеупорядоченный списокУпорядоченный список
add$O(1)$ без проверки дубликата, $O(n)$ с проверкой$O(n)$: поиск $O(\log n)$, но сдвиг $\Theta(n)$
contains$O(n)$$O(\log n)$
remove$O(n)$$O(n)$: поиск $O(\log n)$, но сдвиг $\Theta(n)$

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

Та же дилемма была на неделе 7: у стека и очереди один интерфейс и разные реализации, и цена операции зависела от реализации. Здесь сравниваем две реализации одного ADT.

1. Словарь как ADT

Словарь (ассоциативный массив, map) хранит пары «ключ → значение». Интерфейс:

  • put(key, value) — вставить или обновить;
  • get(key) — вернуть значение, при отсутствии — KeyError;
  • contains(key) — есть ли ключ;
  • remove(key) — удалить пару;
  • len(table) — число ключей.

Контракт. Ключи уникальны; put по существующему ключу обновляет значение, а не добавляет вторую пару; множество — частный случай, где значение не нужно.

В Python у встроенного словаря тот же интерфейс, только короче: d[k], d.get(k), k in d, del d[k]. Наша таблица повторяет смысл, а не синтаксис.

Та же мысль, что на лекции 7: ADT — это интерфейс и контракт, представление выбираем сами. Сегодня интерфейс словаря, представление — хеш-таблица.

Ключ обязан быть хешируемым. int, str, tuple из хешируемых — да; list, dict, set — нет. Причина: таблица опирается на неизменность ключа. Если ключ изменить после вставки, он окажется не в своём бакете, и найти его будет нельзя.

2. Хеш-функции

Идея: превратить ключ в индекс массива. Хеш-функция $h(key)$ отображает ключ в число, индекс бакета — $h(key) \bmod m$.

Требования:

  1. Детерминизм — одинаковый ключ даёт одинаковый индекс.
  2. Быстрота — не зависит от числа элементов таблицы; от длины ключа зависит линейно, и это единственная плата.
  3. Равномерность — похожие ключи попадают в разные бакеты.
  4. Согласованность с равенством — если a == b, то h(a) == h(b); обратное не требуется.

Для целых напрашивается само число по модулю $m$. Для строк — полиномиальная свёртка: считаем строку числом в системе счисления с основанием 31.

In [3]:
MOD = 2**31 - 1          # большой простой модуль: числа не растут с длиной строки


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


for word in ("кот", "ток", "кто"):
    code = hash_str(word)
    print(f"{word}: хеш = {code:>10}, индекс при m = 101: {code % 101:>3}")

кот: хеш =    1074558, индекс при m = 101:  19
ток: хеш =    1082238, индекс при m = 101:  23
кто: хеш =    1074678, индекс при m = 101:  38

hash_str возвращает хеш-код — большое число. Индекс бакета получается из него отдельно: hash_str(key) % m. Внутри многочлена остаток берётся по большому простому модулю, иначе число растёт с длиной строки и длинная арифметика съедает выигрыш.

Почему 31? Традиция: множитель не 1 и не чётный; 31 хорошо перемешивает соседние коды символов. Другие нечётные основания (37, 131) работают так же.

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

Хеш-код и индекс — разные вещи: одинаковый хеш-код при разных $m$ даёт разные индексы, а разные хеш-коды могут дать один индекс. Коллизия индексов — нормальная ситуация, а не ошибка.

Полезное следствие: если h(a) != h(b), ключи точно разные. А h(a) == h(b) ничего не говорит о равенстве — это коллизия.

In [4]:
import random
import string


def hash_len(s):
    return len(s)


def hash_first(s):
    return ord(s[0])


def hash_const(s):
    return 0


random.seed(42)
words = []
while len(words) < 1000:
    word = "".join(random.choice(string.ascii_lowercase) for _ in range(5))
    if word not in words:
        words.append(word)

M = 101      # простое число: распределение видно, цепочки короткие


def report(name, keys, hash_fn, m):
    counts = [0] * m
    for key in keys:
        counts[hash_fn(key) % m] += 1
    used = 0
    for c in counts:
        if c:
            used += 1
    average = sum(counts) / used
    print(f"{name:<18} занято {used:>3} из {m}, "
          f"средняя непустого {average:>6.1f}, максимум {max(counts):>4}")


print(f"1000 слов по {M} бакетам, alpha = {1000 / M:.1f}")
report("полиномиальная", words, hash_str, M)
report("len(s)", words, hash_len, M)
report("ord(s[0])", words, hash_first, M)
report("константа", words, hash_const, M)

1000 слов по 101 бакетам, alpha = 9.9
полиномиальная     занято 101 из 101, средняя непустого    9.9, максимум   18
len(s)             занято   1 из 101, средняя непустого 1000.0, максимум 1000
ord(s[0])          занято  26 из 101, средняя непустого   38.5, максимум   48
константа          занято   1 из 101, средняя непустого 1000.0, максимум 1000

Числа показывают, что «равномерно» — свойство распределения, а не лозунг:

  • полиномиальная функция занимает все 101 бакет, максимум 18 при среднем 9.9;
  • len(s) сваливает все слова длины 5 в одну цепочку из 1000;
  • ord(s[0]) использует только первую букву: занято 26 бакетов, максимум 48;
  • константа — вся таблица в одной цепочке, это худший случай.

Средняя длина по всем бакетам всегда равна $n/m \approx 9.9$ — по ней равномерность не проверишь. Смотрим на занятость, максимум и разброс.

Бакетов 101, а не 10: при малом $m$ средняя цепочка $n/m$ велика, и различия между функциями смазаны. На большом $m$ видно, что len(s) и ord(s[0]) теряют информацию о ключе.

Подбор ключей под известную хеш-функцию сваливает всё в одну цепочку. Поэтому в Python хеши строк рандомизированы при запуске: подбирать под них ключи заранее нельзя.

In [5]:
import subprocess
import sys

print("в текущем процессе:", hash("строка"))

for _ in range(3):
    result = subprocess.run(
        [sys.executable, "-c", "print(hash('строка'))"],
        capture_output=True,
        text=True,
    )
    print("в новом процессе:", result.stdout.strip())

в текущем процессе: -2543911540180361055
в новом процессе: 4637504618212963118
в новом процессе: -8958671136431960088
в новом процессе: 2924240912931008508

Встроенный hash() для строк рандомизирован при запуске (PYTHONHASHSEED): в одном процессе значение постоянно, в новом — другое. Для таблицы это нормально и защищает от подбора ключей; для воспроизводимых демонстраций — нет. Поэтому в ноутбуке хеш-функция передаётся в таблицу параметром: HashTable(hash_fn=hash_str).

Для целых hash(x) == x, поэтому в демонстрациях ниже это удобно. Но именно поэтому степень двойки в $m$ опасна: номер бакета определяется младшими битами.

id() как хеш не подходит: у равных строк адреса разные, и требование a == b ⇒ h(a) == h(b) нарушается.

3. Своя class HashTable: метод цепочек

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

Параметр hash_fn нужен для демонстраций: таблица не зависит от конкретной хеш-функции. По умолчанию — встроенный hash.

In [6]:
_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):
        bucket = self.data[self._index(key)]
        for i in range(len(bucket)):
            k = bucket[i][0]
            if k == key:                 # ключ уже есть — обновляем
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > self.LOAD_LIMIT * len(self.data):
            self._resize()

    def get(self, key, default=_MISSING):
        bucket = self.data[self._index(key)]
        for k, v in bucket:  # O(len(bucket))
            if k == key:
                return v
        if default is not _MISSING:      # второй аргумент передан явно
            return default
        raise KeyError(key)

    def contains(self, key):
        for k, _ in self.data[self._index(key)]:
            if k == key:
                return True
        return False

    def remove(self, key):
        bucket = self.data[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)  # O(len(bucket))
                self.size -= 1
                return
        raise KeyError(key)

    def _resize(self):
        old = self.data
        self.data = [[] for _ in range(2 * len(old))]
        self.size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)

    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 = 0
        for length in lengths:
            if length:
                used += 1
        print(f"m = {len(lengths):>5}, n = {self.size:>5}, "
              f"alpha = {self.size / len(lengths):.2f}, "
              f"занято {used:>5}, max цепочка = {max(lengths)}")

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

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

Пара в бакете — кортеж (ключ, значение), поэтому при обновлении заменяем её целиком: bucket[i] = (key, value).

_MISSING — служебная метка: она позволяет отличить «второй аргумент не передан» от default=None. Иначе отсутствие ключа и сохранённое значение None были бы неразличимы.

describe — вспомогательный метод для печати статистики; к интерфейсу словаря он не относится.

Посмотрим на примере: $m = 8$, несколько ключей, обновление, KeyError, удаление из середины цепочки.

In [7]:
t = HashTable(8, hash_fn=hash_str)
for i, key in enumerate(("яблоко", "банан", "вишня", "груша", "слива", "киви")):
    t.put(key, i + 1)

print(t)
print(t.data)                 # видно, какие ключи попали в один бакет
print("get('вишня') =", t.get("вишня"))

HashTable(8 бакетов, 6 ключей)
[[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 3), ('слива', 5), ('киви', 6)], [], [('груша', 4)], []]
get('вишня') = 3
In [8]:
t.put("вишня", 100)           # обновление, а не вторая пара
print("после put('вишня', 100):", t.data)

после put('вишня', 100): [[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 100), ('слива', 5), ('киви', 6)], [], [('груша', 4)], []]
In [9]:
print("contains('айва') =", t.contains("айва"))
print("get('айва', 0) =", t.get("айва", 0))
try:
    t.get("айва")
except KeyError as err:
    print("KeyError:", err)

contains('айва') = False
get('айва', 0) = 0
KeyError: 'айва'
In [10]:
t.remove("слива")
print("после remove('слива'):", t.data)
print("len(t) =", len(t))

после remove('слива'): [[('яблоко', 1)], [], [], [('банан', 2)], [('вишня', 100), ('киви', 6)], [], [('груша', 4)], []]
len(t) = 5

Цена: put, get, remove стоят $O(1 + \text{длина цепочки})$. При равномерном хеше и коэффициенте заполнения $\alpha = n/m$ средняя длина цепочки — $\alpha$, итого $O(1+\alpha)$.

Почему $m$ лучше брать простым? Если $m$ — степень двойки, номер бакета определяется только младшими битами хеша. Любая закономерность в них (например, все ключи кратны 8) сваливает ключи в один бакет. Простое $m$ перемешивает все биты. Степень двойки тоже годится, но тогда хеш нужно дополнительно перемешивать — так и сделано в dict Python.

Ключи сравниваем через ==, а не is: равные строки не обязаны быть одним объектом. В Python % от отрицательного числа неотрицателен, поэтому индекс бакета не уйдёт в минус.

In [11]:
keys = [8 * i for i in range(100)]      # кратны 8; для целых hash(key) == key

for m in (8, 97):
    counts = [0] * m
    for key in keys:
        counts[key % m] += 1
    used = 0
    for c in counts:
        if c:
            used += 1
    print(f"m = {m:>3}: занято {used:>3} бакетов, max = {max(counts)}")

m =   8: занято   1 бакетов, max = 100
m =  97: занято  97 бакетов, max = 2

4. Коэффициент заполнения и перехеширование

Коэффициент заполнения $\alpha = n/m$: сколько в среднем пар приходится на бакет. Ожидаемое время операции — $O(1+\alpha)$; при $\alpha$, близком к единице, цепочки растут, и константа в оценке перестаёт быть константой.

Правило: когда $\alpha$ превышает порог (в коде LOAD_LIMIT = 0.75), удваиваем $m$ и перекладываем все пары заново. Старые индексы недействительны: изменился модуль. Это _resize.

Стоимость: одна операция put в момент роста стоит $\Theta(n)$, но такие операции редки. Амортизированно выходит $O(1)$ — та же логика, что у list.append на лекции 2.

In [12]:
import random

random.seed(42)
keys = random.sample(range(1_000_000), 10_000)

t = HashTable(hash_fn=hash)
last_m = len(t.data)
for key in keys:
    t.put(key, key * key)
    if len(t.data) != last_m:       # таблица только что выросла
        last_m = len(t.data)
        t.describe()

print("итог:")
t.describe()

m =    16, n =     7, alpha = 0.44, занято     5, max цепочка = 2
m =    32, n =    13, alpha = 0.41, занято    11, max цепочка = 2
m =    64, n =    25, alpha = 0.39, занято    20, max цепочка = 2
m =   128, n =    49, alpha = 0.38, занято    41, max цепочка = 2
m =   256, n =    97, alpha = 0.38, занято    81, max цепочка = 2
m =   512, n =   193, alpha = 0.38, занято   164, max цепочка = 4
m =  1024, n =   385, alpha = 0.38, занято   321, max цепочка = 3
m =  2048, n =   769, alpha = 0.38, занято   638, max цепочка = 4
m =  4096, n =  1537, alpha = 0.38, занято  1281, max цепочка = 4
m =  8192, n =  3073, alpha = 0.38, занято  2574, max цепочка = 4
m = 16384, n =  6145, alpha = 0.38, занято  5154, max цепочка = 5
итог:
m = 16384, n = 10000, alpha = 0.61, занято  7530, max цепочка = 6

$\alpha$ держится ниже 0.75: сразу после удвоения она около 0.4, к следующему росту поднимается к 0.75. Максимальная цепочка — единицы: на 10 000 ключей она не больше 6. Это и есть «$O(1)$ в среднем» на практике: не потому, что коллизий нет, а потому, что их немного и они короткие.

Среднее против худшего:

Среднее (равномерный хеш)Худшее
put / get / remove$O(1+\alpha)$, амортизированно $O(1)$$\Theta(n)$: все ключи в одной цепочке
Память$\Theta(n+m)$$\Theta(n+m)$

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

Худший случай: ёмкость $m = 1024$, все ключи кратны 1024. Формально $\alpha \approx 0.5$, а фактически вся таблица — одна цепочка.

In [13]:
worst = HashTable(1024, hash_fn=hash)
for i in range(500):
    worst.put(1024 * i, i)

worst.describe()
print("длина первой цепочки:", len(worst.data[0]))

m =  1024, n =   500, alpha = 0.49, занято     1, max цепочка = 500
длина первой цепочки: 500

$\alpha$ маленькая, но это не спасает: все 500 ключей лежат в одной цепочке, и каждый поиск просматривает до 500 пар, хотя формально $\alpha \approx 0.5$. Оценка $O(1+\alpha)$ держится в предположении равномерного хеша; при подборе ключей предположение нарушено.

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

Другой способ разрешения коллизий: цепочек нет, все пары лежат в самом массиве. Если ячейка h(key) % m занята, идём дальше по правилу, например (h(key) + i) % m — линейное пробирование. Поиск идёт той же последовательностью, пока не найдёт ключ или пустую ячейку.

В примере ниже храним только ключи: для картинки коллизий этого достаточно. Массив из 8 ячеек заполняется несколькими вставками — видно, как образуются кластеры, подряд занятые ячейки. Чем выше $\alpha$, тем длиннее пробы; при $\alpha \to 1$ линейное пробирование деградирует.

In [14]:
M = 8
slots = [None] * M


def insert_linear(key):
    start = key % M
    for step in range(M):
        pos = (start + step) % M
        if slots[pos] is None:
            slots[pos] = key
            print(f"ключ {key:>3}: старт {start:>2}, проб {step + 1}, слот {pos:>2}")
            return pos
    raise OverflowError("таблица заполнена")


def find_linear(key):
    start = key % M
    for step in range(M):
        pos = (start + step) % M
        if slots[pos] is None:
            return None
        if slots[pos] == key:
            return pos
    return None


for key in (0, 8, 16, 24, 7, 15, 23):
    insert_linear(key)
print(slots)
print("ищем 16:", find_linear(16))
print("ищем 5:", find_linear(5))

ключ   0: старт  0, проб 1, слот  0
ключ   8: старт  0, проб 2, слот  1
ключ  16: старт  0, проб 3, слот  2
ключ  24: старт  0, проб 4, слот  3
ключ   7: старт  7, проб 1, слот  7
ключ  15: старт  7, проб 6, слот  4
ключ  23: старт  7, проб 7, слот  5
[0, 8, 16, 24, 15, 23, None, 7]
ищем 16: 2
ищем 5: None

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

In [15]:
print("удаляем 8: просто очищаем ячейку 1")
slots[1] = None
print("ищем 16 после удаления:", find_linear(16))
print(slots)

удаляем 8: просто очищаем ячейку 1
ищем 16 после удаления: None
[0, None, 16, 24, 15, 23, None, 7]

16 лежит в ячейке 2, но поиск стартует с 0, видит пустую ячейку 1 и делает вывод «ключа нет». С tombstone ячейка 1 осталась бы помеченной, поиск прошёл бы дальше и нашёл 16.

Сравнение с цепочками:

ЦепочкиОткрытая адресация
Коллизиипары в одном бакетепробы по массиву
$\alpha$может быть $>1$обязана быть $<1$
Удалениепросто убрать из списканужен tombstone
Памятьсписок в каждом бакете и парытолько массив ячеек
Локальностьхужелучше

В Python dict устроен как открытая адресация с перемешиванием, но это деталь реализации, а не интерфейса.

6. dict / set как эталон и к семинару 8

Сопоставим интерфейс:

Наша таблицаВстроенный dict
put(k, v)d[k] = v
get(k) / get(k, default)d[k] / d.get(k, default)
contains(k)k in d
remove(k)del d[k]
len(t)len(d)

set — то же самое без значений. У встроенного словаря есть ещё итерация, keys / values / items и порядок вставки; наша таблица этого не обещает.

Правило курса: dict и set — эталон интерфейса и рабочий инструмент после этой пары, но не замена собственной реализации в упражнениях семинара.

In [16]:
d = {}
d["яблоко"] = 3
d["банан"] = 5
print("d =", d)
print("d['яблоко'] =", d["яблоко"])
print("d.get('вишня') =", d.get("вишня"))
print("d.get('вишня', 0) =", d.get("вишня", 0))
print("'банан' in d:", "банан" in d, " len(d) =", len(d))

d["яблоко"] = 10
print("после обновления:", d)
del d["банан"]
print("после del:", d)

s = {3, 1, 2}
s.add(3)
print("s =", s, " 1 in s:", 1 in s, " len(s) =", len(s))
s.discard(1)
print("после discard(1):", s)

d = {'яблоко': 3, 'банан': 5}
d['яблоко'] = 3
d.get('вишня') = None
d.get('вишня', 0) = 0
'банан' in d: True  len(d) = 2
после обновления: {'яблоко': 10, 'банан': 5}
после del: {'яблоко': 10}
s = {1, 2, 3}  1 in s: True  len(s) = 3
после discard(1): {2, 3}

Порядок в set не обещан: {3, 1, 2} печатается как {1, 2, 3} — это не сортировка, а деталь реализации. У dict порядок вставки гарантирован, у множества — нет.

In [17]:
# Частоты: наша таблица и встроенный словарь делают одно и то же.
text = "абракадабра"

t = HashTable(hash_fn=hash_str)
for ch in text:
    t.put(ch, t.get(ch, 0) + 1)

freq = {}
for ch in text:
    freq[ch] = freq.get(ch, 0) + 1

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

наша таблица: [('а', 5), ('б', 2), ('р', 2), ('к', 1), ('д', 1)]
dict:         {'а': 5, 'б': 2, 'р': 2, 'к': 1, 'д': 1}

Итог. Словарь и множество дают $O(1)$ в среднем на put, get и remove. Плата — память $\Theta(n+m)$ и зависимость от равномерности хеша: в худшем случае одна цепочка даёт $\Theta(n)$.

Частоты элементов — уже собранный пример: put(x, get(x, 0) + 1). Пару с суммой $k$ и сравнение с встроенным словарём разберём на семинаре 8.

В коллоквиуме 2 спрашиваются хеш-функция, коллизии и разница между средним и наихудшим временем.

Материалы

  • Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms, гл. 11 «Hash Tables» — цепочки, открытая адресация, коэффициент заполнения.
  • Goodrich M. T., Tamassia R., Goldwasser M. H. Data Structures and Algorithms in Python. Wiley, 2013 — ADT словаря и хеш-таблицы.
  • Документация Python: dict, set, hash(); примечание о рандомизации хешей строк и PYTHONHASHSEED.
  • Опираемся на лекцию 7 (sem1/07/lecture.ipynb) и семинар 4 (sem1/04/seminar.ipynb).