Hash tablica u strukturi podataka: Python Primjer

Š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 * n²) gdje je varijabla m veličina poredak, a varijabla n je broj znamenki za broj zaposlenika. Ovaj pristup uvodi problem skladišnog prostora.

Hash funkcija rješava gore navedeni problem dobivanjem broja zaposlenika i njegovim korištenjem za generiranje hash cjelobrojne vrijednosti, fiksnih znamenki i optimiziranje prostora za pohranu. Svrha hash funkcije je stvaranje ključa koji će se koristiti za referenciranje vrijednosti koju želimo pohraniti. Funkcija prihvaća vrijednost koju treba spremiti, a zatim koristi algoritam za izračun 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₁ % 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 (k₁ % m) gdje je m veličina hash tablice.

Sljedeća tablica prikazuje hash vrijednosti koje će se generirati.

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:

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)}')

Hash tablica Code Objašnjenje

OVDJE,

1. Definira funkciju hash_key koja prihvaća parametre key i m.
2. Koristi jednostavnu operaciju modula za određivanje hash vrijednosti
3. Definira varijablu m koja je inicijalizirana na vrijednost 7. Ovo je veličina naše hash tablice
4. Izračunava i ispisuje hash vrijednost 3
5. Izračunava i ispisuje hash vrijednost 2
6. Izračunava i ispisuje hash vrijednost 9
7. Izračunava i ispisuje hash vrijednost 11
8. 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,

1. Definira varijablu rječnika zaposlenik. Naziv ključa koristi se za pohranu vrijednosti John Doe, dob pohranjuje 36, a pozicija pohranjuje vrijednost Business Manager.
2. Dohvaća vrijednost naziva ključa i ispisuje je u terminalu
3. Ažurira vrijednost ključne pozicije na vrijednost Software Engineer
4. Ispisuje vrijednosti naziva i položaja tipki
5. Briše sve vrijednosti koje su pohranjene u našoj varijabli rječnika zaposlenik
6. 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.

Pitanja i odgovori