Kas ir hašings?
Hash ir vērtība, kurai ir noteikts garums, un tā tiek ģenerēta, izmantojot matemātisko formulu. Hash vērtības tiek izmantotas datu saspiešanā, kriptoloģijā utt. Datu indeksēšanā tiek izmantotas hash vērtības, jo tām ir noteikts garuma lielums neatkarīgi no vērtībām, kas tika izmantotas to ģenerēšanai. Tas padara jaukšanas vērtības aizņemt minimālu vietu salīdzinājumā ar citām dažāda garuma vērtībām.
Hash funkcija izmanto matemātisko algoritmu, lai atslēgu pārveidotu par hash. Sadursme notiek, ja jaucējfunkcija rada vienu un to pašu hash vērtību vairāk nekā vienam taustiņam.
Šajā algoritma apmācībā jūs uzzināsiet:
- Kas ir hašings?
- Kas ir Hash tabula?
- Hash funkcijas
- Labas hash funkcijas īpašības
- Sadursme
- Hash tabulas darbības
- Hash Table Python piemērs
- Hash tabulas koda skaidrojums
- Python vārdnīcas piemērs
- Sarežģītības analīze
- Reālās pasaules lietojumprogrammas
- Hash tabulu priekšrocības
- Hash tabulu trūkumi
Kas ir Hash tabula?
Hash tabulu ir datu struktūra, kas glabā vērtības, izmantojot pāris atslēgas un vērtības. Katrai vērtībai tiek piešķirta unikāla atslēga, kas tiek ģenerēta, izmantojot jaucējfunkciju.
Atslēgas nosaukums tiek izmantots, lai piekļūtu ar to saistītajai vērtībai. Tas padara vērtību meklēšanu jaukšanas tabulā ļoti ātru, neatkarīgi no jaucēj tabulas vienumu skaita.
Hash funkcijas
Piemēram, ja mēs vēlamies saglabāt darbinieku ierakstus, un katrs darbinieks tiek unikāli identificēts, izmantojot darbinieka numuru.
Mēs varam izmantot darbinieka numuru kā atslēgu un piešķirt darbinieka datus kā vērtību.
Iepriekš aprakstītajai pieejai būs nepieciešama papildu brīva vieta pakāpē (m * n 2 ), kur mainīgais m ir masīva lielums, un mainīgais n ir darbinieka skaitļa ciparu skaits. Šī pieeja ievieš uzglabāšanas vietas problēmu.
Jaucējfunkcija atrisina iepriekš minēto problēmu, iegūstot darbinieka numuru un izmantojot to, lai ģenerētu hash vesela skaitļa vērtību, fiksētus ciparus un optimizētu krātuves vietu. Jaucējfunkcijas mērķis ir izveidot atslēgu, kas tiks izmantota, lai norādītu vērtību, kuru mēs vēlamies saglabāt. Funkcija pieņem saglabājamo vērtību, pēc tam izmanto algoritmu, lai aprēķinātu atslēgas vērtību.
Šis ir vienkāršas hash funkcijas piemērs
h(k) = k1 % m
ŠEIT,
- h (k) ir hash funkcija, kas pieņem parametru k. Parametrs k ir vērtība, kurai mēs vēlamies aprēķināt atslēgu.
- k 1 % m ir mūsu hash funkcijas algoritms, kur k1 ir vērtība, kuru mēs vēlamies saglabāt, un m ir saraksta lielums. Mēs izmantojam moduļa operatoru, lai aprēķinātu atslēgu.
Piemērs
Pieņemsim, ka mums ir saraksts ar fiksētu izmēru 3 un šādām vērtībām
[1,2,3]
Mēs varam izmantot iepriekš minēto formulu, lai aprēķinātu pozīcijas, kuras katrai vērtībai vajadzētu aizņemt.
Šis attēls parāda mūsu hash tabulā pieejamos rādītājus.
1. darbība)
Aprēķiniet pozīciju, kuru aizņems pirmā vērtība
h (1) = 1% 3
= 1
Vērtība 1 aizņem vietu indeksā 1
2. solis)
Aprēķiniet pozīciju, kuru aizņems otrā vērtība
h (2) = 2% 3
= 2
Vērtība 2 aizņem vietu indeksā 2
3. solis)
Aprēķiniet pozīciju, kuru aizņems trešā vērtība.
h (3) = 3% 3
= 0
Vērtība 3 aizņem vietu indeksā 0
Galīgais rezultāts
Mūsu aizpildītā jaukšanas tabula tagad būs šāda.
Labas hash funkcijas īpašības
Labai hash funkcijai vajadzētu būt šādām īpašībām.
- Maiņas ģenerēšanas formulai jāizmanto algoritmā saglabājamā datu vērtība.
- Hash funkcijai vajadzētu ģenerēt unikālas hash vērtības pat ievades datiem, kuriem ir vienāds daudzums.
- Funkcijai vajadzētu pēc iespējas samazināt sadursmju skaitu. Sadursmes rodas, ja viena un tā pati vērtība tiek ģenerēta vairākām vērtībām.
- Vērtībām jābūt konsekventi sadalītām visā iespējamajā jaukšanā.
Sadursme
Sadursme notiek, kad algoritms rada vienu un to pašu jaukumu vairākām vērtībām.
Apskatīsim piemēru.
Pieņemsim, ka mums ir šāds vērtību saraksts
[3,2,9,11,7]
Pieņemsim, ka hash tabulas izmērs ir 7, un mēs izmantosim formulu (k 1 % m), kur m ir hash tabulas lielums.
Šajā tabulā ir norādītas ģenerētās jaukšanas vērtības.
| Atslēga | Hash algoritms (k 1 % m) | Hash vērtība |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Kā redzams no iepriekš minētajiem rezultātiem, 2. un 9. vērtībai ir vienāda jaukšanas vērtība, un katrā pozīcijā mēs nevaram saglabāt vairāk nekā vienu vērtību.
Doto problēmu var atrisināt, izmantojot ķēdi vai zondēšanu. Turpmākajās sadaļās detalizēti aplūkota ķēdēšana un zondēšana.
Ķēdes
Ķēdēšana ir paņēmiens, ko izmanto sadursmes problēmas risināšanai, izmantojot saistītus sarakstus, kuriem katram ir unikāli indeksi.
Šis attēls vizualizē, kā izskatās ķēdes saraksts
Gan 2, gan 9 aizņem to pašu indeksu, taču tie tiek glabāti kā saistīti saraksti. Katram sarakstam ir unikāls identifikators.
Ķēdes sarakstu priekšrocības
Ķēdes sarakstu priekšrocības ir šādas:
- Ķēdes sarakstiem ir labāka veiktspēja, ievietojot datus, jo ievietošanas secība ir O (1).
- Nav nepieciešams mainīt jaukšanas tabulas izmēru, kurā tiek izmantots ķēdes saraksts.
- Tas var viegli uzņemt lielu skaitu vērtību, ja vien ir pieejama brīva vieta.
Zondēšana
Cita tehnika, ko izmanto sadursmes novēršanai, ir zondēšana. Izmantojot zondēšanas metodi, ja notiek sadursme, mēs varam vienkārši pāriet uz priekšu un atrast tukšu slotu, lai saglabātu mūsu vērtību.
Zondēšanas metodes ir šādas:
| Metode | Apraksts |
| Lineārā zondēšana | Gluži kā norāda nosaukums, šī metode tukšās vietas meklē lineāri, sākot no sadursmes vietas un virzoties uz priekšu. Ja saraksta beigas ir sasniegtas un tukša vieta nav atrasta. Zondēšana sākas saraksta sākumā. |
| Kvadrātiska zondēšana | Šī metode izmanto kvadrātveida polinomu izteiksmes, lai atrastu nākamo pieejamo brīvo slotu. |
| Dubultā jaukšana | Šis paņēmiens izmanto sekundāro hash funkciju algoritmu, lai atrastu nākamo brīvo pieejamo slotu. |
Izmantojot mūsu iepriekš minēto piemēru, jaukšanas tabula pēc zondēšanas izmantošanas parādīsies šādi:
Hash tabulas darbības
Šeit ir operācijas, kuras atbalsta Hash tabulas:
- Ievietošana - šo operāciju izmanto, lai pievienotu elementu jaukšanas tabulai
- Meklēšana - šo darbību izmanto, lai ar taustiņu meklētu elementus jaukšanas tabulā
- Dzēšana - šo darbību izmanto, lai dzēstu elementus no jaukšanas tabulas
Datu ievietošanas darbība
Ievietošanas darbību izmanto, lai vērtības saglabātu jaukšanas tabulā. Ja jaukšanas tabulā tiek saglabāta jauna vērtība, tai tiek piešķirts indeksa numurs. Indeksa numuru aprēķina, izmantojot hash funkciju. Hash funkcija novērš visas sadursmes, kas rodas, aprēķinot indeksa numuru.
Meklēt datu darbību
Meklēšanas operācija tiek izmantota, lai meklētu vērtības jaukšanas tabulā, izmantojot indeksa numuru. Meklēšanas darbība atgriež vērtību, kas ir saistīta ar meklēšanas indeksa numuru. Piemēram, ja mēs vērtību 6 glabājam indeksā 2, meklēšanas darbība ar indeksa numuru 2 atgriezīs vērtību 6.
Dzēst datu darbību
Dzēšanas darbība tiek izmantota, lai noņemtu vērtību no jaukšanas tabulas. Lai izdzēstu, darbība tiek veikta, izmantojot indeksa numuru. Kad vērtība ir izdzēsta, indeksa numurs tiek atbrīvots. To var izmantot, lai saglabātu citas vērtības, izmantojot ievietošanas darbību.
Hash tabulas ieviešana ar Python piemēru
Apskatīsim vienkāršu piemēru, kas aprēķina atslēgas jaukšanas vērtību
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)}')
Hash tabulas koda skaidrojums
ŠEIT,
- Definē funkciju hash_key, kas pieņem parametru atslēgu un m.
- Izmanto vienkāršu moduļa darbību, lai noteiktu jaukšanas vērtību
- Definē mainīgo m, kas tiek inicializēts līdz vērtībai 7. Tas ir mūsu jaukšanas tabulas lielums
- Aprēķina un izdrukā jaukšanas vērtību 3
- Aprēķina un izdrukā jaukšanas vērtību 2
- Aprēķina un izdrukā jaukšanas vērtību 9
- Aprēķina un izdrukā jaukšanas vērtību 11
- Aprēķina un izdrukā jaukšanas vērtību 7
Izpildot iepriekš minēto kodu, tiek iegūti šādi rezultāti.
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 vārdnīcas piemērs
Python nāk ar iebūvētu datu tipu, ko sauc par vārdnīcu. Vārdnīca ir hash tabulas piemērs. Tas saglabā vērtības, izmantojot atslēgu un vērtību pāri. Jaukšanas vērtības mums tiek automātiski ģenerētas, un visas sadursmes mums tiek novērstas fonā.
Šajā piemērā parādīts, kā var izmantot vārdnīcas datu tipu 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)
ŠEIT,
- Definē vārdnīcas mainīgo darbinieku. Atslēgas nosaukums tiek izmantots, lai saglabātu vērtību Džons Doe, vecums ir 36 gadi un pozīcija - vērtība Biznesa menedžeris.
- Izgūst atslēgas nosaukuma vērtību un izdrukā to terminālā
- Atjaunina atslēgas pozīcijas vērtību uz programmatūras inženieri
- Izdrukā atslēgu nosaukuma un pozīcijas vērtības
- Dzēš visas vērtības, kas tiek glabātas mūsu vārdnīcas mainīgajā darbiniekā
- Izdrukā darbinieka vērtību
Palaižot iepriekš minēto kodu, tiek iegūti šādi rezultāti.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Sarežģītības analīze
Hash tabulām vidējā laika sarežģītība ir O (1) labākajā gadījumā. Sliktākā laika sarežģītība ir O (n). Sliktākais gadījums rodas, ja daudzas vērtības ģenerē vienu un to pašu jaukšanas atslēgu, un mums ir jāatrisina sadursme ar zondēšanu.
Reālās pasaules lietojumprogrammas
Reālajā pasaulē hash tabulas tiek izmantotas, lai saglabātu datus par
- Datu bāzes
- Asociatīvie bloki
- Komplekti
- Atmiņas kešatmiņa
Hash tabulu priekšrocības
Šeit ir hash tabulu izmantošanas priekšrocības / priekšrocības:
- Hash tabulām ir augsta veiktspēja, meklējot datus, ievietojot un dzēšot esošās vērtības.
- Maiņas tabulu laika sarežģītība ir nemainīga neatkarīgi no tabulas vienumu skaita.
- Tie darbojas ļoti labi, pat strādājot ar lielām datu kopām.
Hash tabulu trūkumi
Šeit ir hash tabulu izmantošanas mīnusi:
- Jūs nevarat izmantot nulles vērtību kā atslēgu.
- Nevar izvairīties no sadursmēm, ģenerējot atslēgas, izmantojot. hash funkcijas. Sadursmes rodas, kad tiek ģenerēta jau lietota atslēga.
- Ja jaukšanas funkcijai ir daudz sadursmju, tas var izraisīt veiktspējas samazināšanos.
Kopsavilkums:
- Hash tabulas tiek izmantotas datu glabāšanai, izmantojot atslēgu un vērtību pāri.
- Hash funkcija izmanto matemātisko algoritmu, lai aprēķinātu hash vērtību.
- Sadursme notiek, ja viena un tā pati jaukšanas vērtība tiek ģenerēta vairāk nekā vienai vērtībai.
- Ķēdes atrisina sadursmi, izveidojot saistītus sarakstus.
- Zondēšana atrisina sadursmi, hash tabulā atrodot tukšas vietas.
- Lineārā zondēšana meklē nākamo brīvo slotu, lai saglabātu vērtību, sākot no slota, kurā notika sadursme.
- Kvadrātiskā zondēšana izmanto polinomu izteiksmes, lai atrastu nākamo brīvo vietu, kad notiek sadursme.
- Dubultā jaukšana izmanto sekundāro jaukšanas funkcijas algoritmu, lai atrastu nākamo brīvo vietu, kad notiek sadursme.
- Hash tabulām ir labāka veiktspēja, salīdzinot ar citām datu struktūrām.
- Maizes tabulu vidējā laika sarežģītība ir O (1)
- Vārdnīcas datu tips python ir hash tabulas piemērs.
- Hash tabulas atbalsta ievietošanas, meklēšanas un dzēšanas darbības.
- Nulli vērtību nevar izmantot kā indeksa vērtību.
- Nevar izvairīties no sadursmēm hash funkcijās. Laba jaukšanas funkcija samazina sadursmju skaitu, kas rodas, lai uzlabotu veiktspēju.