Datu struktūras – Hash funkcijas tabulas, jeb atmiņas tabulas

Iepriekšējos rakstos jau apskatījām un iepazināmies ar dažādām datu struktūrām, šeit būs vēl viena, kuru izpētīt. Jūs esat atklājis, ka nav ideāls informācijas glabāšanas veids. Tā vietā ir daudz dažādu pieeju, un katra no tām ir piemērots risinājums atkarībā no problēmas.

Šajā rakstā jūs uzzināsiet par to, kas ir jauktā tabula (Hash table), tās struktūru un raksturīgajām iezīmēm un kā tā darbojas. Jūs arī izpētīsiet dažas jauktās tabulas izmantošanas priekšrocības un atklāsiet, ko nozīmē sadursmes jaukšanā. Jaucējtabulā ir vairāki sloti vai segmenti, lai glabātu atslēgu vērtību pārus. Lai noteiktu pareizo segmentu, kurā ievietot datus, ir nepieciešama jaukšanas funkcija (Hashing function). Jaukšanas funkcija ir jebkurš algoritms vai formula, kas tiek lietota atslēgai (key), lai ģenerētu unikālu numuru. Katram saglabājamajam datu vienumam ir jābūt atslēgai un vērtībai (value). Atslēga tiek paņemta un tai tiek piemērota jaukšanas funkcija, lai tā tiktu samazināta līdz noteikta lieluma vērtībai.

Var izmantot dažādas jaukšanas funkcijas. Jūs, iespējams, esat pazīstams ar tiem saistībā ar datu saspiešanu (piemēram Zip, vai Rar). Ja vēlaties nosūtīt informāciju internetā, vispirms varat saspiest tās lielumu līdz pārvaldāmam baitu skaitam, nosūtīt to internetā un pēc tam izvērst to otrā pusē. Šis ir piemērs tam, kā darbojas jaukšana. Tas samazina atslēgu līdz mazam, pārvaldāmam izmēram, kas pēc tam darbojas kā indeksa indikators. Kāda informācija tiek izmantota indeksa ģenerēšanai, ir atkarīga no lietojumprogrammas. Tie var būt paši dati, ja tie ir pietiekami mazi, vai arī tie var būt darbinieka ID numura pēdējie četri cipari, vai arī tā var būt vārdnīcas atslēga.

Lielākajai daļai programmēšanas valodu ir iebūvētas jaukšanas funkcijas, piemēram,

• MD5(Message Digest Method 5),
• SHA(Secure Hash Algorithms) vai
• CRC32,(Cyclic redundancy check)

tāpēc jaukšanas funkcijas ieviešana ir vienkāršs darbs. Apspriežot Big-O notation apzīmējumu, tika ieviesta ideja, ka ātrums un telpa bieži ir pretrunā viens ar otru. Tas nozīmē, ka varat samazināt laiku, kas nepieciešams vienuma izgūšanai, taču, to darot, jūs pievienojat savai lietojumprogrammai papildu datu izmaksas. Jaukšanas tabulās prioritāte ir ātrums, nevis vieta, un tās var izgūt vienumu vienā reizē.

Atsauciet atmiņā tēmu par masīviem (Arrays). Ja vēlaties pārbaudīt, vai vērtība pastāv, ir jāveic meklēšana, kas pārbauda katru saraksta elementu un salīdzina ar mērķa vērtību. Sliktākajā gadījumā tas prasīs O(n) laika, vai, citiem vārdiem sakot, ja elements atradās masīva beigās, tam ir jāveic n pārbaudes. Hash tabulas piedāvā alternatīvu pieeju datu glabāšanai un meklēšanai.

Tas tiek darīts, izmantojot indeksu. Lai to panāktu, jums ir jāievieš algoritms, kas ņem atslēgu un kartē to ar vērtību, kas tiek saglabāta indeksā. Pēc tam, kad tiek parādīta jauna atslēga, algoritmam tikai jāpalaiž tā pati funkcija un jānosaka, kur indeksā atrodas vērtība.

Līdzīgi kā satura rādītājs grāmatā, tas ievērojami paātrinās dažu datu atrašanās vietas noteikšanai nepieciešamo laiku.

Jūs, visticamāk, atradīsit jaucējtabulas, ko izmanto

• kešatmiņās,
• vārdnīcās,
• datu bāzes indeksos
• un kopās.

