Jaukšana attiecas uz fiksēta izmēra izvades ģenerēšanas procesu no mainīga lieluma ievades, izmantojot matemātiskās formulas, kas pazīstamas kā jaucējfunkcijas. Šis paņēmiens nosaka indeksu vai vietu vienuma glabāšanai datu struktūrā.
Nepieciešamība pēc Hash datu struktūras
Datu apjoms internetā katru dienu pieaug eksponenciāli, tāpēc ir grūti to visu efektīvi uzglabāt. Ikdienas programmēšanā šis datu apjoms var nebūt tik liels, bet tomēr tas ir jāsaglabā, jāpiekļūst un jāapstrādā viegli un efektīvi. Ļoti izplatīta datu struktūra, kas tiek izmantota šādam mērķim, ir masīva datu struktūra.
Tagad rodas jautājums, ja masīvs jau bija, kam bija vajadzīga jauna datu struktūra! Atbilde uz to ir vārda efektivitāte. Lai gan uzglabāšana Array aizņem O(1) laika, meklēšana tajā aizņem vismaz O(log n) laiks. Šķiet, ka šis laiks ir mazs, taču lielai datu kopai tas var radīt daudz problēmu, un tas savukārt padara masīva datu struktūru neefektīvu.
Tāpēc tagad mēs meklējam datu struktūru, kas var uzglabāt datus un meklēt tajos nemainīgā laikā, t.i., O(1) laiks. Tādā veidā ienāca Hashing datu struktūra. Ieviešot Hash datu struktūru, tagad ir iespējams ērti uzglabāt datus nemainīgā laikā un arī izgūt tos nemainīgā laikā.
Jaukšanas sastāvdaļas
Jaukšanai galvenokārt ir trīs komponenti:
- Taustiņš: A Atslēga var būt jebkas virkne vai vesels skaitlis, kas tiek ievadīts kā ievade jaucējfunkcijā — paņēmienā, kas nosaka indeksu vai vietu vienuma glabāšanai datu struktūrā.
- Jaucējfunkcija: The jaucējfunkcija saņem ievades atslēgu un atgriež elementa indeksu masīvā, ko sauc par hash tabulu. Indekss ir pazīstams kā hash indekss .
- Hash tabula: Hash tabula ir datu struktūra, kas kartē atslēgas vērtībām, izmantojot īpašu funkciju, ko sauc par jaucējfunkciju. Hash saglabā datus asociatīvā veidā masīvā, kur katrai datu vērtībai ir savs unikāls indekss.
Jaukšanas sastāvdaļas
Kas ir sadursme?
Jaukšanas procesā lielai atslēgai tiek ģenerēts neliels skaitlis, tāpēc pastāv iespēja, ka divas atslēgas var radīt vienādu vērtību. Situācija, kad tikko ievietotā atslēga tiek kartēta uz jau aizņemtu, un tā ir jāapstrādā, izmantojot kādu sadursmju apstrādes tehnoloģiju.
Sadursme Hašingā
Jaukšanas priekšrocības datu struktūrās
- Atslēgas vērtības atbalsts: Jaukšana ir ideāli piemērota atslēgas vērtību datu struktūru ieviešanai.
- Ātra datu izguve: Jaukšana ļauj ātri piekļūt elementiem ar pastāvīgu sarežģītību.
- Efektivitāte: Ievietošanas, dzēšanas un meklēšanas darbības ir ļoti efektīvas.
- Atmiņas izmantošanas samazināšana: Jaukšanai ir nepieciešams mazāk atmiņas, jo tā elementu glabāšanai piešķir fiksētu vietu.
- Mērogojamība: Jaukšana labi darbojas ar lielām datu kopām, saglabājot pastāvīgu piekļuves laiku.
- Drošība un šifrēšana: Jaukšana ir būtiska drošai datu glabāšanai un integritātes pārbaudei.
Lai uzzinātu vairāk par jaukšanu, lūdzu, skatiet Ievads jaukšanā — datu struktūras un algoritmu apmācības