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

Hash je extrémně špatně pojmenovaná datová struktura, kde si programátor zaměnil rozhraní s implementací ( a byla příliš líná na to, aby napsala celé jméno, tj. HashTable místo uchýlení se ke zkratce 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 jedna možná implementace takového slovníku, který poskytuje celkem dobré charakteristiky přístupu (z hlediska běhového prostředí) a je proto často výchozí implementací.

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

1. klíče musí být ha shable a srovnatelnost rovnosti .
2. položky se ve slovníku nezobrazují v žádném konkrétním pořadí.

(Pro klíč k be hashable znamená, že můžeme vypočítat číselnou hodnotu z klíče, který se následně použije jako index v poli.)

Existují alternativní implementace slovníkové datové struktury, které ukládají uspořádání na klávesách – často se tomu říká seřazený slovník (a obvykle se implementuje ve formě vyhledávacího stromu, i když existují další efektivní implementace).

To shrnout: slovník je ADT, který mapuje klíče k hodnotám. Existuje několik možných implementací tohoto ADT, z nichž hash tabulka je jedna. Hash je nesprávné pojmenování, ale v kontextu je ekvivalentní se slovníkem, který je implementován ve formě hash tabulky.

Komentáře

• Abychom uvedli příklad v C ++, standardní asociativní šablony kontejnerů nemohly být ' implementovány jako hash, i když příští standard bude mít to, co jsou efektivně hash tabulky. ' Zavolali unordered_map, aby ukázali, co dělají, místo toho, čím jsou.
• „správné“ podle jaký úřad? V některých jazycích, jako jsou Ruby a Perl, je oficiální – číst „správný“ – název pro tyto struktury „hash“.
• @nohat: Všimněte si mého použití uvozovek. Dále jsem vysvětlil , proč je název špatně zvolen, že? Pokud tedy požadujete autoritu, řeknu, že je to autorita teoretické policie pro počítačové vědy.
• Zajímavé je, že v Ruby 1.9 je ve skutečnosti nemožné implementovat Hash třída s hashovací tabulkou, protože Ruby 1.9 Hash es zachovává pořadí vložení, zatímco hash tabulka nikoli. Takže v Ruby 1.9 název Hash již ' už ani neodráží implementaci.
• @hippietrail Mýlíte se – za prvé, jsou objektivní popisy. Koneckonců, kvalifikuji se, proč je pojmenování špatné a nesprávné pojmenování (viz níže). „Příliš líný“ je umělecká licence z mé strany, ale jde o to, že důvod ke zkrácení jména je přirozený, tj. Není důvod zde používat jiný krátký název, než zkrácení názvu. A ve „slovníku“ se mýlíte: to je jednoduše oficiální název datové struktury. Vaše definice „slovníku“ je v kontextu počítačové vědy nesprávná a název předchází Pythonu desítky let.

„Slovník“ je název konceptu. Možnou implementací je hashtable.

Komentáře

• Hash je také ADT. HashTable je implementace Hash
• @Sairam, myslím, že je mnohem běžnější, když ' hash ' znamená spíše hashovací funkce než hashovací tabulka.
• @jk Vlastně " hash " je výsledkem použití a " hash funkce / algoritmu " k nějakému vstupu. " hash tabulka " nebo " hash mapa " omehoe souvisí a hashovatelný objekt s nějakým objektem (objekt v obecné formě, bez omezení na OOP)
• Existují jazyky, které používají ' hash ' odkazovat spíše na strukturu slovníku než na operaci hash funkce. například Ruby .

Slovník je souhrnný termín pro jakoukoli implementaci datové struktury používanou pro rychlé vyhledávání / vkládání. Toho lze dosáhnout / implementovat pomocí různých datových struktur, jako je hash 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.

Komentáře

• Hash je také ADT. Existuje nějaký konkrétní rozdíl mezi Hash a Dictionary ADT?
• @Sairam: Ne, hash je výstup určitého druhu algoritmu (hash funkce).

Slovník používá klíč k odkazovat na hodnotu přímo uvnitř asociativního pole .

tj. (KEY => VALUE)

A hash je častěji popisován jako hash tabulka , která používá hashovací funkci k výpočtu pozice v paměti (nebo snadněji pole), kde bude hodnota. Hash bude mít KEY jako vstup a dá hodnotu jako výstup. Poté tuto hodnotu zapojte do indexu paměti nebo pole.

tj. KEY => HASH FUNCTION => VALUE

Myslím, že jeden je přímý, zatímco druhý isn „t. Funkce hash nemusí být ani dokonalé a někdy mohou poskytnout index odkazující na nesprávnou hodnotu. To však lze opravit.

Nejlepší místo k hledání: Wikipedia ( asociativní pole a hash tabulka )