Mitä eroa hashilla ja sanakirjalla on?

Hash on erittäin huonosti nimetty tietorakenne, jossa ohjelmoija on sekoittanut käyttöliittymän toteutukseen ( ja oli liian laiska kirjoittamaan koko nimeä, eli HashTable turvautuu sen sijaan lyhenteeseen, Hash).

Dictionary on käyttöliittymän ”oikea” nimi (= ADT ), eli assosiatiivinen säilö, joka yhdistää (yleensä yksilölliset) avaimet (ei välttämättä ainutlaatuisiin) arvoihin.

Hajautustaulukko on yksi tällaisen sanakirjan mahdollinen toteutus, joka tarjoaa melko hyvät käyttöominaisuudet (ajonaikaisesti) ja on siksi usein oletustoteutus.

Tällaisella toteutuksella on kaksi tärkeää ominaisuutta:

1. avainten on oltava ha shable ja verrattavissa oleva tasa-arvo .
2. merkinnät eivät näy sanakirjassa tietyssä järjestyksessä.

(Avain olla hashable tarkoittaa, että voimme laskea numeerisen arvon avaimesta, jota myöhemmin käytetään indeksinä taulukossa.)

Sanakirjatietorakenteelle on olemassa vaihtoehtoisia toteutuksia, jotka asettavat tilauksen näppäimissä – tätä kutsutaan usein lajitelluksi sanakirjaksi (ja se toteutetaan yleensä hakupuuna, vaikka muita tehokkaita toteutuksia onkin).

yhteenveto: sanakirja on ADT, joka yhdistää avaimet arvoihin. Tätä ADT: tä on useita mahdollisia toteutuksia, joista yksi on hash-taulukko . Hash on väärä nimi, mutta asiayhteydessä se vastaa sanakirjaa, joka on toteutettu hash-taulukon muodossa.

Kommentit

• Esimerkkinä C ++: sta, tavallisia assosiatiivisia säilömalleja ei voitu ' t käyttää hashina, vaikka seuraavassa standardissa olisi tehokkaasti hash-taulukot. He ' kutsuivat unordered_map näyttämään, mitä he tekevät pikemminkin kuin mitä he ovat.
• ”oikein” mukaan mikä viranomainen? Joillakin kielillä, kuten Ruby ja Perl, näiden rakenteiden virallinen – lue ”oikea” – nimi on ”hash”.
• @nohat: Huomaa käyttämäni lainausmerkkejä. Lisäksi olen selittänyt miksi nimi on valittu huonosti, vai mitä? Joten jos tarvitset viranomaista, sanon, että se on teoreettisen tietojenkäsittelypolitiikan viranomainen.
• Kiinnostavaa on, että Ruby 1.9: ssä on todella mahdotonta toteuttaa Hash -luokka, jossa on hash-taulukko, koska Ruby 1.9 Hash es säilyttää lisäysjärjestyksen, kun taas hash-taulukko ei. Joten Ruby 1.9: ssä nimi Hash ei ' t heijasta edes toteutusta.
• @hippietrail Olet väärässä – ensinnäkin nämä ovat objektiivisia kuvauksia. Loppujen lopuksi voin todeta, miksi nimeäminen on huono ja väärä nimi (katso alla). ”Liian laiska” on taiteellinen lisenssi, mutta asia on edelleen se, että syy lyhentää nimeä on luonnostaan, ts. Ei ole mitään syytä käyttää tässä lyhyttä nimeä muuten kuin lyhentämään nimeä. Ja olet väärässä sanakirjan suhteen: se on yksinkertaisesti tietorakenteen virallinen nimi . Määritelmäsi ”sanakirja” on väärä tietojenkäsittelytieteen kontekstissa, ja nimi edeltää Pythonia vuosikymmenien ajan.

”Sanakirja” on konseptin nimi. Hashtable on mahdollinen toteutus.

Kommentit

• Hash on myös ADT. HashTable on hashin toteutus
• @Sairam. Mielestäni sen ' hash ' tarkoittaa paljon yleisempää hash-funktio hash-taulukon sijasta.
• @jk Itse asiassa " hash " on tulos sovelluksesta " hash-funktio / algoritmi " johonkin tuloon. " hash-taulukko " tai " hash-kartta " omehoe liittyy ja hashable-objekti johonkin objektiin (objekti yleisessä muodossa, ei rajoitu OOP: iin)
• On kieliä, jotka käyttävät ' Hash ' viitata sanakirjatyyppiseen rakenteeseen eikä vain hash-funktioon. Esimerkiksi Ruby .

Sanakirja on kollektiivinen termi, joka annetaan kaikelle tietorakenteen toteutukselle, jota käytetään nopeaan hakuun / lisäykseen. Tämä voidaan saavuttaa / toteuttaa käyttämällä erilaisia tietorakenteita, kuten hash-taulukko, ohitusluettelot, rb-puu jne. Hash-taulukko on erityinen tietorakenne, joka on hyödyllinen moniin tarkoituksiin, mukaan lukien sanakirjan toteuttaminen.

Kommentit

• Hash on myös ADT. Onko Hashin ja Dictionary ADT: n välillä mitään erityistä eroa?
• @Sairam: Ei, hash on tietynlaisen algoritmin (hash-funktio) tulos.

A sanakirja käyttää avainta viittaa arvoon suoraan assosiatiivisen taulukon sisällä .

ts. (KEY => VALUE)

A hash kuvataan useammin nimellä hajautustaulukko joka käyttää hajautusfunktiota laskeaksesi muistin sijainti (tai helpommin matriisi), jossa arvo on. Hajautus ottaa KEY-syötteen ja antaa arvon tuotokseksi. Liitä sitten arvo muistiin tai taulukkoindeksiin.

ts. KEY => HASH FUNCTION => VALUE

Luulen, että yksi on suora, kun toinen isn ”t. Hash-toiminnot eivät myöskään välttämättä ole täydellisiä, ja joskus ne voivat tarjota hakemiston, joka viittaa väärään arvoon. Mutta se voidaan korjata.

Paras paikka etsiä: Wikipedia ( assosiatiivinen taulukko ja hash-taulukko )