Bevezetés a hash-ba
A hashing célja, hogy megoldja azt a problémát, hogy hatékonyan kell megkeresni vagy tárolni egy elemet egy gyűjteményben.
Például, ha van egy 10 000 angol szóból álló listánk, és ellenőrizni akarjuk, hogy egy adott szó szerepel-e a listán, akkor nem lenne hatékony egymás után összehasonlítani a szót mind a 10 000 elemmel, amíg találunk egyezést. Még akkor is, ha a szavak listája lexikográfia szerint van rendezve, például egy szótárban, mégis szüksége van egy kis időre a keresett szó megtalálásához.
A hashing egy olyan technika, amellyel hatékonyabbá lehet tenni a dolgokat azáltal, hogy az elején hatékonyan leszűkíti a keresést.
Mi a keverés?
A hash azt jelenti, hogy valamilyen függvényt vagy algoritmust használunk az objektumadatok leképezésére valamilyen reprezentatív egész értékre.
Ezt az úgynevezett kivonatkódot (vagy egyszerűen hash-kódot) felhasználhatjuk arra, hogy szűkítsük a keresésünket, amikor az elemet a térképen keressük.
Általában ezeket a kivonatkódokat használják egy index létrehozására, amelynél az érték tárolódik.
Hogyan működik a hash
A hash táblákban kulcs- és értékpárok formájában tárolja az adatokat. A kulcs, amelyet az adatok azonosítására használnak, a kivonatoló funkció bemeneteként szolgál. A hash kód, amely egy egész szám, ezután hozzárendelve a rendelkezésünkre álló fix mérethez.
A hash-tábláknak 3 funkciót kell támogatniuk.
- beszúrás (kulcs, érték)
- get (kulcs)
- törlés (kulcs)
Tisztán példaként, hogy segítsen megérteni a koncepciót, tegyük fel, hogy a karakterlánc-kulcsok listáját a karakterlánc-értékekhez szeretnénk hozzárendelni (például feltérképezzük az országok listáját a fővárosukba).
Tegyük fel tehát, hogy az adatokat a Táblázatban szeretnénk tárolni a térképen.
Tegyük fel, hogy a hash függvényünk az, hogy egyszerűen vegyük fel a karakterlánc hosszát.
Az egyszerűség kedvéért két tömböt kapunk: egyet a kulcsainkra és egyet az értékekre.
Tehát ahhoz, hogy egy elemet beillesszünk a kivonat táblába, kiszámoljuk annak kivonatkódját (ebben az esetben egyszerűen meg kell számolni a karakterek számát), majd a kulcsot és az értéket beletesszük a megfelelő index tömbjeibe.
Például Kubának hash-kódja (hossza) 4. Tehát Kubát a kulcstömbben a 4. pozícióban, Havannát az értéktömb 4. indexében stb. Tároljuk. És a következõkkel járunk:
Ebben a konkrét példában a dolgok elég jól működnek. A tömbünknek elég nagynak kell lennie ahhoz, hogy elférjen a leghosszabb karakterlánc, de ebben az esetben ez csak 11 bővítőhely.
Kicsi helyet pazarolunk, mert például nincsenek 1 betűs kulcsok az adatainkban, és nem is 8 és 10 betű közötti kulcsok.
De ebben az esetben a pazarolt hely sem olyan rossz. A karakterlánc hosszának felvétele szép és gyors, ahogyan az adott kulcshoz tartozó érték megtalálásának folyamata is (természetesen gyorsabb, mint akár öt karakterlánc összehasonlítása).
De mit tegyünk, ha az adatkészletünknek 11-nél több karakterből álló karakterlánca van?
Mi van, ha van egy másik, 5 karakteres szó, az „India”, és megpróbáljuk hash függvényünkkel indexhez rendelni. Mivel az 5 index már elfoglalt, felhívnunk kell, hogy mit kezdjünk vele. Ezt hívják ütközésnek.
Ha az adatkészletünknek ezer karakterből álló karakterlánca lenne, és az adatok tárolásához ezer indexből álló tömböt készítene, az helypazarlást eredményezne. Ha a kulcsaink véletlenszerű szavak lennének angolból, ahol annyi azonos hosszúságú szó van, akkor a hosszúság hash-függvényként való használata elég haszontalan lenne.
Ütközés kezelése
Az ütközések kezelésére két alapvető módszert alkalmaznak.
- Külön láncolás
- Nyissa meg a Címzés lehetőséget
Külön láncolás
A hash ütközések kezelése külön láncolással, további adatstruktúrát használ, előnyösen a dinamikus elosztáshoz összekapcsolt listát használva, sávokba. Példánkban, amikor hozzáadjuk Indiát az adatkészlethez, az hozzáfűződik az 5. indexben tárolt összekapcsolt listához, akkor táblázatunk így nézne ki.
Elem megtalálásához először a vödörbe megyünk, majd összehasonlítjuk a kulcsokat. Ez egy népszerű módszer, és ha hivatkozások listáját használjuk, akkor a hash soha nem töltődik be. A költség get(k)átlagosan O(n)ott van, ahol n a kulcsok száma a vödörben, a kulcsok teljes száma pedig N.
A külön láncolás problémája, hogy az adatszerkezet korlátok nélkül növekedhet.
Nyissa meg a Címzés lehetőséget
A nyílt címzés nem vezet be új adatstruktúrát. Ha ütközés történik, akkor keressük a rendelkezésre állást az algoritmus által létrehozott következő helyen. A nyílt címzést általában akkor használják, ha a tárhely korlátozott, azaz beágyazott processzorok. A nyitott címzés nem feltétlenül gyorsabb, mint a külön láncolás.
A nyílt címzés módszerei
- [Lineáris tapintás
- Másodlagos szondázás
- Dupla hashelés
Hogyan kell használni a kivonatot a kódban.
Piton
# Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
Futtassa a kódot
Jáva
// Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();Futtassa a kódot
További információ a hashról
- A kódolatlan útmutató a hash és hash táblázatokhoz
- Hogyan lehet egy egyszerű hash táblázatot megvalósítani a JavaScript-ben
- Hash táblázatok magyarázkodtak