Kaj je Hashing?
Razpršitev je vrednost s fiksno dolžino in se ustvari z uporabo matematične formule. Vrednosti razpršitve se uporabljajo pri stiskanju podatkov, kriptologiji itd. Pri indeksiranju podatkov se uporabljajo razpršene vrednosti, ker imajo nespremenljivo dolžino, ne glede na vrednosti, ki so bile uporabljene za njihovo ustvarjanje. Vrednosti zgoščevanja zasedajo minimalni prostor v primerjavi z drugimi vrednostmi različnih dolžin.
Funkcija zgoščevanja uporablja matematični algoritem za pretvorbo ključa v razpršitev. Do trčenja pride, ko funkcija zgoščevanja ustvari isto vrednost zgoščevanja za več kot en ključ.
V tej vadnici Algoritma boste izvedeli:
- Kaj je Hashing?
- Kaj je Hash tabela?
- Funkcije razpršitve
- Kakovosti dobre razpršene funkcije
- Trčenje
- Operacije razprševalne tabele
- Primer razpršilne tabele Python
- Pojasnilo kode tabele hash
- Primer slovarja Python
- Analiza kompleksnosti
- Aplikacije iz resničnega sveta
- Prednosti hash tabel
- Slabosti hash tabel
Kaj je Hash tabela?
Razpršene tabele je struktura podatkov, ki shranjuje vrednosti uporablja par ključev in vrednosti. Vsaki vrednosti je dodeljen unikatni ključ, ki je ustvarjen s pomočjo zgoščevalne funkcije.
Ime ključa se uporablja za dostop do povezane vrednosti. Zaradi tega je iskanje vrednosti v zgoščeni tabeli zelo hitro, ne glede na število elementov v razpršeni tabeli.
Funkcije razpršitve
Na primer, če želimo shraniti evidence zaposlenih in je vsak zaposleni enolično identificiran s pomočjo številke zaposlenega.
Številko zaposlenega lahko uporabimo kot ključ, podatke o zaposlenem pa dodelimo kot vrednost.
Zgornji pristop bo zahteval dodaten prosti prostor vrstnega reda (m * n 2 ), kjer je spremenljivka m velikost matrike, spremenljivka n pa število števk za številko zaposlenega. Ta pristop predstavlja težavo s prostorom za shranjevanje.
Z zgoščevalno funkcijo zgoraj navedeno težavo rešite tako, da dobite številko zaposlenega in jo uporabite za generiranje celoštevilske vrednosti zgoščene številke, fiksnih številk in optimiziranja prostora za shranjevanje. Namen zgoščevalne funkcije je ustvariti ključ, ki se bo uporabljal za sklicevanje na vrednost, ki jo želimo shraniti. Funkcija sprejme vrednost, ki jo želite shraniti, nato pa uporabi algoritem za izračun vrednosti ključa.
Sledi primer preproste zgoščevalne funkcije
h(k) = k1 % m
TUKAJ,
- h (k) je zgoščevalna funkcija, ki sprejme parameter k. Parameter k je vrednost, za katero želimo izračunati ključ.
- k 1 % m je algoritem za našo zgoščevalno funkcijo, kjer je k1 vrednost, ki jo želimo shraniti, in m je velikost seznama. Za izračun ključa uporabljamo operator modula.
Primer
Predpostavimo, da imamo seznam s fiksno velikostjo 3 in naslednjimi vrednostmi
[1,2,3]
Zgornjo formulo lahko uporabimo za izračun položajev, ki jih mora zavzeti vsaka vrednost.
Naslednja slika prikazuje razpoložljive indekse v naši hash tabeli.
Korak 1)
Izračunajte položaj, ki ga bo tako zavzela prva vrednost
h (1) = 1% 3
= 1
Vrednost 1 bo zasedla prostor na indeksu 1
2. korak)
Izračunajte položaj, ki ga bo zasedla druga vrednost
h (2) = 2% 3
= 2
Vrednost 2 bo zasedla prostor na indeksu 2
3. korak)
Izračunajte položaj, ki ga bo zasedla tretja vrednost.
h (3) = 3% 3
= 0
Vrednost 3 bo zasedla prostor na indeksu 0
Končni rezultat
Naša izpolnjena hash tabela bo zdaj naslednja.
Kakovosti dobre razpršene funkcije
Dobra zgoščevalna funkcija mora imeti naslednje lastnosti.
- Formula za generiranje zgoščene oznake mora uporabljati vrednost podatkov, ki se shrani v algoritmu.
- Funkcija zgoščevanja bi morala ustvariti edinstvene vrednosti zgoščevanja tudi za vhodne podatke z enako količino.
- Funkcija mora zmanjšati število trkov. Do trkov pride, ko se ista vrednost ustvari za več kot eno vrednost.
- Vrednosti morajo biti dosledno porazdeljene po vseh možnih zgoščenih točkah.
Trčenje
Do trka pride, ko algoritem generira isto razpršitev za več kot eno vrednost.
Oglejmo si primer.
Recimo, da imamo naslednji seznam vrednosti
[3,2,9,11,7]
Predpostavimo, da je velikost hash tabele 7, in uporabili bomo formulo (k 1 % m), kjer je m velikost hash tabele.
Naslednja tabela prikazuje zgoščene vrednosti, ki bodo ustvarjene.
| Ključ | Algoritem razpršitve (k 1 % m) | Vrednost razpršitve |
| 3. | 3% 7 | 3. |
| 2. | 3% 7 | 2. |
| 9. | 3% 7 | 2. |
| 11. | 3% 7 | 4. |
| 7. | 3% 7 | 0 |
Kot lahko vidimo iz zgornjih rezultatov, imata vrednosti 2 in 9 enako zgoščeno vrednost in na vsaki poziciji ne moremo shraniti več kot ene vrednosti.
Dano težavo je mogoče rešiti bodisi z veriženjem bodisi s sondiranjem. Naslednji razdelki podrobno razpravljajo o veriženju in tipanju.
Veriženje
Veriženje je tehnika, ki se uporablja za reševanje problema trka z uporabo povezanih seznamov, ki imajo vsak unikatne indekse.
Naslednja slika prikazuje, kako izgleda okovan seznam
Tako 2 kot 9 zasedata isti indeks, vendar sta shranjena kot povezana seznama. Vsak seznam ima edinstven identifikator.
Prednosti okovanih seznamov
Prednosti veriženih seznamov so naslednje:
- Verižni seznami imajo boljšo zmogljivost pri vstavljanju podatkov, ker je vrstni red vstavljanja O (1).
- Ni treba spreminjati velikosti razpršilne tabele, ki uporablja verižen seznam.
- Z lahkoto lahko sprejme veliko število vrednosti, če je na voljo prosti prostor.
Sondiranje
Druga tehnika, ki se uporablja za reševanje trka, je sondiranje. Če pride do trka pri uporabi metode tipanja, lahko preprosto nadaljujemo in poiščemo prazno režo za shranjevanje naše vrednosti.
Sledijo metode sondiranja:
| Metoda | Opis |
| Linearno sondiranje | Tako kot že ime pove, ta metoda išče prazne reže linearno, začenši s položaja, kjer je prišlo do trka, in naprej. Če je konec seznama dosežen in prazne reže ni mogoče najti. Sondiranje se začne na začetku seznama. |
| Kvadratno sondiranje | Ta metoda uporablja kvadratne polinomske izraze za iskanje naslednje proste reže. |
| Dvojno razprševanje | Ta tehnika uporablja algoritem sekundarne zgoščevalne funkcije za iskanje naslednje proste razpoložljive reže. |
Z uporabo zgornjega primera bi se hash tabela po uporabi tipala prikazala na naslednji način:
Operacije razprševalne tabele
Tu so operacije, ki jih podpirajo tabele Hash:
- Vstavljanje - ta operacija se uporablja za dodajanje elementa v razpršilno tabelo
- Iskanje - ta operacija se uporablja za iskanje elementov v razpršeni tabeli s pomočjo ključa
- Brisanje - ta operacija se uporablja za brisanje elementov iz razpršilne tabele
Vstavljanje podatkovne operacije
Operacija vstavljanja se uporablja za shranjevanje vrednosti v razpršeni tabeli. Ko je nova vrednost shranjena v razpršeni tabeli, ji je dodeljena indeksna številka. Številka indeksa se izračuna s pomočjo zgoščevalne funkcije. Funkcija zgoščevanja razreši vsa trčenja, ki se pojavijo pri izračunu indeksnega števila.
Poiščite podatkovno operacijo
Iskalna operacija se uporablja za iskanje vrednosti v razpršeni tabeli s pomočjo indeksne številke. Iskalna operacija vrne vrednost, ki je povezana s številko indeksa iskanja. Če na primer vrednost 6 shranimo v indeks 2, bo iskalna operacija z indeksno številko 2 vrnila vrednost 6.
Postopek brisanja podatkov
Operacija brisanja se uporablja za odstranjevanje vrednosti iz zgoščene tabele. Če želite izbrisati operacijo, uporabite številko indeksa. Ko je vrednost izbrisana, se indeksna številka sprosti. Uporabite ga lahko za shranjevanje drugih vrednosti z uporabo vstavitve.
Izvedba tabele razprševanja s primerom Python
Oglejmo si preprost primer, ki izračuna zgoščeno vrednost 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)}')
Pojasnilo kode tabele hash
TUKAJ,
- Določi funkcijo hash_key, ki sprejme ključ parametrov in m.
- Za določitev zgoščene vrednosti uporablja preprosto operacijo modula
- Določa spremenljivko m, ki je inicializirana na vrednost 7. To je velikost naše hash tabele
- Izračuna in natisne hash vrednost 3
- Izračuna in natisne zgoščeno vrednost 2
- Izračuna in natisne zgoščeno vrednost 9
- Izračuna in natisne hash vrednost 11
- Izračuna in natisne zgoščeno vrednost 7
Izvedba zgornje kode povzroči naslednje 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
Primer slovarja Python
Python ima vgrajen podatkovni tip, imenovan Dictionary. Slovar je primer hash tabele. Vrednosti shrani z uporabo para ključev in vrednosti. Vrednosti zgoščevanja se samodejno generirajo za nas, morebitna trčenja pa se rešijo v ozadju.
Naslednji primer prikazuje, kako lahko v slovarju python 3 uporabite podatkovni tip slovarja
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)
TUKAJ,
- Določa spremenljivko slovarja uslužbenec. Ime ključa se uporablja za shranjevanje vrednosti John Doe, starost shrani 36 let, in položaj shrani vrednost Business Manager.
- Pridobi vrednost imena ključa in jo natisne v terminalu
- Posodobi vrednost položaja ključa na vrednost Software Engineer
- Natisne vrednosti imena in položaja tipk
- Izbriše vse vrednosti, ki so shranjene v naši slovarški spremenljivki zaposleni
- Natisne vrednost zaposlenega
Zagon zgornje kode daje naslednje rezultate.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Analiza kompleksnosti
Hash tabele imajo v najboljšem primeru povprečno časovno zapletenost O (1). Najslabša časovna zapletenost je O (n). Najslabši scenarij se zgodi, ko številne vrednosti generirajo isti hash ključ, trk pa moramo rešiti s sondiranjem.
Aplikacije iz resničnega sveta
V resničnem svetu se hash tabele uporabljajo za shranjevanje podatkov za
- Zbirke podatkov
- Asociativni nizi
- Kompleti
- Predpomnilnik
Prednosti hash tabel
Tu so prednosti / prednosti uporabe zgoščevalnih tabel:
- Hash tabele imajo visoko zmogljivost pri iskanju podatkov, vstavljanju in brisanju obstoječih vrednosti.
- Časovna zapletenost hash tabel je konstantna ne glede na število elementov v tabeli.
- Zelo dobro se obnesejo tudi pri delu z velikimi nabori podatkov.
Slabosti hash tabel
Tu so še slabosti uporabe hash tabel:
- Kot ključ ne morete uporabiti ničelne vrednosti.
- Pri ustvarjanju ključev z uporabo trkov se ni mogoče izogniti. hash funkcije. Do trkov pride, ko je generiran ključ, ki je že v uporabi.
- Če ima funkcija razprševanja več trkov, lahko to povzroči zmanjšanje zmogljivosti.
Povzetek:
- Hash tabele se uporabljajo za shranjevanje podatkov z uporabo para ključev in vrednosti.
- Razpršilna funkcija uporablja matematični algoritem za izračun razpršene vrednosti.
- Do trčenja pride, ko se ista hash vrednost ustvari za več kot eno vrednost.
- Veriženje rešuje trčenje z ustvarjanjem povezanih seznamov.
- Sondiranje reši trk z iskanjem praznih rež v razpršeni tabeli.
- Linearno testiranje išče naslednjo prosto režo, da shrani vrednost, začenši z režo, kjer je prišlo do trka.
- Kvadratno sondiranje uporablja polinomske izraze za iskanje naslednje proste reže, ko pride do trka.
- Dvojno zgoščevanje uporablja algoritem sekundarne zgoščevalne funkcije, da poišče naslednjo prosto režo, ko pride do trka.
- Hash tabele imajo boljšo zmogljivost v primerjavi z drugimi podatkovnimi strukturami.
- Povprečna časovna zapletenost hash tabel je O (1)
- Podatkovni tip slovarja v pythonu je primer razpršilne tabele.
- Hash tabele podpirajo operacije vstavljanja, iskanja in brisanja.
- Ničelne vrednosti ni mogoče uporabiti kot vrednost indeksa.
- Trkov se ne more izogniti v zgoščevalnih funkcijah. Dobra zgoščevalna funkcija zmanjša število trkov, da se izboljša zmogljivost.