Hash tablica u strukturi podataka: Python Primjer
Sarah Chen
Što je hashiranje?
Hash je vrijednost fiksne duljine, a generira se pomoću matematičke formule. Hash vrijednosti se koriste u kompresiji podataka, kriptologiji, itd. U indeksiranju podataka, hash vrijednosti se koriste jer imaju fiksnu duljinu bez obzira na vrijednosti koje su korištene za njihovo generiranje. Čini da hash vrijednosti zauzimaju minimalan prostor u usporedbi s drugim vrijednostima različitih duljina.
Raspršivanje koristi matematički algoritam za pretvaranje ključa u raspršivanje. Do sudara dolazi kada hash funkcija proizvede istu hash vrijednost za više od jednog ključa.
Što je hash tablica?
A HASH TABLICA je podatkovna struktura koja pohranjuje vrijednosti koristeći par ključeva i vrijednosti. Svakoj vrijednosti dodijeljen je jedinstveni ključ koji se generira pomoću hash funkcije.
Ime ključa koristi se za pristup pridruženoj vrijednosti. To čini pretraživanje vrijednosti u hash tablici vrlo brzim, bez obzira na broj stavki u hash tablici.
Hash funkcije
Na primjer, ako želimo pohraniti evidenciju zaposlenika, a svaki zaposlenik je jedinstveno identificiran pomoću broja zaposlenika.
Možemo koristiti broj zaposlenika kao ključ i dodijeliti podatke o zaposleniku kao vrijednost.
Gornji pristup će zahtijevati dodatni slobodni prostor reda veličine (m * n2) gdje je varijabla m veličina poredak, a varijabla n je broj znamenki za broj zaposlenika. Ovaj pristup uvodi problem skladišnog prostora.
Raspršivačka funkcija rješava gornji problem dobivanjem broja zaposlenika i njegovom upotrebom za generiranje raspršivačke vrijednosti cijelog broja, fiksnih znamenki i optimiziranja prostora za pohranu. Svrha hash funkcije je stvoriti ključ koji će se koristiti za referenciranje vrijednosti koju želimo pohraniti. Funkcija prihvaća vrijednost koju treba spremiti, a zatim koristi algoritam za izračunavanje vrijednosti ključa.
Slijedi primjer jednostavne hash funkcije
h(k) = k1 % m
OVDJE,
- h(k) je hash funkcija koja prihvaća parametar k. Parametar k je vrijednost za koju želimo izračunati ključ.
- k1 % m je algoritam za našu hash funkciju gdje je k1 vrijednost koju želimo pohraniti, a m je veličina popisa. Za izračunavanje ključa koristimo operator modula.
Primjer
Pretpostavimo da imamo popis s fiksnom veličinom 3 i sljedećim vrijednostima
[1,2,3]
Možemo upotrijebiti gornju formulu za izračun pozicija koje svaka vrijednost treba zauzimati.
Sljedeća slika prikazuje dostupne indekse u našoj hash tablici.
Korak 1) Izračunajte poziciju koju će zauzeti prva vrijednost ovako
h(1) = 1 % 3
= 1
Vrijednost 1 će zauzeti prostor na indeks 1
Korak 2) Izračunajte poziciju koju će zauzeti druga vrijednost
h(2) = 2 % 3
= 2
Vrijednost 2 će zauzeti prostor na indeks 2
Korak 3) Izračunajte poziciju koju će zauzeti treća vrijednost.
h(3) = 3 % 3
= 0
Vrijednost 3 će zauzeti prostor na indeks 0
Konačni rezultat
Naša ispunjena hash tablica sada će biti sljedeća.
Kvalitete dobre hash funkcije
Dobra hash funkcija trebala bi imati sljedeće kvalitete.
- Formula za generiranje hasha trebala bi koristiti vrijednost podataka koja se pohranjuje u algoritam.
- Funkcija raspršivanja treba generirati jedinstvene vrijednosti raspršivanja čak i za ulazne podatke koji imaju istu količinu.
- Funkcija bi trebala minimizirati broj kolizija. Do sudara dolazi kada se ista vrijednost generira za više od jedne vrijednosti.
- Vrijednosti moraju biti dosljedno raspoređene na sve moguće hash vrijednosti.
Sudar
Do sudara dolazi kada algoritam generira isti hash za više od jedne vrijednosti.
Pogledajmo primjer.
Pretpostavimo da imamo sljedeći popis vrijednosti
[3,2,9,11,7]
Pretpostavimo da je veličina hash tablice 7, a mi ćemo koristiti formulu (k1 % m) gdje je m veličina hash tablice.
Sljedeća tablica prikazuje hash vrijednosti koje će se generirati.
| Ključ | Hash algoritam (k1 % m) | Raspršena vrijednost |
|---|---|---|
| 3 | 3 % 7 | 3 |
| 2 | 3 % 7 | 2 |
| 9 | 3 % 7 | 2 |
| 11 | 3 % 7 | 4 |
| 7 | 3 % 7 | 0 |
Kao što možemo vidjeti iz gornjih rezultata, vrijednosti 2 i 9 imaju istu hash vrijednost i ne možemo pohraniti više od jedne vrijednosti na svakoj poziciji.
Zadani problem može se riješiti ulančavanjem ili ispitivanjem. Sljedeći odjeljci detaljno govore o ulančavanju i ispitivanju.
Ulančavanje
Ulančavanje je tehnika koja se koristi za rješavanje problema kolizije korištenjem povezanih popisa od kojih svaki ima jedinstvene indekse.
Sljedeća slika vizualizira kako izgleda lančana lista
I 2 i 9 zauzimaju isti indeks, ali su pohranjeni kao povezani popisi. Svaki popis ima jedinstveni identifikator.
Prednosti lančanih popisa
Sljedeće su prednosti lančanih popisa:
- Lančane liste imaju bolje performanse pri umetanju podataka jer je redoslijed umetanja O(1).
- Nije potrebno mijenjati veličinu hash tablice koja koristi ulančani popis.
- Može lako primiti veliki broj vrijednosti sve dok ima slobodnog prostora.
Sondiranje
Druga tehnika koja se koristi za rješavanje sudara je sondiranje. Kada koristimo metodu sondiranja, ako dođe do sudara, možemo jednostavno krenuti dalje i pronaći prazan utor za pohranu naše vrijednosti.
Sljedeće su metode sondiranja:
| način | Description |
|---|---|
| Linearno sondiranje | Baš kao što naziv sugerira, ova metoda traži prazne utore linearno počevši od pozicije gdje je došlo do sudara i kreće se prema naprijed. Ako se dosegne kraj popisa i nije pronađen nijedan prazan utor. Ispitivanje počinje na početku popisa. |
| Kvadratno ispitivanje | Ova metoda koristi izraze kvadratnog polinoma za pronalaženje sljedećeg slobodnog mjesta. |
| Double raspršivanje | Ova tehnika koristi sekundarni algoritam hash funkcije za pronalaženje sljedećeg slobodnog dostupnog mjesta. |
Koristeći naš gornji primjer, hash tablica nakon korištenja sondiranja izgledala bi ovako:
Operacije s hash tablicom
Ovdje su Operacije koje podržavaju Hash tablice:
- Umetanje - ovo Operation se koristi za dodavanje elementa u hash tablicu
- Pretraživanje - ovo Operation se koristi za traženje elemenata u hash tablici pomoću ključa
- Brisanje - ovo Operation se koristi za brisanje elemenata iz hash tablice
Operacija umetanja podataka
Operacija umetanja koristi se za pohranjivanje vrijednosti u hash tablicu. Kada se nova vrijednost pohranjuje u hash tablicu, dodjeljuje joj se indeksni broj. Indeksni broj izračunava se pomoću hash funkcije. Funkcija raspršivanja rješava sve kolizije do kojih dođe prilikom izračunavanja broja indeksa.
Traženje podatkovne operacije
Operacija pretraživanja koristi se za traženje vrijednosti u hash tablici pomoću broja indeksa. Operacija pretraživanja vraća vrijednost koja je povezana s brojem indeksa pretraživanja. Na primjer, ako pohranimo vrijednost 6 pod indeksom 2, operacija pretraživanja s indeksom broj 2 vratit će vrijednost 6.
Operacija brisanja podataka
Operacija brisanja koristi se za uklanjanje vrijednosti iz hash tablice. Za brisanje Operacija se vrši pomoću broja indeksa. Nakon što je vrijednost izbrisana, indeksni broj postaje slobodan. Može se koristiti za pohranjivanje drugih vrijednosti pomoću operacije umetanja.
Implementacija hash tablice sa Python Primjer
Pogledajmo jednostavan primjer koji izračunava hash vrijednost ključa
def hash_key( key, m):
return key % m
m = 7
print(f'The hash value for 3 is {hash_key(3,m)}')
print(f'The hash value for 2 is {hash_key(2,m)}')
print(f'The hash value for 9 is {hash_key(9,m)}')
print(f'The hash value for 11 is {hash_key(11,m)}')
print(f'The hash value for 7 is {hash_key(7,m)}')
Objašnjenje koda hash tablice
OVDJE,
- Definira funkciju hash_key koja prihvaća parametre key i m.
- Koristi jednostavnu operaciju modula za određivanje hash vrijednosti
- Definira varijablu m koja je inicijalizirana na vrijednost 7. Ovo je veličina naše hash tablice
- Izračunava i ispisuje hash vrijednost 3
- Izračunava i ispisuje hash vrijednost 2
- Izračunava i ispisuje hash vrijednost 9
- Izračunava i ispisuje hash vrijednost 11
- Izračunava i ispisuje hash vrijednost 7
Izvršenje gornjeg koda daje sljedeće rezultate.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Primjer rječnika
Python dolazi s ugrađenim tipom podataka pod nazivom Rječnik. Rječnik je primjer hash tablice. Pohranjuje vrijednosti koristeći par ključeva i vrijednosti. Vrijednosti raspršivanja automatski se generiraju za nas, a sve kolizije rješavaju se za nas u pozadini.
Sljedeći primjer pokazuje kako možete koristiti tip podataka rječnika u piton 3
employee = {
'name': 'John Doe',
'age': 36,
'position': 'Business Manager.'
}
print (f"The name of the employee is {employee['name']}")
employee['position'] = 'Software Engineer'
print (f"The position of {employee['name']} is {employee['position']}")
employee.clear()
print (employee)
OVDJE,
- Definira varijablu rječnika zaposlenik. Naziv ključa koristi se za pohranu vrijednosti John Doe, dob pohranjuje 36, a pozicija pohranjuje vrijednost Business Manager.
- Dohvaća vrijednost naziva ključa i ispisuje je u terminalu
- Ažurira vrijednost ključne pozicije na vrijednost Software Engineer
- Ispisuje vrijednosti naziva i položaja tipki
- Briše sve vrijednosti koje su pohranjene u našoj varijabli rječnika zaposlenik
- Ispisuje vrijednost zaposlenika
Pokretanje gornjeg koda daje sljedeće rezultate.
The name of the employee is John Doe.
The position of John Doe is a Software Engineer.
{}
Analiza složenosti
Hash tablice imaju prosječnu vremensku složenost od O (1) u najboljem slučaju. Vremenska složenost u najgorem slučaju je O(n). Najgori scenarij događa se kada mnoge vrijednosti generiraju isti hash ključ, a mi moramo riješiti koliziju ispitivanjem.
Prijave iz stvarnog svijeta
U stvarnom svijetu, hash tablice se koriste za pohranu podataka za
- Baze podataka
- Asocijativni nizovi
- Kompleti
- Predmemorija memorije
Prednosti hash tablica
Ovdje su prednosti/prednosti korištenja hash tablica:
- Hash tablice imaju visoku izvedbu pri traženju podataka, umetanju i brisanju postojećih vrijednosti.
- Vremenska složenost za hash tablice je konstantna bez obzira na broj stavki u tablici.
- Rade vrlo dobro čak i kada rade s velikim skupovima podataka.
Nedostaci hash tablica
Evo nedostataka upotrebe hash tablica:
- Ne možete koristiti vrijednost null kao ključ.
- Ne mogu se izbjeći kolizije prilikom generiranja ključeva korištenjem. hash funkcije. Do sudara dolazi kada se generira ključ koji je već u upotrebi.
- Ako funkcija raspršivanja ima mnogo kolizija, to može dovesti do smanjenja izvedbe.
rezime
- Hash tablice koriste se za pohranu podataka pomoću para ključeva i vrijednosti.
- Funkcija raspršivanja koristi matematički algoritam za izračunavanje vrijednosti raspršivanja.
- Do sudara dolazi kada se ista hash vrijednost generira za više od jedne vrijednosti.
- Ulančavanje rješava koliziju stvaranjem povezanih popisa.
- Ispitivanje rješava koliziju pronalaženjem praznih utora u hash tablici.
- Linearno ispitivanje traži sljedeći slobodni utor za pohranjivanje vrijednosti počevši od utora u kojem je došlo do sudara.
- Kvadratno ispitivanje koristi polinomske izraze za pronalaženje sljedećeg slobodnog utora kada dođe do sudara.
- Double hashiranje koristi sekundarni algoritam hash funkcije za pronalaženje sljedećeg slobodnog utora kada dođe do kolizije.
- Hash tablice imaju bolje performanse u usporedbi s drugim strukturama podataka.
- Prosječna vremenska složenost hash tablica je O (1)
- Tip podataka rječnika u pythonu primjer je hash tablice.
- Hash tablice podržavaju operacije umetanja, pretraživanja i brisanja.
- Null vrijednost ne može se koristiti kao vrijednost indeksa.
- U hash funkcijama se ne mogu izbjeći kolizije. Dobra hash funkcija smanjuje broj kolizija do kojih dolazi kako bi se poboljšala izvedba.
