Mis on räsimine?
Räsi on fikseeritud pikkusega väärtus ja see luuakse matemaatilise valemi abil. Räsi väärtusi kasutatakse andmete tihendamisel, krüptoloogias jne. Andmete indekseerimisel kasutatakse räsiväärtusi, kuna nende pikkus on fikseeritud olenemata väärtustest, mida nende loomiseks kasutati. See muudab räsiväärtused minimaalse ruumi hõivamiseks võrreldes teiste erineva pikkusega väärtustega.
Räsifunktsioon kasutab matemaatilist algoritmi, et muuta võti räsi. Kokkupõrge toimub siis, kui räsifunktsioon loob sama räsiväärtuse rohkem kui ühe võtme jaoks.
Selles algoritmi õpetuses saate teada:
- Mis on räsimine?
- Mis on hash tabel?
- Räsifunktsioonid
- Hea räsifunktsiooni omadused
- Kokkupõrge
- Räsitabeli toimingud
- Hash Table Pythoni näide
- Räsi tabeli koodi selgitus
- Pythoni sõnastiku näide
- Keerukuse analüüs
- Reaalsetes rakendustes
- Räsitabelite eelised
- Räsitabelite puudused
Mis on hash tabel?
Hash tabelit on andmete struktuur, mis salvestab väärtused kasutades paari võtmeid ja väärtusi. Igale väärtusele määratakse unikaalne võti, mis on loodud räsifunktsiooni abil.
Võtme nime kasutatakse sellega seotud väärtusele juurdepääsemiseks. See muudab räsitabeli väärtuste otsimise väga kiireks, sõltumata räsitabeli üksuste arvust.
Räsifunktsioonid
Näiteks kui soovime salvestada töötajate arvestust ja iga töötaja identifitseeritakse töötaja numbri abil ainulaadselt.
Võime kasutada võtmena töötaja numbrit ja väärtuseks määrata töötaja andmed.
Ülaltoodud lähenemisviis nõuab täiendavat vaba ruumi suurusjärgus (m * n 2 ), kus muutuja m on massiivi suurus ja muutuja n on töötaja arvu numbrite arv. Selle lähenemisviisiga kaasneb salvestusruumi probleem.
Räsifunktsioon lahendab ülaltoodud probleemi, hankides töötaja numbri ja kasutades seda räsi täisarvu, fikseeritud numbrite ja mäluruumi optimeerimiseks. Räsifunktsiooni eesmärk on luua võti, mida kasutatakse väärtuse viitamiseks, mida me tahame salvestada. Funktsioon aktsepteerib salvestatava väärtuse ja kasutab seejärel võtme väärtuse arvutamiseks algoritmi.
Järgnev on näide lihtsast räsifunktsioonist
h(k) = k1 % m
SIIN,
- h (k) on räsifunktsioon, mis aktsepteerib parameetri k. Parameeter k on väärtus, millele soovime võtme arvutada.
- k 1 % m on meie räsifunktsiooni algoritm, kus k1 on väärtus, mida soovime salvestada, ja m on loendi suurus. Võtme arvutamiseks kasutame moodulioperaatorit.
Näide
Oletame, et meil on fikseeritud suurusega 3 loend ja järgmised väärtused
[1,2,3]
Saame ülaltoodud valemi abil arvutada positsioonid, mille iga väärtus peaks hõivama.
Järgmisel pildil on meie räsitabeli saadaolevad indeksid.
Samm 1)
Arvutage positsioon, mille hõivab esimene väärtus
h (1) = 1% 3
= 1
Väärtus 1 hõivab indeksi 1 ruumi
2. samm)
Arvutage positsioon, mille hõivab teine väärtus
h (2) = 2% 3
= 2
Väärtus 2 hõivab indeksi 2 ruumi
3. samm)
Arvutage positsioon, mille hõivab kolmas väärtus.
h (3) = 3% 3
= 0
Väärtus 3 hõivab indeksi 0 ruumi
Lõpptulemus
Meie täidetud räsitabel on nüüd järgmine.
Hea räsifunktsiooni omadused
Hea räsifunktsioonil peaksid olema järgmised omadused.
- Räsi genereerimise valem peaks kasutama algoritmis salvestatavate andmete väärtust.
- Räsifunktsioon peaks genereerima ainulaadsed räsiväärtused isegi sama palju sisendandmete jaoks.
- Funktsioon peaks kokkupõrgete arvu minimeerima. Kokkupõrked toimuvad siis, kui sama väärtus genereeritakse mitme väärtuse jaoks.
- Väärtused tuleb jaotada järjepidevalt kogu võimaliku räsi ulatuses.
Kokkupõrge
Kokkupõrge toimub siis, kui algoritm genereerib sama räsi rohkem kui ühe väärtuse jaoks.
Vaatame ühte näidet.
Oletame, et meil on järgmine väärtuste loend
[3,2,9,11,7]
Oletame, et räsi tabeli suurus on 7, ja me kasutame valemit (k 1 % m), kus m on räsitabeli suurus.
Järgmine tabel näitab genereeritavaid räsiväärtusi.
| Võti | Hashi algoritm (k 1 % m) | Räsi väärtus |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Nagu ülaltoodud tulemustest näeme, on väärtustel 2 ja 9 sama räsiväärtus ning me ei saa igas positsioonis salvestada rohkem kui ühte väärtust.
Antud probleemi saab lahendada kas aheldamise või sondeerimisega. Järgmistes osades käsitletakse üksikasjalikult aheldamist ja sondeerimist.
Aheldamine
Aheldamine on tehnika, mida kasutatakse kokkupõrke probleemi lahendamiseks lingitud loendite abil, millel kõigil on ainulaadsed indeksid.
Järgmine pilt visualiseerib, kuidas aheldatud loend välja näeb
Nii 2 kui 9 hõivavad sama indeksit, kuid need salvestatakse lingitud loenditena. Igal loendil on kordumatu identifikaator.
Aheldatud loendite eelised
Aheldatud loendite eelised on järgmised:
- Aheldatud loenditel on andmete sisestamisel parem jõudlus, kuna sisestamise järjekord on O (1).
- Aheldatud loendit kasutava räsitabeli suurust ei ole vaja muuta.
- See mahutab hõlpsasti suure hulga väärtusi, kui vaba ruumi on vaba.
Sondeerimine
Teine tehnika, mida kasutatakse kokkupõrke lahendamiseks, on sondeerimine. Proovimeetodi kasutamisel saame kokkupõrke korral lihtsalt edasi liikuda ja leida tühi pesa oma väärtuse salvestamiseks.
Järgnevad on sondeerimismeetodid:
| Meetod | Kirjeldus |
| Lineaarne sondeerimine | Täpselt nagu nimigi ütleb, otsib see meetod tühje pesasid lineaarselt, alustades kokkupõrke asukohast ja liikudes edasi. Kui loendi lõpp on käes ja tühja pesa ei leita. Sondeerimine algab loendi algusest. |
| Teise astme sondeerimine | See meetod kasutab järgmise saadaoleva vaba pesa leidmiseks kvadratiivseid polünoomväljendeid. |
| Topelt räsimine | See tehnika kasutab teise vaba saadaoleva pesa leidmiseks sekundaarset räsifunktsiooni algoritmi. |
Kasutades meie ülaltoodud näidet, ilmub pärast sondeerimist räsitabel järgmiselt:
Räsitabeli toimingud
Siin on toimingud, mida Hash-tabelid toetavad:
- Sisestamine - seda toimingut kasutatakse elemendi lisamiseks räsitabelisse
- Otsimine - seda toimingut kasutatakse klahvi abil räsitabeli elementide otsimiseks
- Kustutamine - seda toimingut kasutatakse elementide kustutamiseks räsitabelist
Andmete sisestamine
Sisestusoperatsiooni kasutatakse väärtuste salvestamiseks räsi tabelis. Kui räsitabelisse on salvestatud uus väärtus, määratakse sellele indeksi number. Indeksinumber arvutatakse räsifunktsiooni abil. Räsifunktsioon lahendab kõik indeksinumbri arvutamisel tekkivad kokkupõrked.
Andmetoimingute otsimine
Otsinguoperatsiooni kasutatakse räsitabeli väärtuste otsimiseks indeksi numbri abil. Otsinguoperatsioon tagastab väärtuse, mis on seotud otsinguindeksi numbriga. Näiteks kui salvestame väärtuse 6 indeksisse 2, tagastab otsinguoperatsioon indeksinumbriga 2 väärtuse 6.
Andmete kustutamine
Kustutustoimingut kasutatakse räsitabeli väärtuse eemaldamiseks. Toimingu kustutamiseks kasutatakse registrinumbrit. Kui väärtus on kustutatud, vabastatakse indeksinumber. Seda saab sisestamise abil kasutada muude väärtuste salvestamiseks.
Räsitabeli rakendamine Pythoni näitega
Vaatame lihtsat näidet, mis arvutab võtme räsi väärtuse
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)}')
Räsi tabeli koodi selgitus
SIIN,
- Määrab funktsiooni hash_key, mis aktsepteerib parameetrite võtme ja m.
- Kasutab räsi väärtuse määramiseks lihtsat moodulioperatsiooni
- Määratleb muutuja m, mis initsialiseeritakse väärtuseks 7. See on meie räsitabeli suurus
- Arvutab ja prindib räsi väärtuse 3
- Arvutab ja prindib räsi väärtuse 2
- Arvutab ja prindib räsi väärtuse 9
- Arvutab ja prindib räsi väärtuse 11
- Arvutab ja prindib räsi väärtuse 7
Ülaltoodud koodi käivitamine annab järgmised tulemused.
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
Pythoni sõnastiku näide
Pythonil on sisseehitatud andmetüüp nimega Sõnastik. Sõnastik on räsitabeli näide. See salvestab väärtused paari võtme ja väärtuse abil. Räsiväärtused genereeritakse meie jaoks automaatselt ja kõik kokkupõrked lahendatakse meie jaoks taustal.
Järgmine näide näitab, kuidas saate Python 3-s kasutada sõnastiku andmetüüpi
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)
SIIN,
- Määratleb sõnastiku muutuja töötaja. Võtme nime kasutatakse väärtuse salvestamiseks John Doe, vanus 36 ja positsioon kaupluses väärtus Business Manager.
- Toob võtme nime väärtuse ja prindib selle terminali
- Värskendab võtmepositsiooni väärtust väärtuseks Software Engineer
- Prindib võtmete nime ja asukoha väärtused
- Kustutab kõik meie sõnastiku muutuja töötaja salvestatud väärtused
- Prindib töötaja väärtuse
Ülaltoodud koodi käivitamine annab järgmised tulemused.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Keerukuse analüüs
Hash-tabelite keskmine ajaline keerukus on parimal juhul O (1). Halvimal juhul on aja keerukus O (n). Halvim stsenaarium ilmneb siis, kui paljud väärtused genereerivad sama räsivõtme ja peame kokkupõrke lahendama sondeerimisega.
Reaalsetes rakendustes
Reaalses maailmas kasutatakse räsi tabeleid andmete salvestamiseks
- Andmebaasid
- Assotsiatiivsed massiivid
- Komplektid
- Mälu vahemälu
Räsitabelite eelised
Siin on räsitabelite kasutamise plussid / eelised:
- Hash-tabelid on andmete jõudmisel, olemasolevate väärtuste sisestamisel ja kustutamisel suure jõudlusega.
- Räsitabelite ajaline keerukus on konstantne, olenemata tabeli üksuste arvust.
- Need toimivad väga hästi ka suurte andmekogumitega töötades.
Räsitabelite puudused
Siin on räsi tabelite kasutamise miinused:
- Nullväärtust ei saa võtmena kasutada.
- Kasutades võtmeid genereerides ei saa kokkupõrkeid vältida. räsifunktsioonid. Kokkupõrked toimuvad juba kasutusel oleva võtme genereerimisel.
- Kui räsimisfunktsioonil on palju kokkupõrkeid, võib see põhjustada jõudluse vähenemist.
Kokkuvõte:
- Räsi tabeleid kasutatakse andmete salvestamiseks, kasutades paari võtit ja väärtust.
- Räsifunktsioon kasutab räsi väärtuse arvutamiseks matemaatilist algoritmi.
- Kokkupõrge toimub siis, kui sama räsiväärtus genereeritakse mitme väärtuse jaoks.
- Ketid lahendavad kokkupõrke lingitud loendite loomisega.
- Sondeerimine lahendab kokkupõrke, leides räsitabelist tühjad pilud.
- Lineaarne sondeerimine otsib järgmist vaba pesa, et salvestada väärtus alates pesast, kus kokkupõrge toimus.
- Teise astme sondeerimine kasutab kokkupõrke korral järgmise vaba pesa leidmiseks polünoomväljendeid.
- Topelt räsimine kasutab teise vaba pilu leidmiseks kokkupõrke korral sekundaarset räsimisfunktsiooni algoritmi.
- Räsi tabelid on teiste andmestruktuuridega võrreldes paremad.
- Räsitabelite keskmine ajaline keerukus on O (1)
- Sõnaraamatu andmetüüp pythonis on räsitabeli näide.
- Räsi tabelid toetavad sisestamise, otsingu ja kustutamise toiminguid.
- Nullväärtust ei saa kasutada indeksi väärtusena.
- Räsifunktsioonides ei saa kokkupõrkeid vältida. Hea räsifunktsioon minimeerib jõudluse parandamiseks toimuvate kokkupõrgete arvu.