Jaukšana ir populārs paņēmiens, ko izmanto, lai pēc iespējas ātrāk saglabātu un izgūtu datus. Galvenais jaukšanas izmantošanas iemesls ir tas, ka tā veic ievietošanu, dzēšanu, meklēšanu un citas darbības

Kāpēc izmantot jaukšanu?

Jaukšanā visas darbības, piemēram, ievietošanu, meklēšanu un dzēšanu, var veikt O(1), t.i., nemainīgā laikā. Sliktākā gadījuma laika sarežģītība jaukšanai joprojām ir O(n), bet vidējā gadījuma laika sarežģītība ir O(1).

HashTable

Izmanto, lai izveidotu jaunu hash tabulu.

Sintakse:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Pamatoperācijas ar sintaksi

Gūt:

Izmanto, lai meklētu atslēgu hash tabulā un atgrieztu ar šo atslēgu saistīto vērtību.

Sintakse:

// function inside hashtable class to  // access a value using its key get(key) {  const target = this._setKey(key);  return this.table[target]; } 

Ievietot:

Izmanto, lai ievietotu jaunu atslēgas vērtību pāri hash tabulā.

Sintakse:

// function to insert a value in the  // hash table using setKey function insert(value) {  const index = this._setKey(value);  this.table[index] = value;  this.size++; } 

Meklēt:

Izmanto, lai meklētu vērtību.

Sintakse:

// search a value (by getting its  // key using setKey function) search(value){  const index = this._setKey(value);  if(this.table[index]==value)  console.log('The value is found at index : ',index);  else  console.log('Not found'); } 

Dzēst:

Izmanto, lai dzēstu noteiktu atslēgu-vērtību pāri no hash tabulas.

Sintakse:

// function to delete a key from the hashtable  delete (key) {  const index = this._setKey(key);  if (this.table[index]) {  this.table[index] = [];  this.size--;  return true;  } else {  return false;  } } 

Javascript jaukšanas komponenti

1. Jaukšanas tabula: Hash tabula ir masīva vispārinājums. Tas nodrošina funkcionalitāti, kurā datu kolekcija tiek glabāta tā, lai vajadzības gadījumā vēlāk būtu viegli atrast šos vienumus. Tas padara elementa meklēšanu ļoti efektīvu.

2. Jaukšanas funkcija: Jaucējfunkcija tiek izmantota, lai pārveidotu doto atslēgu noteiktā slota indeksā. to izmanto, lai kartētu katru iespējamo atslēgu unikālā slota indeksā. Ja katra atslēga ir kartēta unikālā slota indeksā, tad jaucējfunkciju sauc par perfektu jaucējfunkciju. Ir ļoti grūti izveidot perfektu jaucējfunkciju, bet mūsu kā programmētāja uzdevums ir izveidot tādu jaucējfunkciju, ar kuras palīdzību sadursmju skaits būtu pēc iespējas mazāks.

Labai jaucējfunkcijai ir jābūt šādām īpašībām:

• Efektīvi aprēķināms.
• Vienmērīgi jāsadala atslēgas (katrai galda pozīcija ir vienāda iespējama katram).
• Ir jāsamazina sadursmes.
• Jābūt zemam noslodzes koeficientam (vienumu skaits tabulā, dalīts ar tabulas lielumu).

3. Sadursmes apstrāde: Tā kā jaucējfunkcija iegūst nelielu skaitli lielai atslēgai, pastāv iespēja, ka divas atslēgas rada vienādu vērtību. Situāciju, kad tikko ievietota atslēga sakrīt ar jau aizņemtu slotu hash tabulā, sauc par sadursmi, un tā ir jārisina, izmantojot kādu sadursmju apstrādes paņēmienu. Tālāk ir norādīti veidi, kā rīkoties ar sadursmēm.

• Ķēdēšana: Ideja ir likt katrai jaukšanas tabulas šūnai norādīt uz saistīto ierakstu sarakstu, kuriem ir tāda pati jaucējfunkcijas vērtība. Ķēdēšana ir vienkārša, taču tai ir nepieciešama papildu atmiņa ārpus galda.
• Atvērta adresācija: Atvērtajā adresēšanā visi elementi tiek saglabāti pašā hash tabulā. Katrs tabulas ieraksts satur ierakstu vai NIL. Meklējot elementu, mēs pārbaudām tabulas slotus pa vienam, līdz tiek atrasts vēlamais elements vai ir skaidrs, ka elementa tabulā nav.

Īstenošana ar piemēru:

1. darbība: Izveidojiet HashTable klasi ar tabulas un izmēra sākotnējām īpašībām.

2. darbība: Pievienojiet privātu funkciju setKey(key), lai pārveidotu atslēgas indeksos.

3. darbība: Pievienojiet funkcijas insert() un get(), lai pievienotu un piekļūtu atslēgu un vērtību pāriem no tabulas.

4. darbība: Pievienojiet funkciju Remove(), lai noņemtu atslēgu no jaucēj tabulas.

1. piemērs: Pieņemsim, ka mums ir jāsaglabā 5 skaitļi 100,87,86,12,25 un 9 jaucējtabulā. Šajā gadījumā mēs izveidosim funkciju setKey, kurā mēs ņemsim vērtību kā argumentu un pārveidosim to par hash tabulas indeksu. Zemāk ir tā ieviešana.

Javascript

Izvade:

[ 100,  ,  12,  ,  86,  87,  ,  9 ] The value is found at index : 7 Not found [ 100,  ,  [],  ,  86,  87,  ,  9 ] 

Izvadā vai parāda, ka tabulā ir 1 vai 3 secīgas tukšas vietas/indeksi.

2. piemērs: Pieņemsim, ka mēs vēlamies saglabāt 5 cilvēku ģimenes kontaktu numurus jaucēj tabulā. Šim nolūkam mēs izveidosim 10 izmēra jaucējtabulu un saglabāsim kontaktinformāciju. Indekss tiks iestatīts, izmantojot setKey privāto funkciju, kas pārveidos kontakta numura pēdējo ciparu par jaukšanas tabulas indeksu.

Javascript

Izvade:

[ ,  92752521,  98747512,  94755523,  ,  98754525,  ,  98556529 ] The contact number is found at index : 1 Contact Number not found [ ,  [],  98747512,  94755523,  ,  98754525,  ,  98556529 ] 

Izvadā vai parāda, ka tabulā ir 1 vai 3 secīgas tukšas vietas/indeksi.