Към съдържанието
wannacode

Хеш таблица

Накратко: Хеш таблицата (dict в Python) намира ключа по хеша му: хешът казва на кое място в таблицата да търси, затова търсенето и добавянето са средно O(1).

Проблем

Кешът на цените се бави

Страницата на продукта чете цената от кеш: таблица SKU → цена, която програмата пази в паметта. Някой е написал своя таблица PriceTable, с хеш функция, която „да е бърза“: само първата буква на SKU.

cache = PriceTable(lambda key: ord(key[0]))

С 20 продукта в теста всичко лети. С истинския каталог страницата се бави, а профилерът сочи get. При 1000 продукта, записани и прочетени по веднъж, таблицата прави 1 000 000 сравнения на ключове: по хиляда за продукт. Една hash таблица би трябвало да прави по едно-две.

Всички SKU започват със „S“. Какво става вътре?

Идеята

Кофи, хеш и номер на кофата

В урока „Хеш код и хеш функции“ видя таблицата отвън. Отвътре тя е три неща:

  • масив от кофи;
  • хеш функция, която прави от ключа цяло число;
  • номер на кофата = хеш % броя кофи. Така всеки ключ има точно едно място, където да го търсиш.

Два ключа с еднакъв номер на кофата са сблъсък. Тук сблъсъците стоят във верига: всяка кофа е начало на свързан списък от двойки ключ → стойност.

keys = [1007, 2043, 3010, 4051]
buckets = 8
for key in keys:
    h = hash(key)
    index = h % buckets
    print(f"{key} -> {h} -> кофа {index}")
Стъпка по стъпка, с думи
  1. Четири ключа (номера на поръчки) и осем празни кофи с номера от 0 до 7.
  2. hash(1007) е самото число, 1007. Остатъкът при деление на 8 е 7: това е кофата.
  3. 2043 дава кофа 3.
  4. 3010 дава кофа 2.
  5. 4051 също е в кофа 3: колизия. Тук е нарисувана като верига, както в Java. dict в CPython вместо това търси друго свободно място.
  6. Търсене на 4051: същото число, същата кофа 3. == с 2043: не. С 4051: да.

get смята кофата и минава само по нейната верига. Ако веригите са къси, това е O(1), колкото и ключове да има.

Виж го

Своята таблица

Хеш функцията за SKU е същата като hashCode на текст в Java: 31 · h + знак за всеки знак. Накрая се маха знакът, за да е числото неотрицателно:

def sku_hash(key):
    h = 0
    for c in key:
        h = (31 * h + ord(c)) & 0xFFFFFFFF
    return h & 0x7FFFFFFF
В Python цялото число няма горна граница, затова & 0xFFFFFFFF го държи в 32 бита при всяка стъпка, както препълването в Java. Така хешът е същият като на другите езици.

Двойката е възел с ключ, цена и стрелка към следващия във веригата:

class Entry:
    def __init__(self, key, price, next_entry):
        self.key = key
        self.price = price
        self.next = next_entry

Таблицата получава хеш функцията отвън, за да можеш да ги сравниш. compares брои сравненията на ключове:

class PriceTable:
    def __init__(self, hash_fn):
        self.hash = hash_fn
        self.buckets = [None] * 4
        self.size = 0
        self.compares = 0


    def index(self, key):
        return self.hash(key) % len(self.buckets)


    def put(self, key, price):
        i = self.index(key)
        e = self.buckets[i]
        while e is not None:
            self.compares += 1
            if e.key == key:
                e.price = price
                return
            e = e.next
        self.buckets[i] = Entry(key, price, self.buckets[i])
        self.size += 1
        if self.size > len(self.buckets) * 3 // 4:
            self.resize()


    def resize(self):
        fresh = [None] * (len(self.buckets) * 2)
        for head in self.buckets:
            e = head
            while e is not None:
                i = self.hash(e.key) % len(fresh)
                fresh[i] = Entry(e.key, e.price, fresh[i])
                e = e.next
        self.buckets = fresh


    def get(self, key):
        e = self.buckets[self.index(key)]
        while e is not None:
            self.compares += 1
            if e.key == key:
                return e.price
            e = e.next
        return None
  • put минава по веригата на кофата. Ако ключът е там, сменя цената. Ако не е, слага нова двойка в началото на веригата: това не иска обхождане.
  • get минава по същата верига и спира при ключа.

Пробвай

Попълни

Номерът на кофата:

return self.hash(key) %

Идеята

Load factor и разширяване

Колкото повече двойки, толкова по-дълги вериги. Отношението двойки / кофи се казва load factor. Тук, щом стане над 3/4, таблицата прави два пъти повече кофи.

