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

Хеш таблица

Накратко: Хеш таблицата (Dictionary в C#) пази двойки ключ–стойност в кофи: хешът на ключа казва в коя кофа е, затова търсенето и добавянето са средно O(1).

Проблем

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

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

var cache = new PriceTable(key => key[0]);

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

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

Идеята

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

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

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

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

int[] keys = { 1007, 2043, 3010, 4051 };
int buckets = 8;
foreach (int key in keys)
{
    int hash = key.GetHashCode();
    int index = (hash % buckets + buckets) % buckets;
    Console.WriteLine(key + " -> " + hash + " -> кофа " + index);
}
Стъпка по стъпка, с думи
  1. Четири ключа (номера на поръчки) и осем празни кофи с номера от 0 до 7.
  2. 1007.GetHashCode() е самото число, 1007. Остатъкът при деление на 8 е 7: това е кофата.
  3. 2043 дава кофа 3.
  4. 3010 дава кофа 2.
  5. 4051 също е в кофа 3: колизия. Двата ключа са в една кофа: 4051 се закача след 2043 като верига.
  6. Търсене на 4051: същото число, същата кофа 3. Equals с 2043: не. С 4051: да.

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

Виж го

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

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

static int SkuHash(string key)
{
    int h = 0;
    foreach (char c in key)
    {
        h = 31 * h + c;
    }
    return h & 0x7fffffff;
}

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

class Entry
{
    public readonly string Key;
    public double Price;
    public Entry? Next;


    public Entry(string key, double price, Entry? next)
    {
        Key = key;
        Price = price;
        Next = next;
    }
}

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

class PriceTable
{
    private readonly Func<string, int> hash;
    private Entry?[] buckets = new Entry?[4];
    private int size = 0;
    public long Compares { get; private set; }


    public PriceTable(Func<string, int> hash)
    {
        this.hash = hash;
    }


    public int Capacity => buckets.Length;


    private int Index(string key) => hash(key) % buckets.Length;


    public void Put(string key, double price)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            Compares++;
            if (e.Key == key)
            {
                e.Price = price;
                return;
            }
        }
        buckets[i] = new Entry(key, price, buckets[i]);
        size++;
        if (size > buckets.Length * 3 / 4) Resize();
    }


    private void Resize()
    {
        var fresh = new Entry?[buckets.Length * 2];
        foreach (var head in buckets)
        {
            for (var e = head; e != null; e = e.Next)
            {
                int i = hash(e.Key) % fresh.Length;
                fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
            }
        }
        buckets = fresh;
    }


    public double? Get(string key)
    {
        int i = Index(key);
        for (var e = buckets[i]; e != null; e = e.Next)
        {
            Compares++;
            if (e.Key == key) return e.Price;
        }
        return null;
    }
}
  • put минава по веригата на кофата. Ако ключът е там, сменя цената. Ако не е, слага нова двойка в началото на веригата: това не иска обхождане.
  • get минава по същата верига и спира при ключа.

Пробвай

Попълни

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

private int Index(string key) => hash(key) % ;

Идеята

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

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

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

private int Index(string key) => hash(key) % buckets.Length;


public void Put(string key, double price)
{
    int i = Index(key);
    for (var e = buckets[i]; e != null; e = e.Next)
    {
        Compares++;
        if (e.Key == key)
        {
            e.Price = price;
            return;
        }
    }
    buckets[i] = new Entry(key, price, buckets[i]);
    size++;
    if (size > buckets.Length * 3 / 4) Resize();
}


private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % fresh.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    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, но е рядко.
var cache = new PriceTable(SkuHash);
cache.Put("SKU-1003", 24.9);
cache.Put("SKU-1001", 12.5);
cache.Put("SKU-1007", 8.99);
cache.PrintBuckets();
Console.WriteLine("---");
cache.Put("SKU-1005", 45.5);
cache.PrintBuckets();
Изход
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 кофи. Седем продукта влизат един след друг:

var cache = new PriceTable(SkuHash);
var caps = new List<int>();
for (int n = 2001; n <= 2007; n++)
{
    cache.Put($"SKU-{n}", 10);
    caps.Add(cache.Capacity);
}
Console.WriteLine(string.Join(" ", caps));
Отговор

Идеята

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

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

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

static long Compares(PriceTable cache, int n)
{
    for (int i = 0; i < n; i++) cache.Put($"SKU-{10000 + i}", 1 + i);
    for (int i = 0; i < n; i++) cache.Get($"SKU-{10000 + i}");
    return cache.Compares;
}
Console.WriteLine($"първата буква: {Compares(new PriceTable(key => key[0]), 1000)}");
Console.WriteLine($"целия SKU: {Compares(new PriceTable(SkuHash), 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. Четирите продукта влизат, но два от тях после „ги няма“:

private void Resize()
{
    var fresh = new Entry?[buckets.Length * 2];
    foreach (var head in buckets)
    {
        for (var e = head; e != null; e = e.Next)
        {
            int i = hash(e.Key) % buckets.Length;
            fresh[i] = new Entry(e.Key, e.Price, fresh[i]);
        }
    }
    buckets = fresh;
}
var cache = new PriceTable(SkuHash);
cache.Put("SKU-1003", 24.9);
cache.Put("SKU-1001", 12.5);
cache.Put("SKU-1007", 8.99);
cache.Put("SKU-1005", 45.5);
Console.WriteLine($"SKU-1003: {cache.Get("SKU-1003")?.ToString() ?? "няма"}");
Console.WriteLine($"SKU-1001: {cache.Get("SKU-1001")?.ToString() ?? "няма"}");
Console.WriteLine($"SKU-1007: {cache.Get("SKU-1007")?.ToString() ?? "няма"}");
Console.WriteLine($"SKU-1005: {cache.Get("SKU-1005")?.ToString() ?? "няма"}");
Изход
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 за достъпно обучение по програмиране ·