Hash table

avg O(1)

Hash tabulka ukládá hodnoty do pole kbelíků a kbelík vybírá hashovací funkcí (tady h(v) = v mod 7). Insert, search i delete skočí rovnou do kbelíku h(v) — v průměru O(1) — a když dvě hodnoty padnou do stejného kbelíku (kolize), drží se v malém řetězu, který se prochází lineárně. Dobré hashování drží řetězy krátké; takhle se staví slovníky a množiny.

Hash tabulka
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Spočítej index kbelíku hashovací funkcí h(v).
  2. Insert přidá v do řetězu toho kbelíku (duplicity přeskočí).
  3. Search a delete procházejí jen řetěz daného kbelíku.
  4. Kolize (stejný kbelík) se řetězí — pro O(1) je drž krátké.

Pseudokód

1h(v) = v mod m                      # m buckets, here 723insert(v): add v to the chain at bucket h(v)   # avg O(1)4search(v): scan the chain at bucket h(v)5delete(v): unlink v from the chain at bucket h(v)6# collisions share a bucket as a linked chain