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

Хеш таблица

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

Проблем

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

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

PriceTable cache = new PriceTable(key -> key.charAt(0));

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

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

Идеята

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

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

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

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

String[] keys = { "Иван", "Мария", "Петър", "Ана" };
int buckets = 8;
for (String key : keys) {
    int hash = key.hashCode();
    int index = Math.floorMod(hash, buckets);
    System.out.println(key + " -> " + hash + " -> кофа " + index);
}
Стъпка по стъпка, с думи
  1. Четири ключа и осем празни кофи с номера от 0 до 7.
  2. „Иван“.hashCode() е 32287399. Остатъкът при деление на 8 е 7: това е кофата.
  3. „Мария“ дава 1004560195, кофа 3.
  4. „Петър“ дава 1007482178, кофа 2.
  5. „Ана“ също е в кофа 3: колизия. Двата ключа са в една кофа: „Ана“ се закача след „Мария“ като верига.
  6. Търсене на „Ана“: същото число, същата кофа 3. equals с „Мария“: не. С „Ана“: да.

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

Виж го

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

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

static int skuHash(String key) {
    int h = 0;
    for (int i = 0; i < key.length(); i++) {
        h = 31 * h + key.charAt(i);
    }
    return h & 0x7fffffff;
}

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

class Entry {
    final String key;
    double price;
    Entry next;


    Entry(String key, double price, Entry next) {
        this.key = key;
        this.price = price;
        this.next = next;
    }
}

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

class PriceTable {
    private final ToIntFunction<String> hash;
    private Entry[] buckets = new Entry[4];
    private int size = 0;
    long compares = 0;


    PriceTable(ToIntFunction<String> hash) {
        this.hash = hash;
    }


    int capacity() {
        return buckets.length;
    }


    private int index(String key) {
        return hash.applyAsInt(key) % buckets.length;
    }


    void put(String key, double price) {
        int i = index(key);
        for (Entry e = buckets[i]; e != null; e = e.next) {
            compares++;
            if (e.key.equals(key)) {
                e.price = price;
                return;
            }
        }
        buckets[i] = new Entry(key, price, buckets[i]);
        size++;
        if (size > buckets.length * 3 / 4) resize();
    }


    private void resize() {
        Entry[] fresh = new Entry[buckets.length * 2];
        for (Entry head : buckets) {
            for (Entry e = head; e != null; e = e.next) {
                int i = hash.applyAsInt(e.key) % fresh.length;
                fresh[i] = new Entry(e.key, e.price, fresh[i]);
            }
        }
        buckets = fresh;
    }


    Double get(String key) {
        int i = index(key);
        for (Entry e = buckets[i]; e != null; e = e.next) {
            compares++;
            if (e.key.equals(key)) return e.price;
        }
        return null;
    }
}
  • put минава по веригата на кофата. Ако ключът е там, сменя цената. Ако не е, слага нова двойка в началото на веригата: това не иска обхождане.
  • get минава по същата верига и спира при ключа.

Пробвай

Попълни

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

return hash.applyAsInt(key) % ;

Идеята

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

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

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

private int index(String key) {
    return hash.applyAsInt(key) % buckets.length;
}


void put(String key, double price) {
    int i = index(key);
    for (Entry e = buckets[i]; e != null; e = e.next) {
        compares++;
        if (e.key.equals(key)) {
            e.price = price;
            return;
        }
    }
    buckets[i] = new Entry(key, price, buckets[i]);
    size++;
    if (size > buckets.length * 3 / 4) resize();
}


private void resize() {
    Entry[] fresh = new Entry[buckets.length * 2];
    for (Entry head : buckets) {
        for (Entry e = head; e != null; e = e.next) {
            int i = hash.applyAsInt(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, но е рядко.
PriceTable cache = new PriceTable(Main::skuHash);
cache.put("SKU-1003", 24.9);
cache.put("SKU-1001", 12.5);
cache.put("SKU-1007", 8.99);
cache.printBuckets();
System.out.println("---");
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 кофи. Седем продукта влизат един след друг:

PriceTable cache = new PriceTable(Main::skuHash);
StringBuilder caps = new StringBuilder();
for (int n = 2001; n <= 2007; n++) {
    cache.put("SKU-" + n, 10);
    caps.append(cache.capacity()).append(" ");
}
System.out.println(caps.toString().trim());
Отговор

Идеята

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

Обратно към кеша. Хешът „първата буква“ дава 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;
}
System.out.println("първата буква: " + compares(new PriceTable(key -> key.charAt(0)), 1000));
System.out.println("целия SKU: " + compares(new PriceTable(Main::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() {
    Entry[] fresh = new Entry[buckets.length * 2];
    for (Entry head : buckets) {
        for (Entry e = head; e != null; e = e.next) {
            int i = hash.applyAsInt(e.key) % buckets.length;
            fresh[i] = new Entry(e.key, e.price, fresh[i]);
        }
    }
    buckets = fresh;
}
PriceTable cache = new PriceTable(Main::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);
Double p1003 = cache.get("SKU-1003");
System.out.println("SKU-1003: " + (p1003 == null ? "няма" : p1003));
Double p1001 = cache.get("SKU-1001");
System.out.println("SKU-1001: " + (p1001 == null ? "няма" : p1001));
Double p1007 = cache.get("SKU-1007");
System.out.println("SKU-1007: " + (p1007 == null ? "няма" : p1007));
Double p1005 = cache.get("SKU-1005");
System.out.println("SKU-1005: " + (p1005 == null ? "няма" : p1005));
Изход
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 за достъпно обучение по програмиране ·