Rästabel andmestruktuuris: Python Näide
Mis on räsimine?
Räsi on fikseeritud pikkusega väärtus ja see luuakse matemaatilise valemi abil. Räsiväärtusi kasutatakse andmete tihendamisel, krüptoloogias jne. Andmete indekseerimisel kasutatakse räsiväärtusi, kuna neil on fikseeritud pikkus sõltumata väärtustest, mida nende genereerimiseks kasutati. See muudab räsiväärtuste jaoks minimaalse ruumi võrreldes muude erineva pikkusega väärtustega.
Räsifunktsioon kasutab võtme räsideks teisendamiseks matemaatilist algoritmi. Kokkupõrge tekib siis, kui räsifunktsioon tekitab sama räsiväärtuse rohkem kui ühe võtme jaoks.
Mis on räsitabel?
A RÄSITABEL on andmestruktuur, mis salvestab väärtusi kasutades võtmete ja väärtuste paari. Igale väärtusele määratakse kordumatu võti, mis genereeritakse räsifunktsiooni abil.
Võtme nime kasutatakse sellega seotud väärtusele juurdepääsuks. See muudab väärtuste otsimise räsitabelis väga kiireks, sõltumata räsitabelis olevate üksuste arvust.
Räsifunktsioonid
Näiteks kui soovime salvestada töötajate kirjeid ja iga töötaja identifitseeritakse töötaja numbri abil kordumatult.
Võtmena saame kasutada töötaja numbrit ja väärtuseks määrata töötaja andmed.
Ülaltoodud lähenemisviis nõuab suurusjärgus täiendavat vaba ruumi (m * n2) kus muutuja m on suurus massiivi, ja muutuja n on töötaja numbri numbrite arv. See lähenemisviis toob kaasa salvestusruumi probleemi.
Räsifunktsioon lahendab ülaltoodud probleemi, hankides töötaja numbri ja kasutades seda räsitäisarvu väärtuse, fikseeritud numbrite genereerimiseks ja salvestusruumi optimeerimiseks. Räsifunktsiooni eesmärk on luua võti, mida kasutatakse väärtusele, mida soovime salvestada, viitamiseks. Funktsioon aktsepteerib salvestatava väärtuse ja kasutab seejärel võtme väärtuse arvutamiseks algoritmi.
Järgmine on näide lihtsast räsifunktsioonist
h(k) = k1 % m
SIIN,
- h(k) on räsifunktsioon, mis aktsepteerib parameetrit k. Parameeter k on väärtus, mille võtit tahame arvutada.
- k1 % m on meie räsifunktsiooni algoritm, kus k1 on väärtus, mida tahame salvestada, ja m on loendi suurus. Võtme arvutamiseks kasutame mooduloperaatorit.
Näide
Oletame, et meil on loend fikseeritud suurusega 3 ja järgmiste väärtustega
[1,2,3]
Saame kasutada ülaltoodud valemit, et arvutada positsioonid, mida iga väärtus peaks hõivama.
Järgmine pilt näitab saadaolevaid indekseid meie räsitabelis.
Step 1) Arvutage positsioon, mille hõivab esimene väärtus
h(1) = 1 % 3
= 1
Väärtus 1 hõivab ruum peal indeks 1
Step 2) Arvutage positsioon, mille hõivab teine väärtus
h(2) = 2 % 3
= 2
Väärtus 2 hõivab ruum peal indeks 2
Step 3) Arvutage positsioon, mille hõivab kolmas väärtus.
h(3) = 3 % 3
= 0
Väärtus 3 hõivab ruum peal indeks 0
Lõpptulemus
Meie täidetud räsitabel on nüüd järgmine.
Hea räsifunktsiooni omadused
Heal räsifunktsioonil peaksid olema järgmised omadused.
- Räsi genereerimise valem peaks kasutama algoritmi salvestatavate andmete väärtust.
- Räsifunktsioon peaks genereerima unikaalseid räsiväärtusi isegi sama koguse sisendandmete jaoks.
- Funktsioon peaks minimeerima kokkupõrgete arvu. Kokkupõrked tekivad siis, kui sama väärtus genereeritakse rohkem kui ühe väärtuse jaoks.
- Väärtused peavad olema järjepidevalt jaotatud kõigi võimalike räside vahel.
Kokkupõrge
Kokkupõrge toimub siis, kui algoritm genereerib sama räsi rohkem kui ühe väärtuse jaoks.
Vaatame näidet.
Oletame, et meil on järgmine väärtuste loend
[3,2,9,11,7]
Oletame, et räsitabeli suurus on 7 ja kasutame valemit (k1 % m) kus m on räsitabeli suurus.
Järgmine tabel näitab genereeritavaid räsiväärtusi.
Võti | Räsialgoritm (k1 % 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 salvestada igasse positsiooni rohkem kui ühe väärtuse.
Antud probleemi saab lahendada kas aheldamise või sondeerimisega. Järgmistes jaotistes käsitletakse üksikasjalikult aheldamist ja sondeerimist.
Aheldamine
Aheldamine on tehnika, mida kasutatakse kokkupõrkeprobleemi lahendamiseks, kasutades lingitud loendeid, millest igaühel on kordumatu indeks.
Järgmine pilt visualiseerib, kuidas aheldatud loend välja näeb
Nii 2 kui 9 hõivavad sama indeksi, 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 seni, kuni vaba ruumi on.
Sondeerimine
Teine kokkupõrke lahendamiseks kasutatav tehnika on sondeerimine. Kui kasutate sondeerimismeetodit, saame kokkupõrke korral lihtsalt edasi liikuda ja leida tühja pesa oma väärtuse salvestamiseks.
Järgmised sondeerimismeetodid:
Meetod | Kirjeldus |
---|---|
Lineaarne sondeerimine | Nagu nimigi ütleb, otsib see meetod tühje pilusid lineaarselt alustades kokkupõrke kohast ja liikudes edasi. Kui loendi lõppu jõutakse ja tühja pesa ei leitud. Uurimine algab loendi algusest. |
Ruutsondeerimine | See meetod kasutab järgmise vaba pesa leidmiseks ruutpolünoomiavaldisi. |
Double Räsimine | See tehnika kasutab järgmise vaba vaba pesa leidmiseks sekundaarset räsifunktsiooni algoritmi. |
Kasutades meie ülaltoodud näidet, näeks räsitabel pärast proovimise kasutamist järgmine:
Räsitabeli toimingud
Siin on Operaräsi tabelite toetatud toimingud:
- sisestamine - see Operasiooni kasutatakse elemendi lisamiseks räsitabelisse
- Otsimine - see Operation kasutatakse räsitabelis elementide otsimiseks klahvi abil
- kustutamine - see Operasiooni kasutatakse räsitabelist elementide kustutamiseks
Andmete sisestamise toiming
Sisestamistoimingut kasutatakse väärtuste salvestamiseks räsitabelisse. Kui räsitabelisse salvestatakse uus väärtus, määratakse sellele indeksi number. Indeksi number arvutatakse räsifunktsiooni abil. Räsifunktsioon lahendab kõik indeksinumbri arvutamisel ilmnevad kokkupõrked.
Otsige andmetoimingut
Otsingutoimingut kasutatakse väärtuste otsimiseks räsitabelist indeksinumbri abil. Otsingutoiming tagastab väärtuse, mis on lingitud otsingu indeksi numbriga. Näiteks kui salvestame väärtuse 6 indeksisse 2, tagastab otsinguoperatsioon indeksi numbriga 2 väärtuse 6.
Andmete kustutamise toiming
Kustutustoimingut kasutatakse väärtuse eemaldamiseks räsitabelist. Et kustutada OperaSeda tehakse indeksinumbri abil. Kui väärtus on kustutatud, vabastatakse indeksi number. Seda saab kasutada muude väärtuste salvestamiseks, kasutades sisestamistoimingut.
Räsitabeli rakendamine koos Python Näide
Vaatame lihtsat näidet, mis arvutab võtme räsiväärtuse
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)}')
Räsitabeli koodi seletus
SIIN,
- Määratleb funktsiooni hash_key, mis aktsepteerib parameetrid võti ja m.
- Kasutab räsiväärtuse määramiseks lihtsat mooduloperatsiooni
- Määratleb muutuja m, mis initsialiseeritakse väärtusega 7. See on meie räsitabeli suurus
- Arvutab ja prindib räsiväärtuse 3
- Arvutab ja prindib räsiväärtuse 2
- Arvutab ja prindib räsiväärtuse 9
- Arvutab ja prindib räsiväärtuse 11
- Arvutab ja prindib räsiväärtuse 7
Ülaltoodud koodi käivitamine annab järgmised tulemused.
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 Sõnastiku näide
Python kaasas on sisseehitatud andmetüüp nimega Dictionary. Räsitabeli näide on sõnastik. See salvestab väärtused, kasutades võtmete ja väärtuste paari. Räsiväärtused genereeritakse meie jaoks automaatselt ja kõik kokkupõrked lahendatakse meie jaoks taustal.
Järgmine näide näitab, kuidas saate kasutada sõnastiku andmetüüpi püüton 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)
SIIN,
- Määrab sõnastikus muutuva töötaja. Võtme nime kasutatakse väärtuse John Doe salvestamiseks, vanus salvestab 36 aastat ja positsioon salvestab väärtuse Business Manager.
- Otsib võtme nime väärtuse ja prindib selle terminalis
- Värskendab võtmepositsiooni väärtuse väärtuseks Tarkvarainsener
- Prindib klahvide nime ja asukoha väärtused
- Kustutab kõik väärtused, mis on salvestatud meie sõnastikus muutuja töötaja
- Trükib 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
Räsitabelite keskmine ajaline keerukus on parimal juhul O (1). Halvimal juhul on ajaline keerukus O(n). Halvim stsenaarium ilmneb siis, kui paljud väärtused genereerivad sama räsivõtme ja me peame lahendama kokkupõrke analüüsimise teel.
Reaalmaailma rakendused
Reaalses maailmas kasutatakse andmete salvestamiseks räsitabeleid
- Andmebaasid
- Assotsiatiivsed massiivid
- Komplektid
- Mälu vahemälu
Räsitabelite eelised
Siin on räsitabelite kasutamise plussid/eelised:
- Rästabelitel on andmete otsimisel, olemasolevate väärtuste sisestamisel ja kustutamisel suur jõudlus.
- Räsitabelite ajaline keerukus on konstantne sõltumata tabelis olevate üksuste arvust.
- Need toimivad väga hästi isegi suurte andmekogumitega töötades.
Räsitabelite miinused
Siin on räsitabelite kasutamise miinused:
- Nullväärtust ei saa võtmena kasutada.
- Kasutades võtmeid genereerides ei saa kokkupõrkeid vältida. räsifunktsioonid. Kokkupõrked tekivad siis, kui genereeritakse juba kasutusel olev võti.
- Kui räsifunktsioonil on palju kokkupõrkeid, võib see kaasa tuua jõudluse vähenemise.
kokkuvõte
- Rästabeleid kasutatakse andmete salvestamiseks võtmete ja väärtuste paari abil.
- Räsifunktsioon kasutab räsiväärtuse arvutamiseks matemaatilist algoritmi.
- Kokkupõrge tekib siis, kui sama räsiväärtus genereeritakse rohkem kui ühe väärtuse jaoks.
- Aheldamine lahendab kokkupõrke, luues lingitud loendeid.
- Uurimine lahendab kokkupõrke, leides räsitabelis tühjad pilud.
- Lineaarne sondeerimine otsib järgmist vaba pilu, et salvestada väärtus alates pesast, kus kokkupõrge toimus.
- Ruutmõõtmine kasutab kokkupõrke korral järgmise vaba pesa leidmiseks polünoomiavaldisi.
- Double räsimine kasutab kokkupõrke korral järgmise vaba pesa leidmiseks sekundaarset räsifunktsiooni algoritmi.
- Räsitabelitel on teiste andmestruktuuridega võrreldes parem jõudlus.
- Räsitabelite keskmine ajaline keerukus on O (1)
- Sõnastiku andmetüüp Pythonis on räsitabeli näide.
- Räsitabelid toetavad sisestamise, otsimise 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 tekkivate kokkupõrgete arvu.