Кофите не се копират едно към едно. Номерът на кофата е хеш % броя кофи, а броят се е сменил. Затова resize минава по всички двойки и смята кофата на всяка наново: това е преразпределяне (rehashing). При удвояване от 4 на 8 ключът от кофа b отива в b или в b + 4, и веригите се разделят.

def index(self, key):
    return self.hash(key) % len(self.buckets)


def put(self, key, price):
    i = self.index(key)
    e = self.buckets[i]
    while e is not None:
        self.compares += 1
        if e.key == key:
            e.price = price
            return
        e = e.next
    self.buckets[i] = Entry(key, price, self.buckets[i])
    self.size += 1
    if self.size > len(self.buckets) * 3 // 4:
        self.resize()


def resize(self):
    fresh = [None] * (len(self.buckets) * 2)
    for head in self.buckets:
        e = head
        while e is not None:
            i = self.hash(e.key) % len(fresh)
            fresh[i] = Entry(e.key, e.price, fresh[i])
            e = e.next
    self.buckets = fresh
Стъпка по стъпка, с думи
  1. Кеш на цените с 4 кофи. Кофата на ключа е хешът му % 4.
  2. SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Кофите са празни: без сравнения.
  3. SKU-1007 също пада в кофа 2: сблъсък. put го сравнява с SKU-1003 (не е същият ключ) и го слага в началото на веригата.
  4. SKU-1005 отива при SKU-1001 в кофа 0. Двойките вече са 4, повече от 3/4 от 4 кофи: веригите почват да растат.
  5. resize прави 8 кофи. Всеки ключ се смята наново с % 8: остава на номера си или отива с 4 нагоре.
  6. Новата таблица: всяка верига е с една двойка, затова get прави едно сравнение. Разширяването струва n, но е рядко.
cache = PriceTable(sku_hash)
cache.put("SKU-1003", 24.9)
cache.put("SKU-1001", 12.5)
cache.put("SKU-1007", 8.99)
cache.print_buckets()
print("---")
cache.put("SKU-1005", 45.5)
cache.print_buckets()
Изход
0: SKU-1001
1:
2: SKU-1007 SKU-1003
3:
---
0: SKU-1001
1:
2: SKU-1003
3:
4: SKU-1005
5:
6: SKU-1007
7:

Разширяването струва колкото броя двойки. Но става рядко: при 4, 8, 16… двойки, като растенето на масива в амортизираната сложност. Средно put остава O(1).

Пробвай

Колко кофи?

Таблицата започва с 4 кофи. Седем продукта влизат един след друг:

cache = PriceTable(sku_hash)
caps = []
for n in range(2001, 2008):
    cache.put(f"SKU-{n}", 10)
    caps.append(len(cache.buckets))
print(" ".join(str(c) for c in caps))
Отговор

Идеята

Лош хеш: таблицата става списък

Обратно към кеша. Хешът „първата буква“ дава 83 (кодът на „S“) за всеки SKU. 83 % 4, 83 % 8, 83 % 1024: при всеки брой кофи номерът е един. Всички двойки са в една верига, а таблицата е свързан списък, при който всеки put и всеки get минава през всички.

Разширяването не помага: то разделя веригите само ако ключовете имат различни хешове. Хеш функцията трябва да зависи от целия ключ и да разпръсква близките ключове (SKU-10000, SKU-10001) далеч един от друг.

def compares(cache, n):
    for i in range(n):
        cache.put(f"SKU-{10000 + i}", 1 + i)
    for i in range(n):
        cache.get(f"SKU-{10000 + i}")
    return cache.compares
print(f"първата буква: {compares(PriceTable(lambda key: ord(key[0])), 1000)}")
print(f"целия SKU: {compares(PriceTable(sku_hash), 1000)}")
Изход
първата буква: 1000000
целия SKU: 2593

Пусни двете таблици в браузъра:

  • Хеш от целия SKU O(n)
  • Хеш от първата буква O(n²)
Алгоритъмn = 10n = 1000n = 100 000
Хеш от целия SKU102593211 990
Хеш от първата буква1001 000 000≈ 10 000 000 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

При 1000 продукта мързеливият хеш прави 1 000 000 сравнения, а хешът от целия SKU 2593: под три на продукт. Мързеливият е O(n) на операция и O(n²) общо: n продукта, записани и прочетени по веднъж, правят точно n² сравнения.

По-точно, за любопитните

Open addressing (linear probing). Вместо вериги всички двойки стоят в самия масив. Ако мястото hash % n е заето, пробваш следващото, после по-следващото, докато намериш свободно или ключа. get върви по същия път и спира на празно място. Плюсът е, че всичко е в един масив и процесорът го чете подред. Минусите: заетите места се събират на купчини и всяка купчина расте все по-бързо, затова таблицата трябва да е по-празна (разширява се още при около половина или 2/3). Махането не може просто да изчисти мястото, защото ще прекъсне пътя към ключовете след него: слага се знак „изтрито“.

