Mi a különbség a hash és a szótár között?

Hash egy rendkívül rosszul megnevezett adatstruktúra, ahol a programozó összekeverte az interfészt a megvalósítással ( és lusta volt a teljes név, azaz HashTable inkább rövidítéshez folyamodik, Hash).

Dictionary a felület “helyes” neve (= a ADT ), azaz egy asszociatív tároló, amely (általában egyedi) kulcsokat (nem feltétlenül egyedi) értékekhez társít.

A hash tábla egy lehetséges ilyen szótár megvalósítása, amely meglehetősen jó hozzáférési jellemzőket biztosít (futásidejű szempontból), és ezért gyakran az alapértelmezett megvalósítás.

Egy ilyen megvalósításnak két fontos tulajdonsága van:

1. a kulcsoknak ha-nak kell lenniük shable és egyenlőség összehasonlítható .
2. a bejegyzések nem külön sorrendben jelennek meg a szótárban.

(A A be hashable azt jelenti, hogy számszerű értéket számolhatunk egy kulcsból, amelyet később egy tömb indexeként használunk.)

A szótár adatstruktúrájának vannak alternatív megvalósításai, amelyek sorrendet a billentyűkön – ezt gyakran rendezett szótárnak hívják (és általában egy keresési fán keresztül valósítják meg, bár más hatékony megvalósítás is létezik).

összegezzük: a szótár egy ADT, amely a kulcsokat feltérképezi az értékekre. Ennek az ADT-nek több lehetséges megvalósítása létezik, amelyek közül a hash tábla egy. A Hash helytelen elnevezés, de összefüggésében egyenértékű egy szótárral, amelyet hash-táblázatban valósítanak meg.

Megjegyzések

• Példaként a C ++ nyelven a standard asszociatív tárolósablonok nem kerülhetnek ' kivitelezésre hash-ként, bár a következő szabvány a hatékony hash táblákat tartalmazza. ' Felhívták unordered_map -et, hogy megmutassák, mit csinálnak, nem pedig, hogy mik.
• „helyes” a milyen hatóság? Bizonyos nyelveken, például a Ruby és a Perl, ezeknek a struktúráknak a hivatalos – olvassa el a „helyes” – neve „hash”.
• @nohat: Vegye figyelembe, hogy idézeteket használok. Továbbá, megmagyaráztam , hogy miért választják rosszul a nevet, nem? Tehát ha jogosultságra van szükséged, akkor azt mondom, hogy az elméleti informatikai rendőrség hatáskörébe tartozik.
• Érdekes, hogy a Ruby 1.9-ben valójában lehetetlen megvalósítani a Hash osztály hash táblával, mivel a Ruby 1.9 Hash es megőrzi a beszúrási sorrendet, míg a hash tábla nem. Tehát a Ruby 1.9-ben a Hash név nem ' nem is tükrözi tovább a megvalósítást.
• @hippietrail Téved – először is, ezek objektív leírások. Végül is minősítem, miért rossz a névadás és helytelen elnevezés (lásd alább). A „túl lusta” művészi engedély a részemről, de a lényeg továbbra is az, hogy a név rövidítésének oka önmagában rejlik, vagyis a név lerövidítésén kívül itt nincs ok rövid név használatára. És téved a „szótárral” kapcsolatban: ez egyszerűen az adatstruktúra hivatalos neve . A „szótár” definíciója téves az informatika összefüggésében, és a név évtizedekkel előzi meg a Pythont.