Objašnjena hash tablica: što je to i kako ga primijeniti

Hash tablica, također poznata i kao hash karta, je struktura podataka koja preslikava ključeve u vrijednosti. To je jedan dio tehnike koja se naziva hashiranje, a drugi je hash funkcija. Hash funkcija je algoritam koji stvara indeks mjesta gdje se vrijednost može pronaći ili pohraniti u hash tablicu.

Neke važne napomene o hash tablicama:

  1. Vrijednosti se ne pohranjuju u razvrstanom redoslijedu.
  2. Razmišljate o potencijalnim sudarima. To se obično radi tehnikom koja se naziva ulančavanje. Chaining znači stvaranje povezanog popisa vrijednosti čiji se ključevi mapiraju u određeni indeks.

Implementacija hash tablice

Osnovna ideja koja stoji iza hashiranja je raspodjela parova ključ / vrijednost kroz niz rezerviranih mjesta ili "segmenata" u hash tablici.

Tabela raspršivanja obično je niz povezanih popisa. Kada želite umetnuti par ključ / vrijednost, najprije morate upotrijebiti funkciju raspršivanja za mapiranje ključa u indeks u tablici raspršivanja. S obzirom na ključ, hash funkcija može predložiti indeks u kojem se vrijednost može pronaći ili pohraniti:

index = f(key, array_size)

To se često radi u dva koraka:

hash = hashfunc(key) index = hash % array_size

Korištenjem ove metode hashneovisno je o veličini hash tablice. hashsvodi se na indeks - broj između 0, početka niza i array_size - 1, na kraju niza - pomoću modulo (%) operatora.

Razmotrite sljedeći niz S:

string S = “ababcd”

Morate izbrojati učestalost svih znakova u S. To ćete najlakše učiniti prelistavanjem svih mogućih znakova i brojanjem učestalosti svakog od njih, jednog po jednog.

To djeluje, ali sporo je - vremenska složenost takvog pristupa je O (26 * N), pri Nčemu je veličina niza Spomnožena s 26 mogućih znakova iz AZ-a.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Izlaz:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Pogledajmo rješenje koje koristi raspršivanje.

Uzmite niz i upotrijebite hash funkciju za raspršivanje 26 mogućih znakova s ​​indeksima polja. Zatim ponovite Si povećajte vrijednost trenutnog znaka niza s pripadajućim indeksom za svaki znak.

Složenost ovog pristupa raspršivanju je O (N), gdje je N veličina niza.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Izlaz

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash sudari

Budući da će vaša hash karta vjerojatno biti znatno manja od količine podataka koje obrađujete, kolizijski hashi su neizbježni. Dva su glavna pristupa rješavanju sudara: lančano i otvoreno adresiranje .

Ulančavanje

Kao što je ranije spomenuto, ulančavanje znači da je svaki par ključ / vrijednost u hash tablici vrijednost povezani popis podataka, a ne jedna ćelija.

Na primjer, zamislite da ključ 152 ima vrijednost "John Smith". Ako se vrijednosti "Sandra Dee" doda isti ključ, "Sandra Dee" dodaje se kao drugi element tipki 152, odmah iza "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Glavni nedostatak lančanog povezivanja je povećanje vremenske složenosti. Umjesto 0 (1) kao kod uobičajene tablice raspršivanja, svakom pretraživanju trebat će više vremena jer moramo prelaziti svaki povezani popis da bismo pronašli ispravnu vrijednost.

Otvoreno adresiranje

Otvoreno adresiranje znači da, nakon što se vrijednost preslika na ključ koji je već zauzet, krećete se po tipkama hash tablice dok ne pronađete praznu. Na primjer, ako je "John Smith" mapiran na 152, "Sandra Dee" bit će mapirana na sljedeći otvoreni indeks:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Glavni nedostatak otvorenog adresiranja je taj što, kada potražite vrijednosti, one možda neće biti na ključnoj mapi na kojoj ih očekujete. Umjesto toga, morate preći različite dijelove hash tablice kako biste pronašli vrijednost koju tražite.