Co je hashtable?

V počítačové vědě je hashtable struktura dat pro ukládání dat, která se skládá ze seznamu hodnot, nazývaných klíče, které se spárují s odpovídajícím seznamem hodnot, nazývané pole.Například obchodní jméno by se mohlo spárovat s jeho adresou.Každá hodnota v poli má obvykle číslo pozice označované jako hash.Funkce hash je obecně sada pokynů nebo algoritmu, který mapuje každou hodnotu klíče k hash mdash;Například připojení obchodního názvu s jeho adresou, jeho telefonní číslo a obchodní kategorii.Účelem funkce hash je přiřadit každou klíč k jedinečné odpovídající hodnotě v poli;Toto se běžně označuje jako hashování.Funkce hash musí být správně naformátovány, aby hashtable fungovala správně.

Výkon hashtable na sadě dat závisí na účinnosti její hashové funkce.Dobrá hashová funkce obvykle poskytuje jednotné vyhledávání klíčů a rovnoměrné rozdělení mapování v odpovídajícím poli.Kolize hash dochází, když jsou dvě klíče přiřazeny ke stejné odpovídající hodnotě.Když dojde k kolizi hash, funkce hash se obvykle provádí znovu, dokud není nalezena jedinečná odpovídající hodnota;To obvykle vede k delším hashovacím časům.Ačkoli počet klíčů v hashtable je obvykle pevný, někdy by mohly existovat duplicitní klíče.Přesto dobře navržený hashtable má účinné hashovací funkce, které mapují každý klíč k jedinečné odpovídající hodnotě v poli.

Někdy mohou neefektivní funkce hash v hashtable také vytvořit shluk mapování.Pokud funkce hash vytvoří shluk mapování pro existující klíče, může to prodloužit množství času potřebného k vyhledání odpovídajících hodnot.To může zpomalit hashování pro budoucí klíče, protože většina funkcí hash obecně hledá další dostupnou pozici v poli.Pokud již byl přiřazen velký shluk hodnot, obvykle by hledalo nepřiřazenou hodnotu pro nový klíč mnohem déle.

Faktor zatížení je další koncept související s účinností funkce hash;Faktorem zatížení je množství již existujících hasů ve vztahu k celkové velikosti odpovídajícího pole v hashtable.Obvykle je definován dělením počtu již přiřazených klíčů velikostí odpovídajícího pole.Jak se faktor zatížení zvyšuje, dobrá funkce hash bude obvykle stále udržovat konstantní počet kolizí a shluků až do určitého bodu.Tento práh lze často použít k určení, jak efektivní je funkce hash s daným počtem klíčů a kdy může být potřeba nová hashová funkce.ten, který nevytváří žádné kolize ani klastry vzhledem k rostoucímu faktoru zátěže.Teoreticky je klíčem k vytvoření dokonalého hashtable vytvořit perfektní hashovou funkci.Vědci obecně věří, že dokonalá funkce hash by měla mít neustálý výkon a mdash;počet kolizí a shluků a mdash;se zvyšujícím se faktorem zátěže.V nejhorších scénářích by perfektní hashovací funkce stále umožňovala neustálý hashování bez dosažení prahu.