Co je hashtable?
V informatice, hashtable je datová struktura 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ým 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 - připojení obchodního názvu na jeho adresu, jeho telefonní číslo a jeho 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 jeho hashové funkce. Dobrá hashová funkce typicAlly zajišťuje 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é produkovat 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 je velký klastrZ hodnot již bylo přiřazeno, obvykle by trvalo mnohem déle hledat nepřiřazenou hodnotu pro nový klíč.
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á hashovací funkce.
Mnoho výzkumných pracovníků v oblasti informatiky se snažilo vytvořit perfektní hashovací funkci - ta, která nevytváří žádné kolize nebo klastry vzhledem k rostoucímu faktoru zátěže. Teoreticky je klíčem k vytvoření dokonalého hashtable proDUCE Perfektní hashovací funkce. Vědci se obecně domnívají, že dokonalá funkce hash by měla mít neustálý výkon - počet kolizí a shluků - s rostoucím faktorem zatížení. V nejhorších scénářích by dokonalá funkce hash stále umožňovala neustálý hashování, aniž by dosáhla prahu.