Co je to hashable?
V informatice je hashtable 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, zvaného matice. Například obchodní název může být spárován s jeho adresou. Každá hodnota v poli má obvykle číslo pozice označované jako hash. Hašovací funkce je obecně sada instrukcí nebo algoritmu, který mapuje každou hodnotu klíče na hash - například spojuje obchodní jméno s jeho adresou, telefonním číslem a obchodní kategorií. Účelem hashovací funkce je přiřadit každému klíči jedinečnou odpovídající hodnotu v poli; toto se běžně označuje jako hašování. Hash funkce musí být správně naformátovány, aby hashtable fungoval správně.
Výkon hashtable na souboru dat je závislý na účinnosti jeho hash funkce. Dobrá hashovací funkce obvykle zajišťuje jednotné vyhledávání klíčů a rovnoměrnou distribuci mapování v odpovídajícím poli. Ke kolizi hash dojde, když jsou dvěma klíčům přiřazeny stejné odpovídající hodnoty. Když dojde ke kolizi hash, hash funkce se obvykle provede znovu, dokud není nalezena jedinečná odpovídající hodnota; výsledkem je obvykle delší doba hashování. Ačkoli počet klíčů v hashtable je obvykle fixní, někdy tam mohou být duplicitní klíče. I přesto má dobře navržený hashtable efektivní hashovací funkce, které mapují každý klíč na jedinečnou odpovídající hodnotu v poli.
Někdy mohou neefektivní hashovací funkce v hashtable také vytvářet shluk mapování. Pokud hashovací funkce vytvoří shluk mapování pro existující klíče, může to prodloužit dobu potřebnou k vyhledání odpovídajících hodnot. To může zpomalit hašování budoucích klíčů, protože většina hashovacích funkcí obecně hledá další dostupnou pozici v poli. Pokud již byla přiřazena velká skupina hodnot, obvykle by hledání nového nepřiřazeného klíče trvalo mnohem déle.
Faktor zatížení je další koncept související s účinností hašovací funkce; faktor zatížení je množství již existujících hashů ve vztahu k celkové velikosti odpovídajícího pole v hashtable. Obvykle je definován vydělením počtu již přiřazených klíčů velikostí odpovídajícího pole. Když se faktor zatížení zvyšuje, dobrá hashovací funkce bude normálně stále udržovat konstantní počet kolizí a shluků až do určitého bodu. Tuto prahovou hodnotu lze často použít k určení, jak účinná je hashovací funkce s daným počtem kláves a kdy může být potřeba nová hashovací funkce.
Mnoho vědců v oblasti informatiky se snažilo vytvořit dokonalou hashovací funkci - takovou, která nevyvolává žádné srážky ani shluky vzhledem k rostoucímu faktoru zatížení. Teoreticky je klíčem k vytvoření perfektního hashtableu vytvoření perfektní hashovací funkce. Obecně se vědci domnívají, že dokonalá hashovací funkce by měla mít konstantní výkon - počet kolizí a shluků - se zvyšujícím se faktorem zatížení. V nejhorších případech by perfektní hashovací funkce stále umožňovala konstantní hašování bez dosažení prahu.