Aký je rozdiel medzi maticou a hashovacou tabuľkou v programovacom jazyku?


Odpoveď 1:

Hash tabuľky používajú polia. Polia majú dôležitú vlastnosť pri hashovaní: ak poznáte jeho index, môžete pristupovať k akémukoľvek prvku v konštantnom čase.

Môžete použiť polia pre vedrá. Povedzme, že ste chceli, aby ste spočítali, koľko z každého písmena v texte, napríklad, navrhli niečo ako Morseov kód. Vytvoríte pole s 26 záznamami (pre jednoduchú nercentovanú rímsku abecedu). Kedykoľvek uvidíte písmeno, vypočítate index a prejdite na túto položku v poli.

Hash tabuľky to rozširujú o ľubovoľne dlhé kľúče. Vypočítate hash kľúča a prejdete na tento index. Problém je, keď má viac kľúčov rovnaký hash. Existuje niekoľko spôsobov, ako sa s tým vysporiadať, z ktorých niektoré porážajú účel hashu (ale dajú sa ľahko implementovať). Niektorí z nich nie sú a aspoň v priemere udržiavajú vlastnosť konštantného času.

To najlepšie, čo som videl, je opakované hashovanie, ktoré v prípade, že pamäť slúži už pred desiatkami rokov, dokázali Gonnet a Munroe v priemere o niečo viac ako 4 prístupy s faktorom zaťaženia 50%, bez ohľadu na veľkosť hash tabuľka. To si však vyžaduje použitie prvočísel, a preto je zložité implementovať. Prvočísla musíte nejako nájsť. Našťastie hashovacie tabuľky nie sú také veľké, že sa to stáva smiešnym.