Što je hashiranje? Kako funkcioniraju hash kodovi - s primjerima

Uvod u raspršivanje

Hashing je dizajniran da riješi problem potrebe za učinkovitim pronalaženjem ili pohranjivanjem predmeta u kolekciji.

Primjerice, ako imamo popis od 10 000 riječi na engleskom i želimo provjeriti nalazi li se zadana riječ na popisu, bilo bi neučinkovito usporediti riječ sa svih 10 000 predmeta dok ne pronađemo podudaranje. Čak i ako je popis riječi leksikografski poredan, kao u rječniku, i dalje će vam trebati neko vrijeme da pronađete riječ koju tražite.

Hashing je tehnika koja učinkovitije čini učinkovitim sužavanjem pretraživanja na samom početku.

Što je raspršivanje?

Hashing znači korištenje neke funkcije ili algoritma za mapiranje podataka objekta u neku reprezentativnu cijelu vrijednost.

Ovaj takozvani hash kod (ili jednostavno hash) tada se može koristiti kao način za sužavanje pretraživanja prilikom traženja stavke na karti.

Općenito se ovi hash kodovi koriste za generiranje indeksa u kojem se vrijednost pohranjuje.

Kako raspršivanje djeluje

U hash tablicama podatke pohranjujete u obrasce parova ključeva i vrijednosti. Ključ koji se koristi za identifikaciju podataka daje se kao ulaz u funkciju raspršivanja. Hash kod, koji je cijeli broj, zatim se preslikava na fiksnu veličinu koju imamo.

Hash tablice moraju podržavati 3 funkcije.

  • umetanje (ključ, vrijednost)
  • dobiti (ključ)
  • izbriši (ključ)

Čisto kao primjer koji će nam pomoći da shvatimo koncept, pretpostavimo da želimo mapirati popis ključeva niza u vrijednosti niza (na primjer, mapirati popis zemalja u njihove glavne gradove).

Dakle, recimo da želimo podatke pohraniti u tablicu na kartu.

I pretpostavimo da je naša hash funkcija jednostavno uzeti dužinu niza.

Radi jednostavnosti imat ćemo dva polja: jedan za naše ključeve i jedan za vrijednosti.

Dakle, da stavimo stavku u hash tablicu, izračunavamo njezin hash kôd (u ovom slučaju jednostavno izbrojimo broj znakova), a zatim stavimo ključ i vrijednost u nizove na odgovarajući indeks.

Na primjer, Kuba ima hash kôd (dužinu) od 4. Dakle, Kubu pohranjujemo na 4. mjesto u polju ključeva, a Havana u 4. indeks niza vrijednosti itd. I na kraju imamo sljedeće:

U ovom konkretnom primjeru stvari funkcioniraju prilično dobro. Naš niz mora biti dovoljno velik da primi najduži niz, ali u ovom slučaju to je samo 11 mjesta.

Gubimo malo prostora jer, na primjer, u našim podacima nema ključeva od jednog slova, niti ključeva između 8 i 10 slova.

Ali u ovom slučaju ni izgubljeni prostor nije tako loš. Uzimanje duljine niza lijepo je i brzo, a takav je i postupak pronalaska vrijednosti povezane s danim ključem (zasigurno brže od uspoređivanja do pet nizova).

Ali, što ćemo učiniti ako naš skup podataka sadrži niz koji sadrži više od 11 znakova?

Što ako imamo jednu drugu riječ s 5 znakova, "India", i pokušamo je dodijeliti indeksu pomoću naše hash funkcije. Budući da je indeks 5 već zauzet, moramo nazvati što učiniti s njim. To se naziva sudarom.

Ako bi naš skup podataka imao niz s tisuću znakova, a vi biste napravili niz od tisuću indeksa za pohranu podataka, to bi rezultiralo gubitkom prostora. Da su naše tipke nasumične riječi s engleskog jezika, gdje ima toliko riječi iste duljine, upotreba duljine kao funkcije raspršivanja bila bi prilično beskorisna.

Rukovanje sudarom

Dvije osnovne metode koriste se za rješavanje sudara.

  1. Odvojeno ulančavanje
  2. Otvoreno adresiranje

Odvojeno ulančavanje

Rukovanje sudarom heša odvojenim lancem, koristi dodatnu strukturu podataka, poželjno povezan popis za dinamičku dodjelu, u segmente. U našem primjeru, kada dodamo Indiju skupu podataka, on se dodaje povezanom popisu pohranjenom u indeksu 5, tada bi naša tablica izgledala ovako.

Da bismo pronašli predmet, prvo idemo u skupinu, a zatim uspoređujemo ključeve. Ovo je popularna metoda, a ako se koristi popis veza, hash se nikad ne popunjava. Trošak za get(k)je u prosjeku O(n)gdje je n broj ključeva u segmentu, ukupan broj ključeva mora biti N.

Problem odvojenog ulančavanja je u tome što struktura podataka može rasti izvan granica.

Otvoreno adresiranje

Otvoreno adresiranje ne uvodi novu strukturu podataka. Ako se dogodi sudar, tada tražimo dostupnost na sljedećem mjestu generiranom algoritmom. Otvoreno adresiranje obično se koristi tamo gdje je prostor za pohranu ograničen, tj. Ugrađeni procesori. Otvoreno adresiranje nije nužno brže od odvojenog lančanog lanca.

Metode za otvoreno adresiranje

  • [Linearno sondiranje
  • Kvadratno sondiranje
  • Dvostruko raspršivanje

Kako koristiti raspršivanje u kodu.

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()
:raketa:

Pokreni kod

Java

 // 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();
:raketa:

Pokreni kod

Više informacija o raspršivanju

  • Bežični vodič za raspršivanje i hash tablice
  • Kako implementirati jednostavnu hash tablicu u JavaScript
  • Objašnjene tablice hasha