Как е в езиците:

  • Java HashMap: вериги. Кофите са степен на 2 (отначало 16), load factor 0,75. Към хеша се примесват горните битове (h ^ (h >>> 16)), защото с маска по степен на 2 иначе важат само долните. Верига с повече от 8 двойки става червено-черно дърво, ако кофите са поне 64 (иначе таблицата първо се разширява). Така дори при много сблъсъци търсенето е O(log n), а не O(n).
  • C# Dictionary<TKey, TValue>: също вериги, но в масиви: _buckets пази номера на първата двойка, а двойките в _entries имат индекс next. Броят кофи е просто число (3, 7, 17, 37, 89…), а разширява, когато масивът с двойките се напълни. Дърво като в Java няма. Срещу нарочни сблъсъци пази това, че хешът на текст е различен при всяко пускане.
  • Python dict: open addressing, но не с линейно пробване: следващото място се смята по формула, в която участват и горните битове на хеша. Таблицата е степен на 2 и се разширява, когато е пълна над 2/3. Двойките стоят в отделен плътен масив по реда на добавяне, а таблицата пази само индекси към него. Затова dict пази реда на добавяне (обещано от Python 3.7).
  • JavaScript Map: спецификацията иска обхождане по реда на добавяне и средно време под линейното, но не казва как. V8 ползва подредена hash таблица: кофи с вериги, а двойките стоят в масив по реда на добавяне. Свой хеш на обект JavaScript не дава: ключ-обект се сравнява по референция.

Пробвай

Намери грешката

Някой е преписал resize. Четирите продукта влизат, но два от тях после „ги няма“:

def resize(self):
    fresh = [None] * (len(self.buckets) * 2)
    for head in self.buckets:
        e = head
        while e is not None:
            i = self.hash(e.key) % len(self.buckets)
            fresh[i] = Entry(e.key, e.price, fresh[i])
            e = e.next
    self.buckets = fresh
cache = PriceTable(sku_hash)
cache.put("SKU-1003", 24.9)
cache.put("SKU-1001", 12.5)
cache.put("SKU-1007", 8.99)
cache.put("SKU-1005", 45.5)
p = cache.get("SKU-1003")
print(f"SKU-1003: {'няма' if p is None else p}")
p = cache.get("SKU-1001")
print(f"SKU-1001: {'няма' if p is None else p}")
p = cache.get("SKU-1007")
print(f"SKU-1007: {'няма' if p is None else p}")
p = cache.get("SKU-1005")
print(f"SKU-1005: {'няма' if p is None else p}")
Изход
SKU-1003: 24.9
SKU-1001: 12.5
SKU-1007: няма
SKU-1005: няма

На кой ред е грешката?

Избери реда с грешката.

Упражнение

Продуктът спира да се продава

Реши задачата в редактора си.

Махане от кеша. Добави в PriceTable метод remove(key), който маха двойката и връща дали е имало такава. Внимавай: двойката може да е първа във веригата (тогава кофата сочи следващата) или по средата (тогава предишната двойка сочи следващата). Сложи SKU-1001, SKU-1005, SKU-1009 и SKU-1012 с цени 10,5, 11,5, 12,5 и 13,5 €; след разширяването до 8 кофи три от тях са в кофа 0, а SKU-1009 е в средата на веригата. Махни SKU-1009 и прочети и четирите:

Изход
SKU-1001: 10.5
SKU-1005: 11.5
SKU-1009: няма
SKU-1012: 13.5
продукти: 3

Още задачи

  • Линейно пробване. Напиши ProbeTable без вериги: при заето място пробвай следващото. Разширявай при половин пълна таблица. Колко сравнения прави при 1000 SKU?
  • Свиване. След разпродажба кешът остава с 10 продукта и 4096 кофи. Кога би свил таблицата?
  • По-добрият мързелив хеш. Хешът „сборът от кодовете на знаците“ гледа целия ключ. Пробвай го със SKU-10000 до SKU-10999. Защо пак има много сблъсъци? (Подсказка: SKU-10019 и SKU-10091.)

Тест

Провери се

1. Таблицата има 8 кофи. Хешът на ключ е 1091696436. В коя кофа е?
2. Защо при разширяване всеки ключ се смята наново, вместо кофите просто да се копират?
3. Хеш функцията връща първата буква на SKU, а всички SKU започват със „S“. Колко струва get при n продукта?
4. Кое е вярно за dict в Python?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·