Hashovací tabulka

  • Pro univerzum zvolíme konečnou množinu přihrádek (hash table),
  • hashovací funkci , která každému klíči přidělí jednu přihrádku
  • Mohou vznikat kolize
    • Z holubníkova principu víme, že pokud je univerzum velké, mohou existovat alespoň 2 prvky, které se zahashují stejně
  • Vhodné jako její velikost volit prvočíslo
  • Ideálně volit kapacitu klidně dvoj/trojnásobnou než počet prvků

Časová složitost ideálního hashování

  • Průměr počtů prvků v přihrádce je
  • Počet prvků v přihrádce je pro skoro všechny přihrádky
  • Průměrný počet operací vykonaných při hledání, vkládání i mazání je

Příklady dobrých hash. funkcí

Lineární kongruence

  • - velikost tabulky, typicky prvočíslo
  • - dostatečně velká konstanta nesoudělná s (často se nastavuje blízko celé části )

Vyšší bity součinu

  • Pokud hashujeme -bitové klíče do přihrádek, vybereme -bitovou lichou konstantu (nesoudělnou s )
  • Pro každé spočítáme , ořízneme ho na bitů a z nich vezmeme nejvyšších
  • Vzhledem k tomu, že ve většině jazycích přetečení automaticky ořezává výsledek, stačí k výpočtu jedno násobení a bitový posun

Skalární součin

  • (pozor, )
  • Posloupnost klíčů zahashujeme tak, že zahashujeme každý klíč zvlášť a výsledky sečteme
  • Pokud -tý klíč zahashujeme lineární kongruencí, je hashem celé posloupnosti její skalární součin s vektorem konstant
  • Podobně lze hash počítat ve dvojkové soustavě pomocí XORu místo součtu

Polynom

  • (pozor, )
  • Zvolíme jednu konstantu a počítáme skalární součin zadané posloupnosti s vektorem mocnin

Nafukovací hash tabulka a přehashování

  • Faktor naplnění
    • = počet prvků
    • = kapacita tabulky
  • Zvětšujeme zhruba 2x velikost, k nejbližšímu prvočíslu
  • Znovu přehashovat prvky z původní tabulky a vložit do nové

Řešení kolizí

  • Řetězení (chaining) - otevřené hashování (open hashing)
  • Otevřené adresování (open addressing) - uzavřené hashování (closed hashing)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25