Wat is het verschil tussen een hash en een woordenboek?

Hash is een extreem slecht benoemde datastructuur waarbij de programmeur de interface heeft verward met implementatie ( en was te lui om de volledige naam te schrijven, dwz HashTable in plaats daarvan toevlucht te nemen tot een afkorting, Hash).

Dictionary is de “juiste” naam van de interface (= de ADT ), dwz een associatieve container die (meestal unieke) sleutels toewijst aan (niet noodzakelijk unieke) waarden.

Een hashtabel is een mogelijke implementatie van een dergelijk woordenboek dat redelijk goede toegangskenmerken (in termen van runtime) biedt en daarom vaak de standaard implementatie is.

Zon implementatie heeft twee belangrijke eigenschappen:

1. de sleutels moeten ha zijn shable en gelijkheid vergelijkbaar .
2. de items verschijnen in willekeurige volgorde in het woordenboek.

(Voor een sleutel tot be hashable betekent dat we een numerieke waarde kunnen berekenen uit een sleutel die vervolgens wordt gebruikt als een index in een array.)

Er bestaan alternatieve implementaties van de datastructuur van het woordenboek die een ordening op de toetsen – dit wordt vaak een gesorteerd woordenboek genoemd (en wordt meestal geïmplementeerd in termen van een zoekboom, hoewel er andere efficiënte implementaties bestaan).

Aan vat samen: een woordenboek is een ADT die sleutels aan waarden toewijst. Er zijn verschillende mogelijke implementaties van deze ADT, waarvan de hashtabel er een is. Hash is een verkeerde benaming, maar in context is het equivalent aan een woordenboek dat is geïmplementeerd in termen van een hashtabel.

Opmerkingen

• Om een voorbeeld te geven in C ++: de standaard associatieve containersjablonen kunnen niet ' worden geïmplementeerd als hashes, hoewel de volgende standaard zal hebben wat in feite hashtabellen zijn. Ze ' worden unordered_map genoemd om te laten zien wat ze doen in plaats van wat ze zijn.
• “correct” volgens welke autoriteit? In sommige talen, zoals Ruby en Perl, is de officiële – lees “correcte” – naam voor deze structuren “hash”.
• @nohat: Merk op dat ik aanhalingstekens gebruik. Verder heb ik heb uitgelegd waarom de naam slecht is gekozen, nietwaar? Dus als je een autoriteit nodig hebt, dan zeg ik dat het door de autoriteit is van de theoretische informatica-politie.
• Interessant is dat het in Ruby 1.9 eigenlijk onmogelijk is om de class met een hashtabel, aangezien Ruby 1.9 Hash es de invoegvolgorde behouden terwijl een hashtabel dat niet doet. Dus in Ruby 1.9 weerspiegelt de naam Hash niet ' de implementatie zelfs niet meer.
• @hippietrail Je hebt het mis – ten eerste zijn dat zijn objectieve beschrijvingen. Ik bepaal tenslotte waarom de naamgeving slecht is en een verkeerde benaming (zie hieronder). “Te lui” is een artistieke licentie van mijn kant, maar het punt blijft dat de reden om de naam in te korten intrinsiek is, d.w.z. er is geen reden om hier een korte naam te gebruiken, behalve om de naam in te korten. En je hebt het mis over “woordenboek”: dat is gewoon de officiële naam van de datastructuur. Uw definitie van “woordenboek” is onjuist in de context van informatica, en de naam is decennia ouder dan Python.

“Woordenboek” is de naam van het concept. Een hashtabel is een mogelijke implementatie.

Reacties

• Hash is ook een ADT. HashTable is een implementatie van een hash
• @Sairam Ik denk dat het veel gebruikelijker is om ' hash ' te betekenen een hash-functie in plaats van een hashtabel.
• @jk Eigenlijk is de " hash " het resultaat van een " hash-functie / algoritme " naar een bepaalde invoer. Een " hashtabel " of " hash-kaart " omehoe relateert en hash-object aan een object (object in een generieke vorm, niet beperkt tot OOP)
• Er zijn talen die ' Hash ' om te verwijzen naar een woordenboekachtige structuur in plaats van alleen naar de hash-functiebewerking. Ruby, bijvoorbeeld .

Een woordenboek is de verzamelnaam die wordt gegeven voor elke datastructuurimplementatie die wordt gebruikt voor snelle opzoekingen / invoegingen. Dit kan worden bereikt / geïmplementeerd met behulp van een verscheidenheid aan datastructuren zoals hashtabel, skiplijsten, rb-boom enz. Een hashtabel is een specifieke datastructuur die nuttig is voor vele doeleinden, inclusief het implementeren van een woordenboek.

Opmerkingen

• Hash is ook een ADT. Is er een specifiek verschil tussen Hash en Dictionary ADT?
• @Sairam: Nee, een hash is de uitvoer van een bepaald soort algoritme (hashfunctie).

Een woordenboek gebruikt een sleutel om verwijs naar de waarde direct in een associatieve array .

dwz (KEY => VALUE)

Een hash wordt vaker beschreven als een hash-tabel die een hash-functie gebruikt om te berekenen de positie in het geheugen (of eenvoudiger een array) waar de waarde zal zijn. De hash neemt de KEY als invoer en geeft een waarde als uitvoer. Sluit die waarde vervolgens aan op het geheugen of de array-index.

ie KEY => HASH FUNCTION => VALUE

Ik denk dat de ene direct is en de andere isn “t. Hash-functies zijn misschien ook niet perfect en bieden soms een index die verwijst naar de verkeerde waarde. Maar dat kan worden gecorrigeerd.

Beste plaats om te zoeken: Wikipedia ( associatieve array en hashtabel )