Apsveriet scenāriju, kurā jums ir 10 taustiņu masīvs, kas ir skaitļi no 0 līdz 9. Jūs vēlaties izmantot jaukšanas funkciju, lai izlemtu, kur atmiņā saglabāt šos skaitļus. Jūs izvēlaties vienkāršotu pieeju, skaitļiem piemērojot moduli 20. Katrai atslēgai no 0 līdz 9 tiek lietota jaukšanas funkcija. Sāciet ar 0 mod 20 ir vienāds ar 0, 1 mod 20 ir vienāds ar 1, 2 mod 20 ir vienāds ar 2, 3 mod 20 ir vienāds ar 3 un tā tālāk kā rādīts attēlā.

Tādā veidā jūs ģenerētu deviņas unikālas vērtības, kuras tiek izmantotas, lai attēlotu atmiņā, kur tiek ievietoti ar šīm atslēgām saistītie dati.

Šis piemērs ir vienkāršots, taču ilustrē HashMaps izveides mehānismu. Problēma rodas, ja saglabājamo atslēgu skaits pārsniedz 20. Atcerieties, ka 1 mod 20 ir vienāds ar 1, bet 20 mod 21 arī vienāds ar 1.

Pāriesim pie sadursmēm hash tabulās.

Kas ir sadursmes hash tabulās?

Jaukšanas funkcija izmantos gudru algoritmu, kas samazinās atslēgas izmēru līdz pārvaldāmam izmēram. Dažas pieejas ir sarežģītākas nekā citas. Kas notiek, ja divu jaukšanas rezultātu rezultāts ir vienāds? Lai paplašinātu šo ideju, ir vērts padomāt par fon Mises dzimšanas dienas paradoksu.

• “Dzimšanas dienas paradokss” ir matemātisks paradokss, kas apgalvo, ka, ja ir 23 cilvēki vienā telpā, tad varbūtība tam, ka vismaz diviem no viņiem ir viena un tā pati dzimšanas diena, ir lielāka par 50%¹.Ludvigs fon Mises bija slavens ekonomists un filozofs un nav saistīts ar šo paradoksu².

Varbūtības dēļ dažkārt notikumam ir lielāka iespējamība, ka tas notiks, nekā mēs ticam. Šajā gadījumā, ja aptaujājat nejaušu grupu, kurā ir tikai 23 cilvēki, patiesībā pastāv aptuveni 50–50 iespēja, ka diviem no viņiem būs vienāda dzimšanas diena. To sauc par dzimšanas dienas paradoksu. Pieņemsim, ka uzņēmumā strādā 24 darbinieki un ir izmantota gudra jaukšanas funkcija, kas ņem viņu dzimšanas dienas datumu un mēnesi un izmanto to kā indeksu.

Tā kā ir tikai 24 darbinieki un jaukšanas tabula ar 365 indeksa laika nišām, kurā ir atsauce uz tiem, jūs domājat, ka ir maz ticams, ka divi darbinieki kopīgi svinēs dzimšanas dienu. Faktiski ir pierādīts, ka tā rašanās iespējamība ir vairāk nekā 50%.

Nākamreiz, kad būsiet ballītē, noteikti pārbaudiet, vai diviem dalībniekiem ir vienāda dzimšanas diena, lai par to pārliecinātos pats. Tas ilustrē to, ka, ja atslēgai tiek lietota jaukšanas funkcija, tiks ģenerēti dublikāti un ka tai ir jāpielāgojas. Problēmai ir daži risinājumi. Viens no risinājumiem ir palielināt tabulu katru reizi, kad notiek sadursme, un pēc tam palielināt jaukšanas pieejas sarežģītību, pārdalot vērtības uz jaunām adresēm. Tādā veidā tabula organiski pieaugs, lai atbilstu nepieciešamo datu lielumam. Vēl viens ir izveidot saistītu sarakstu (Linked list) sadursmes vietā un vienkārši saglabāt papildu vērtības. Sadursmes gadījumā tā vietā, lai saglabātu vērtību, jūs saglabātu saistīto vērtību sarakstu.

Šajā rakstā jūs atklājāt, kas ir hash tabulas, struktūra un funkcijas un kā tās darbojas. Jūs arī uzzinājāt, ka jaukšana ir ļoti gudra pieeja, lai ģenerētu vienreizēju meklējumu O(1), izmantojot jaukšanas funkciju un indeksu. Jūs esat izpētījis sadursmes un to, kā tās var izmantot, lai informētu par galda izmēru, un jūs pat uzzinājāt, ka, ja esat ballītē ar vairāk nekā 24 viesiem, visticamāk, ka vismaz divi dalīsies tā pati dzimšanas diena.