Što je hashiranje?
Hash je vrijednost koja ima fiksnu duljinu i generira se pomoću matematičke formule. Vrijednosti hasha koriste se u kompresiji podataka, kriptologiji itd. U indeksiranju podataka koriste se hash vrijednosti jer imaju fiksnu veličinu duljine bez obzira na vrijednosti koje su korištene za njihovo generiranje. To čini hash vrijednosti da zauzmu minimalni prostor u usporedbi s drugim vrijednostima različitih duljina.
Hash funkcija koristi matematički algoritam za pretvaranje ključa u hash. Do sudara dolazi kada hash funkcija daje istu vrijednost raspršivanja za više od jednog ključa.
U ovom vodiču iz algoritma naučit ćete:
- Što je hashiranje?
- Što je Hash tablica?
- Hash funkcije
- Kvalitete dobre hash funkcije
- Sudar
- Operacije hash tablice
- Primjer Python hash tablice
- Objašnjenje koda tablice heširanja
- Primjer rječnika Pythona
- Analiza složenosti
- Aplikacije u stvarnom svijetu
- Prednosti hash tablica
- Mane hash tablica
Što je Hash tablica?
Hash tablicu je struktura podataka koja pohranjuje vrijednosti pomoću par ključeva i vrijednosti. Svakoj se vrijednosti dodjeljuje 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.
Broj zaposlenika možemo koristiti kao ključ i podatke o zaposleniku dodijeliti kao vrijednost.
Gornji pristup zahtijevat će dodatni slobodni prostor reda (m * n 2 ) gdje je varijabla m veličina polja, a varijabla n broj znamenki za broj zaposlenika. Ovaj pristup uvodi problem skladišnog prostora.
Hash funkcija rješava gornji problem dobivanjem broja zaposlenika i upotrebom njega za generiranje cjelobrojne vrijednosti raspršivanja, fiksnih znamenki i optimizacijom prostora za pohranu. Svrha hash funkcije je stvoriti ključ koji će se koristiti za upućivanje na vrijednost 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č.
- k 1 % 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 fiksne veličine 3 i sljedeće vrijednosti
[1,2,3]
Gornju formulu možemo koristiti za izračunavanje pozicija koje bi svaka vrijednost trebala zauzimati.
Sljedeća slika prikazuje dostupne indekse u našoj hash tablici.
Korak 1)
Izračunajte položaj koji će tako zauzimati prva vrijednost
h (1) = 1% 3
= 1
Vrijednost 1 zauzet će prostor na indeksu 1
Korak 2)
Izračunajte položaj koji će zauzimati druga vrijednost
h (2) = 2% 3
= 2
Vrijednost 2 zauzet će prostor na indeksu 2
Korak 3)
Izračunajte položaj koji će zauzimati treća vrijednost.
h (3) = 3% 3
= 0
Vrijednost 3 zauzet će prostor na indeksu 0
Konačni rezultat
Naša popunjena 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 će se pohraniti u algoritam.
- Hash funkcija treba generirati jedinstvene hash vrijednosti čak i za ulazne podatke koji imaju jednaku količinu.
- Funkcija bi trebala smanjiti broj sudara. Do sudara dolazi kada se ista vrijednost generira za više od jedne vrijednosti.
- Vrijednosti se moraju dosljedno rasporediti po svim mogućim hashovima.
Sudar
Do sudara dolazi kada algoritam generira isto raspršivanje 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 (k 1 % m) gdje je m veličina hash tablice.
Sljedeća tablica prikazuje heš vrijednosti koje će se generirati.
| Ključ | Algoritam raspršivanja (k 1 % m) | Hash 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.
Dati problem može se riješiti ili lancem ili sondiranjem. Sljedeći odjeljci detaljno raspravljaju o lančanom radu i ispitivanju.
Ulančavanje
Chaining je tehnika koja se koristi za rješavanje problema sudara pomoću povezanih popisa koji imaju jedinstvene indekse.
Sljedeća slika vizualizira kako izgleda ulančani popis
I 2 i 9 zauzimaju isti indeks, ali pohranjeni su kao povezani popisi. Svaki popis ima jedinstveni identifikator.
Prednosti okovanih popisa
Slijede prednosti lančanog popisa:
- Ulančani popisi imaju bolju izvedbu pri umetanju podataka jer je redoslijed umetanja O (1).
- Nije potrebno mijenjati veličinu hash tablice koja koristi ulančani popis.
- Lako može primiti velik broj vrijednosti sve dok je na raspolaganju slobodan prostor.
Sondiranje
Druga tehnika koja se koristi za rješavanje sudara je sondiranje. Kada se koristi metoda sondiranja, ako dođe do sudara, jednostavno možemo krenuti dalje i pronaći prazan utor za pohranu naše vrijednosti.
Slijede metode ispitivanja:
| Metoda | Opis |
| Linearno sondiranje | Baš kao što i samo ime govori, ova metoda traži prazne utore linearno počevši od položaja na kojem se sudar dogodio i krećući se naprijed. Ako se dođe do kraja popisa i ne pronađe prazno mjesto. Sondiranje započinje na početku popisa. |
| Kvadratno sondiranje | Ova metoda koristi kvadratne polinomske izraze kako bi pronašla sljedeći slobodni utor. |
| Dvostruko raspršivanje | Ova tehnika koristi sekundarni algoritam hash funkcije za pronalaženje sljedećeg slobodnog utora. |
Koristeći naš gornji primjer, hash tablica nakon korištenja sondiranja prikazala bi se na sljedeći način:
Operacije hash tablice
Evo, podržavaju li operacije Hash tablice:
- Umetanje - ova se operacija koristi za dodavanje elementa u hash tablicu
- Pretraživanje - ova se operacija koristi za traženje elemenata u hash tablici pomoću ključa
- Brisanje - ova se operacija koristi za brisanje elemenata iz hash tablice
Umetanje podataka
Operacija umetanja koristi se za spremanje vrijednosti u tablicu raspršivanja. Kad se nova vrijednost pohrani u hash tablicu, dodjeljuje joj se indeksni broj. Broj indeksa izračunava se pomoću hash funkcije. Funkcija raspršivanja rješava svaki sudar koji se dogodi prilikom izračuna broja indeksa.
Potražite operaciju podataka
Operacija pretraživanja koristi se za traženje vrijednosti u hash tablici pomoću indeksnog broja. Operacija pretraživanja vraća vrijednost koja je povezana s brojem indeksa pretraživanja. Na primjer, ako vrijednost 6 pohranimo u indeks 2, operacija pretraživanja s indeksnim brojem 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 indeksnog broja. Nakon što je vrijednost izbrisana, indeksni broj postaje besplatan. Može se koristiti za spremanje drugih vrijednosti pomoću operacije umetanja.
Primjena hash tablice na primjeru Python
Pogledajmo jednostavan primjer koji izračunava hash vrijednost ključa
def hash_key( key, m):return key % mm = 7print(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 tablice heširanja
OVDJE,
- Definira funkciju hash_key koja prihvaća ključ parametara 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 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Primjer rječnika Pythona
Python dolazi s ugrađenim tipom podataka koji se naziva Rječnik. Rječnik je primjer hash tablice. Pohranjuje vrijednosti pomoću para ključeva i vrijednosti. Vrijednosti hasha automatski se generiraju za nas, a svi sudari se rješavaju u pozadini.
Sljedeći primjer pokazuje kako možete koristiti tip podataka rječnika u python 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 godina, a pozicija pohranjuje vrijednost Business Manager.
- Dohvaća vrijednost imena ključa i ispisuje ga u terminalu
- Ažurira vrijednost položaja ključa na vrijednost Softverski inženjer
- Ispisuje vrijednosti imena i položaja tipki
- Briše sve vrijednosti koje su pohranjene u našoj rječničkoj varijabli 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 O (1) u najboljem slučaju. Složenost vremena u najgorem slučaju je O (n). Najgori se scenarij događa kada mnoge vrijednosti generiraju isti hash ključ, a sudar moramo riješiti ispitivanjem.
Aplikacije u stvarnom svijetu
U stvarnom se svijetu hash tablice koriste za pohranu podataka za
- Baze podataka
- Asocijativni nizovi
- Kompleti
- Predmemorija memorije
Prednosti hash tablica
Evo prednosti / prednosti upotrebe hash tablica:
- Hash tablice imaju visoke performanse prilikom pretraživanja podataka, umetanja i brisanja postojećih vrijednosti.
- Složenost vremena za hash tablice konstantna je bez obzira na broj stavki u tablici.
- Izvode se vrlo dobro čak i kada rade s velikim skupovima podataka.
Mane hash tablica
Evo slabosti upotrebe hash tablica:
- Ne možete koristiti null vrijednost kao ključ.
- Sukobi se ne mogu izbjeći prilikom generiranja ključeva pomoću. hash funkcije. Do sudara dolazi kada se generira ključ koji se već koristi.
- Ako funkcija raspršivanja ima mnogo sudara, to može dovesti do smanjenja performansi.
Sažetak:
- Hash tablice koriste se za pohranu podataka pomoću para ključeva i vrijednosti.
- Hash funkcija koristi matematički algoritam za izračunavanje hash vrijednosti.
- Do sudara dolazi kada se ista hash vrijednost generira za više od jedne vrijednosti.
- Lančanim rješavanjem sudara nastaje stvaranjem povezanih popisa.
- Sondiranje rješava sudar pronalaženjem praznih utora u hash tablici.
- Linearno sondiranje traži sljedeći slobodni utor za pohranu vrijednosti počevši od utora u kojem je došlo do sudara.
- Kvadratno sondiranje koristi polinomske izraze kako bi pronašlo sljedeći slobodni utor kada dođe do sudara.
- Dvostruko raspršivanje koristi sekundarni algoritam raspršivanja kako bi pronašao sljedeći slobodni utor kada dođe do sudara.
- 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.
- Sukobi se ne mogu izbjeći u hash funkcijama. Dobra hash funkcija minimalizira broj sudara koji se javljaju radi poboljšanja performansi.