Kas yra maiša?
Maiša yra vertė, kurios ilgis yra fiksuotas, ir ji generuojama naudojant matematinę formulę. Maišos reikšmės naudojamos duomenų glaudinimui, kriptologijai ir kt. Indeksuojant duomenis maišos reikšmės naudojamos todėl, kad jų ilgis yra fiksuotas, neatsižvelgiant į reikšmes, kurios buvo naudojamos joms generuoti. Tai leidžia maišos reikšmėms užimti minimalią erdvę, palyginti su kitomis skirtingo ilgio vertėmis.
Maišos funkcija naudoja matematinį algoritmą, kuris paverčia raktą maiša. Susidūrimas įvyksta, kai maišos funkcija sukuria tą pačią maišos reikšmę daugiau nei vienam klavišui.
Šioje algoritmo pamokoje sužinosite:
- Kas yra maiša?
- Kas yra maišos lentelė?
- Maišos funkcijos
- Geros maišos funkcijos savybės
- Susidūrimas
- Maišos stalo operacijos
- „Hash Table Python“ pavyzdys
- Maišos lentelės kodo paaiškinimas
- „Python“ žodyno pavyzdys
- Sudėtingumo analizė
- Tikrojo pasaulio programos
- Maišos lentelių privalumai
- Maišos lentelių trūkumai
Kas yra maišos lentelė?
Maišos lentelė yra duomenų struktūra, kuri saugo vertės naudojant klavišų ir vertybių pora. Kiekvienai reikšmei priskiriamas unikalus raktas, kuris sugeneruojamas naudojant maišos funkciją.
Rakto pavadinimas naudojamas norint pasiekti jo susietą vertę. Tai leidžia labai greitai ieškoti verčių maišos lentelėje, neatsižvelgiant į maišos lentelėje esančių elementų skaičių.
Maišos funkcijos
Pavyzdžiui, jei norime saugoti darbuotojų įrašus, o kiekvienas darbuotojas yra unikaliai identifikuojamas naudojant darbuotojo numerį.
Mes galime naudoti darbuotojo numerį kaip raktą ir priskirti darbuotojo duomenis kaip vertę.
Pirmiau nurodytam metodui reikės papildomos laisvos vietos (m * n 2 ), kur kintamasis m yra masyvo dydis, o kintamasis n yra darbuotojo skaičiaus skaitmenų skaičius. Šis metodas sukelia saugojimo vietos problemą.
Maišos funkcija išsprendžia pirmiau nurodytą problemą, gaudama darbuotojo numerį ir naudodama jį maišos sveikojo skaičiaus, fiksuotų skaitmenų ir optimizavimo saugojimo vietai generuoti. Maišos funkcijos tikslas yra sukurti raktą, kuris bus naudojamas norint nurodyti vertę, kurią norime išsaugoti. Funkcija priima išsaugotiną vertę, tada naudodama algoritmą apskaičiuoja rakto vertę.
Toliau pateikiamas paprastos maišos funkcijos pavyzdys
h(k) = k1 % m
ČIA
- h (k) yra maišos funkcija, kuri priima k parametrą. Parametras k yra reikšmė, kuriai norime apskaičiuoti raktą.
- k 1 % m yra mūsų maišos funkcijos algoritmas, kur k1 yra vertė, kurią norime išsaugoti, o m yra sąrašo dydis. Raktui apskaičiuoti naudojame modulio operatorių.
Pavyzdys
Tarkime, kad turime sąrašą su fiksuotu dydžiu 3 ir šiomis reikšmėmis
[1,2,3]
Mes galime naudoti aukščiau pateiktą formulę, kad apskaičiuotume pozicijas, kurias kiekviena vertė turėtų užimti.
Šiame paveikslėlyje rodomi turimi indeksai mūsų maišos lentelėje.
1 žingsnis)
Apskaičiuokite poziciją, kurią užims tokia pirmoji vertė
h (1) = 1% 3
= 1
1 reikšmė užims vietą 1 rodyklėje
2 žingsnis)
Apskaičiuokite poziciją, kurią užims antroji reikšmė
h (2) = 2% 3
= 2
2 reikšmė užims vietą 2 rodyklėje
3 žingsnis)
Apskaičiuokite poziciją, kurią užims trečioji vertė.
h (3) = 3% 3
= 0
3 reikšmė užims vietą indekso 0 vietoje
Galutinis rezultatas
Mūsų užpildyta maišos lentelė dabar bus tokia.
Geros maišos funkcijos savybės
Gera maišos funkcija turėtų turėti šias savybes.
- Maišos generavimo formulėje turėtų būti naudojama duomenų vertė, kuri bus saugoma algoritme.
- Maišos funkcija turėtų sugeneruoti unikalias maišos reikšmes net įvesties duomenims, kurių suma yra tokia pati.
- Funkcija turėtų sumažinti susidūrimų skaičių. Susidūrimai įvyksta, kai ta pati reikšmė generuojama daugiau nei vienai vertei.
- Vertės turi būti nuosekliai paskirstytos visuose įmanomuose maišuose.
Susidūrimas
Susidūrimas įvyksta, kai algoritmas sugeneruoja tą patį maišų daugiau nei vienai vertei.
Pažvelkime į pavyzdį.
Tarkime, kad turime šį verčių sąrašą
[3,2,9,11,7]
Tarkime, kad maišos lentelės dydis yra 7, ir naudosime formulę (k 1 % m), kur m yra maišos lentelės dydis.
Šioje lentelėje pateikiamos sugeneruojamos maišos vertės.
| Raktas | Maišos algoritmas (k 1 % m) | Maišos vertė |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Kaip matome iš pirmiau pateiktų rezultatų, 2 ir 9 reikšmės turi tą pačią maišos vertę ir kiekvienoje pozicijoje negalime išsaugoti daugiau nei vienos vertės.
Pateiktą problemą galima išspręsti naudojant grandinę arba zondavimą. Tolesniuose skyriuose išsamiai aptariamas grandinės ir zondavimas.
Grandinės
Grandinės yra technika, naudojama susidūrimo problemai išspręsti naudojant susietus sąrašus, kurių kiekvienas turi unikalius indeksus.
Šiame paveikslėlyje vaizduojama, kaip atrodo grandinės sąrašas
Tiek 2, tiek 9 užima tą patį indeksą, tačiau jie saugomi kaip susieti sąrašai. Kiekvienas sąrašas turi unikalų identifikatorių.
Grandinių sąrašų privalumai
Šie yra grandinių sąrašų pranašumai:
- Grandinių sąrašai veikia geriau įterpdami duomenis, nes įterpimo tvarka yra O (1).
- Nereikia keisti maišos lentelės, kurioje naudojamas grandininis sąrašas, dydžio.
- Jis gali lengvai pritaikyti daugybę verčių, jei yra laisvos vietos.
Zondavimas
Kita technika, naudojama susidūrimui išspręsti, yra zondavimas. Naudojant zondavimo metodą, jei įvyksta susidūrimas, mes galime tiesiog pereiti ir rasti tuščią lizdą savo vertei išsaugoti.
Šie yra zondavimo metodai:
| Metodas | apibūdinimas |
| Tiesinis zondavimas | Kaip rodo pavadinimas, šiuo metodu tuščių vietų ieškoma tiesiškai, pradedant nuo susidūrimo vietos ir judant į priekį. Pasiekus sąrašo pabaigą ir nerandant tuščio lizdo. Tyrimas prasideda sąrašo pradžioje. |
| Kvadratinis zondavimas | Šis metodas naudoja kvadratines daugianario išraiškas, kad surastų kitą laisvą lizdą. |
| Dvigubas maišos | Ši technika naudoja antrinį maišos funkcijos algoritmą, kad surastų kitą laisvą laisvą lizdą. |
Naudojant aukščiau pateiktą pavyzdį, maišos lentelė po zondavimo pasirodys taip:
Maišos stalo operacijos
Čia yra „Hash“ lentelių palaikomos operacijos:
- Įterpimas - ši operacija naudojama elementui pridėti prie maišos lentelės
- Paieška - ši operacija naudojama ieškant elementų maišos lentelėje naudojant raktą
- Ištrynimas - Ši operacija naudojama ištrinti elementus iš maišos lentelė
Įterpiama duomenų operacija
Įterpimo operacija naudojama vertėms įrašyti maišos lentelėje. Kai maišos lentelėje įrašoma nauja reikšmė, jai priskiriamas indekso numeris. Indekso skaičius apskaičiuojamas naudojant maišos funkciją. Maišos funkcija pašalina visus susidūrimus, įvykusius skaičiuojant indekso numerį.
Ieškokite duomenų operacijos
Paieškos operacija naudojama vertėms ieškoti maišos lentelėje naudojant indekso numerį. Paieškos operacija grąžina vertę, susietą su paieškos indekso numeriu. Pvz., Jei reikšmę 6 saugome indekse 2, paieškos operacija su indekso numeriu 2 grąžins vertę 6.
Ištrinti duomenų operaciją
Ištrinimo operacija naudojama norint pašalinti vertę iš maišos lentelės. Operacija ištrinama naudojant indekso numerį. Ištrynus vertę, indekso numeris yra laisvas. Jis gali būti naudojamas kitoms reikšmėms saugoti naudojant įterpimo operaciją.
Maišos lentelės diegimas naudojant „Python“ pavyzdį
Pažvelkime į paprastą pavyzdį, kuris apskaičiuoja rakto maišos vertę
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)}')
Maišos lentelės kodo paaiškinimas
ČIA
- Apibrėžia funkciją hash_key, kuri priima parametrų raktą ir m.
- Maišo vertei nustatyti naudojama paprasta modulio operacija
- Apibrėžia kintamąjį m, kuris inicijuojamas iki vertės 7. Tai yra mūsų maišos lentelės dydis
- Apskaičiuoja ir atspausdina maišos reikšmę 3
- Apskaičiuoja ir atspausdina maišos reikšmę 2
- Apskaičiuoja ir atspausdina maišos reikšmę 9
- Apskaičiuoja ir atspausdina maišos reikšmę 11
- Apskaičiuoja ir atspausdina maišos reikšmę 7
Vykdant aukščiau nurodytą kodą gaunami šie rezultatai.
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
„Python“ žodyno pavyzdys
„Python“ yra su įmontuotu duomenų tipu, vadinamu žodynu. Žodynas yra maišos lentelės pavyzdys. Jis saugo vertes naudodamas raktų ir verčių porą. Maišos vertės automatiškai sugeneruojamos mums, o bet kokie susidūrimai mums išsprendžiami fone.
Šiame pavyzdyje parodyta, kaip galite naudoti žodyno duomenų tipą „Python 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)
ČIA
- Apibrėžia žodyno kintamąjį darbuotoją. Raktinis pavadinimas naudojamas Johnui Doe'ui išsaugoti, 36 metų amžius, o pozicijos - Business Manager vertė.
- Gauna rakto pavadinimo vertę ir atspausdina ją terminale
- Atnaujina pagrindinės pozicijos vertę į „Software Engineer“ vertę
- Spausdina raktų pavadinimo ir pozicijos reikšmes
- Ištrina visas reikšmes, saugomas mūsų žodyne kintamojo darbuotojo
- Spausdina darbuotojo vertę
Paleidus pirmiau nurodytą kodą gaunami šie rezultatai.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Sudėtingumo analizė
Geriausiu atveju Hash lentelių vidutinis laiko sudėtingumas yra O (1). Blogiausiu atveju laiko sudėtingumas yra O (n). Blogiausias scenarijus įvyksta, kai daugybė reikšmių sugeneruoja tą patį maišos raktą, ir mes turime išspręsti susidūrimą zonduodami.
Tikrojo pasaulio programos
Realiame pasaulyje maišos lentelės naudojamos duomenims saugoti
- Duomenų bazės
- Asociatyvūs masyvai
- Rinkiniai
- Atminties talpykla
Maišos lentelių privalumai
Čia yra maišos lentelių naudojimo privalumai / privalumai:
- „Hash“ lentelės yra labai našios ieškant duomenų, įterpiant ir ištrinant esamas reikšmes.
- Maišos lentelių sudėtingumas yra pastovus, neatsižvelgiant į elementų skaičių lentelėje.
- Jie labai gerai veikia net dirbdami su dideliais duomenų rinkiniais.
Maišos lentelių trūkumai
Čia yra maišos lentelių naudojimo trūkumai:
- Negalite naudoti nulinės vertės kaip rakto.
- Generuojant raktus naudojant negalima išvengti susidūrimų. maišos funkcijos. Susidūrimai įvyksta, kai sugeneruojamas jau naudojamas raktas.
- Jei maišos funkcija turi daug susidūrimų, tai gali sumažinti veikimą.
Santrauka:
- Maišos lentelės naudojamos duomenims saugoti naudojant porą raktų ir reikšmių.
- Maišos funkcija naudoja matematinį algoritmą maišos vertei apskaičiuoti.
- Susidūrimas įvyksta, kai ta pati maišos vertė sugeneruojama daugiau nei vienai vertei.
- Grandinės išsprendžia susidūrimą kuriant susietus sąrašus.
- Zondavimas išsprendžia susidūrimą, maišo lentelėje radęs tuščių vietų.
- Tiesinis zondavimas ieško kito laisvo lizdo, kad išsaugotų vertę, pradedant nuo lizdo, kuriame įvyko susidūrimas.
- Kvadratinis zondavimas naudoja daugianario išraiškas, kad surastų kitą laisvą lizdą susidūrus.
- Dviguba maiša naudoja antrinį maišos funkcijos algoritmą, kad surastų kitą laisvą lizdą įvykus susidūrimui.
- „Hash“ lentelės veikia geriau, palyginti su kitomis duomenų struktūromis.
- Vidutinis maišos lentelių sudėtingumas yra O (1)
- Žodyno duomenų tipas python yra maišos lentelės pavyzdys.
- Maišos lentelės palaiko įterpimo, paieškos ir ištrynimo operacijas.
- Nulinės vertės negalima naudoti kaip indekso vertės.
- Negalima išvengti susidūrimų naudojant maišos funkcijas. Gera maišos funkcija sumažina susidūrimų skaičių, kad pagerėtų našumas.