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.

Räsifunktsioonid

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.

Räsifunktsioonid

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

Aheldamine

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:

Sondeerimine

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

Räsitabeli koodi seletus

SIIN,

  1. Määratleb funktsiooni hash_key, mis aktsepteerib parameetrid võti ja m.
  2. Kasutab räsiväärtuse määramiseks lihtsat mooduloperatsiooni
  3. Määratleb muutuja m, mis initsialiseeritakse väärtusega 7. See on meie räsitabeli suurus
  4. Arvutab ja prindib räsiväärtuse 3
  5. Arvutab ja prindib räsiväärtuse 2
  6. Arvutab ja prindib räsiväärtuse 9
  7. Arvutab ja prindib räsiväärtuse 11
  8. 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)

Python Sõnastiku näide

SIIN,

  1. 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.
  2. Otsib võtme nime väärtuse ja prindib selle terminalis
  3. Värskendab võtmepositsiooni väärtuse väärtuseks Tarkvarainsener
  4. Prindib klahvide nime ja asukoha väärtused
  5. Kustutab kõik väärtused, mis on salvestatud meie sõnastikus muutuja töötaja
  6. 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.