it-swarm-eu.dev

Jaký je rozdíl mezi hashem a slovníkem?

Jaký je rozdíl mezi Hash a Dictionary?

Pocházím ze skriptovacího prostředí, mám pocit, že jsou si podobné, ale chtěl jsem zjistit přesné rozdíly. Googling mi moc nepomohl.

48
Sairam

Hash je extrémně špatně pojmenovaná datová struktura, kde programátor zaměňoval rozhraní s implementací (a bylo příliš líný na napsání celého jména, tj. HashTable namísto toho se používá zkratka Hash).

Dictionary je „správný“ název rozhraní (= = [~ # ~] adt [~ # ~] ), tj. asociativní kontejner, který mapuje (obvykle jedinečné) klíče na (ne nutně jedinečné) hodnoty.

Hašovací tabulka je one možná implementace takového slovníku, který poskytuje docela dobré přístupové charakteristiky (pokud jde o běhové prostředí), a je proto často implicitní implementací.

Taková implementace má dvě důležité vlastnosti:

  1. klíče musí být hashable a srovnatelnost rovnosti.
  2. záznamy se ve slovníku neobjeví v žádném konkrétním pořadí.

(Pro klíč, který má být hashable znamená, že můžeme vypočítat číselnou hodnotu z klíče, který je následně použit jako index v poli.)

Existují alternativní implementace struktury dat slovníku, která ukládá klíčům spořádání - to se často nazývá seřazené slovník (a obvykle se implementuje jako vyhledávací strom, i když existují jiné efektivní implementace).


Shrnout: slovník je ADT, který mapuje klíče na hodnoty. Existuje několik možných implementací tohoto ADT, z nichž hash tabulka je jedna. Hash je nesprávný název, ale v kontextu je ekvivalentem slovníku implementovaného pomocí hashovací tabulky.

94
Konrad Rudolph

„Slovník“ je název pojmu. Možným provedením je hashtable.

8
dan_waterworth

Slovník je souhrnný termín určený pro jakoukoli implementaci datové struktury používané pro rychlé vyhledávání/vkládání. Toho lze dosáhnout/implementovat pomocí různých datových struktur, jako je hashova tabulka, seznamy přeskočení, strom rb atd. Hašovací tabulka je specifická datová struktura užitečná pro mnoho účelů, včetně implementace slovníku.

7
aufather

slovník používá klíč k odkazu na hodnotu přímo uvnitř asociativní pole.

tj (KEY => VALUE)

hash je častěji popisován jako hash tabulka, který používá hash function pro výpočet pozice v paměti (nebo snadněji pole) kde hodnota bude. hash vezme KEY jako vstup a dá hodnotu jako výstup. Poté připojte tuto hodnotu k indexu paměti nebo pole.

tj KEY => HASH FUNCTION => VALUE

Myslím, že jeden je přímý, zatímco druhý ne. Hash funkce nemusí být perfektní a někdy mohou poskytnout index odkazující na nesprávnou hodnotu. Ale to lze napravit.

Nejlepší místo k pohledu: Wikipedia ( asociativní pole a hash tabulka )

5
Ross