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

Хеш таблица

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

Проблем

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

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

const cache = new PriceTable((key) => key.charCodeAt(0));

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

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

Идеята

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

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

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

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

function hashOf(text) {
  let hash = 0;
  for (let i = 0; i < text.length; i++) {
    hash = (31 * hash + text.charCodeAt(i)) | 0;
  }
  return hash;
}


const keys = ["Иван", "Мария", "Петър", "Ана"];
const buckets = 8;
for (const key of keys) {
  const hash = hashOf(key);
  const index = ((hash % buckets) + buckets) % buckets;
  console.log(`${key} -> ${hash} -> кофа ${index}`);
}
Стъпка по стъпка, с думи
  1. Четири ключа и осем празни кофи с номера от 0 до 7.
  2. hashOf("Иван") е 32287399. Остатъкът при деление на 8 е 7: това е кофата.
  3. „Мария“ дава 1004560195, кофа 3.
  4. „Петър“ дава 1007482178, кофа 2.
  5. „Ана“ също е в кофа 3: колизия. Двата ключа са в една кофа: „Ана“ се закача след „Мария“ като верига.
  6. Търсене на „Ана“: същото число, същата кофа 3. === с „Мария“: не. С „Ана“: да.

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

Виж го

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

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

function skuHash(key) {
  let h = 0;
  for (let i = 0; i < key.length; i++) {
    h = (Math.imul(31, h) + key.charCodeAt(i)) | 0;
  }
  return h & 0x7fffffff;
}
Math.imul умножава като 32-битови цели числа, а | 0 връща резултата в 32 бита. Така хешът е същият като на другите езици.

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

class Entry {
  constructor(key, price, next) {
    this.key = key;
    this.price = price;
    this.next = next;
  }
}

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

class PriceTable {
  constructor(hash) {
    this.hash = hash;
    this.buckets = new Array(4).fill(null);
    this.size = 0;
    this.compares = 0;
  }


  index(key) {
    return this.hash(key) % this.buckets.length;
  }


  put(key, price) {
    const i = this.index(key);
    for (let e = this.buckets[i]; e !== null; e = e.next) {
      this.compares++;
      if (e.key === key) {
        e.price = price;
        return;
      }
    }
    this.buckets[i] = new Entry(key, price, this.buckets[i]);
    this.size++;
    const limit = Math.floor((this.buckets.length * 3) / 4);
    if (this.size > limit) this.resize();
  }


  resize() {
    const fresh = new Array(this.buckets.length * 2).fill(null);
    for (const head of this.buckets) {
      for (let e = head; e !== null; e = e.next) {
        const i = this.hash(e.key) % fresh.length;
        fresh[i] = new Entry(e.key, e.price, fresh[i]);
      }
    }
    this.buckets = fresh;
  }


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

Пробвай

Попълни

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

return this.hash(key) % ;

Идеята

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

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

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

index(key) {
  return this.hash(key) % this.buckets.length;
}


put(key, price) {
  const i = this.index(key);
  for (let e = this.buckets[i]; e !== null; e = e.next) {
    this.compares++;
    if (e.key === key) {
      e.price = price;
      return;
    }
  }
  this.buckets[i] = new Entry(key, price, this.buckets[i]);
  this.size++;
  const limit = Math.floor((this.buckets.length * 3) / 4);
  if (this.size > limit) this.resize();
}


resize() {
  const fresh = new Array(this.buckets.length * 2).fill(null);
  for (const head of this.buckets) {
    for (let e = head; e !== null; e = e.next) {
      const i = this.hash(e.key) % fresh.length;
      fresh[i] = new Entry(e.key, e.price, fresh[i]);
    }
  }
  this.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, но е рядко.
const 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.log("---");
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 кофи. Седем продукта влизат един след друг:

const cache = new PriceTable(skuHash);
const caps = [];
for (let n = 2001; n <= 2007; n++) {
  cache.put(`SKU-${n}`, 10);
  caps.push(cache.buckets.length);
}
console.log(caps.join(" "));
Отговор

Идеята

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

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

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

function compares(cache, n) {
  for (let i = 0; i < n; i++) cache.put(`SKU-${10000 + i}`, 1 + i);
  for (let i = 0; i < n; i++) cache.get(`SKU-${10000 + i}`);
  return cache.compares;
}
console.log(`първата буква: ${compares(new PriceTable((key) => key.charCodeAt(0)), 1000)}`);
console.log(`целия 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. Четирите продукта влизат, но два от тях после „ги няма“:

resize() {
  const fresh = new Array(this.buckets.length * 2).fill(null);
  for (const head of this.buckets) {
    for (let e = head; e !== null; e = e.next) {
      const i = this.hash(e.key) % this.buckets.length;
      fresh[i] = new Entry(e.key, e.price, fresh[i]);
    }
  }
  this.buckets = fresh;
}
const 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);
const p1003 = cache.get("SKU-1003");
console.log(`SKU-1003: ${p1003 ?? "няма"}`);
const p1001 = cache.get("SKU-1001");
console.log(`SKU-1001: ${p1001 ?? "няма"}`);
const p1007 = cache.get("SKU-1007");
console.log(`SKU-1007: ${p1007 ?? "няма"}`);
const p1005 = cache.get("SKU-1005");
console.log(`SKU-1005: ${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 за достъпно обучение по програмиране ·