Maiša yra populiari technika, naudojama norint kuo greičiau saugoti ir gauti duomenis. Pagrindinė maišos naudojimo priežastis yra ta, kad ji atlieka įterpimo, ištrynimo, paieškos ir kitas operacijas

Kodėl naudoti maišą?

Taikant maišą, visas operacijas, tokias kaip įterpimas, paieška ir ištrynimas, galima atlikti O(1), ty pastoviu laiku. Blogiausiu atveju maišos sudėtingumas išlieka O(n), bet vidutinis atvejo laiko sudėtingumas yra O(1).

HashTable

Naudojamas norint sukurti naują maišos lentelę.

Sintaksė:

// 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;  } } 

Pagrindinės operacijos su sintaksė

Gaukite:

Naudojamas ieškant rakto maišos lentelėje ir grąžinant su tuo raktu susietą reikšmę.

Sintaksė:

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

Įdėti:

Naudojamas įterpti naują rakto-reikšmių porą maišos lentelėje.

Sintaksė:

// 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++; } 

Paieška:

Naudojamas vertės paieškai.

Sintaksė:

// 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'); } 

Ištrinti:

Naudojamas tam, kad iš maišos lentelės būtų pašalinta tam tikra rakto ir verčių pora.

Sintaksė:

// 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“ maišos komponentai

1. Maišos lentelė: Maišos lentelė yra masyvo apibendrinimas. Tai suteikia duomenų rinkinio saugojimo funkcionalumą taip, kad prireikus vėliau būtų lengva rasti tuos elementus. Dėl to elemento paieška yra labai efektyvi.

2. Maišos funkcija: Maišos funkcija naudojama duotam raktui paversti tam tikru lizdo indeksu. jis naudojamas kiekvienam galimam raktui susieti į unikalų lizdo indeksą. Jei kiekvienas raktas susietas su unikaliu lizdo indeksu, maišos funkcija žinoma kaip tobula maišos funkcija. Labai sunku sukurti tobulą maišos funkciją, tačiau mūsų, kaip programuotojo, darbas yra sukurti tokią maišos funkciją, kurios pagalba būtų kuo mažiau susidūrimų.

Gera maišos funkcija turi turėti šias savybes:

• Efektyviai apskaičiuojamas.
• Turėtų tolygiai paskirstyti raktus (kiekviena stalo padėtis yra vienodai tikėtina kiekvienam).
• Reikėtų sumažinti susidūrimų skaičių.
• Turėtų būti mažas apkrovos koeficientas (lentelės elementų skaičius padalytas iš lentelės dydžio).

3. Susidūrimo valdymas: Kadangi maišos funkcija suteikia mažą skaičių dideliam raktui, yra galimybė, kad du raktai duoda tą pačią reikšmę. Situacija, kai naujai įdėtas raktas susieja su jau užimtu maišos lentelės lizdu, vadinama susidūrimu ir turi būti tvarkoma naudojant tam tikrą susidūrimo valdymo metodą. Toliau pateikiami susidūrimo valdymo būdai:

• Sujungimas: Idėja yra priversti kiekvieną maišos lentelės langelį nukreipti į susietą įrašų, turinčių tą pačią maišos funkcijos reikšmę, sąrašą. Sujungti grandine paprasta, tačiau reikia papildomos atminties už stalo.
• Atviras adresas: Atvirame adresavime visi elementai saugomi pačioje maišos lentelėje. Kiekviename lentelės įraše yra įrašas arba NIL. Ieškodami elemento, lentelės lizdus nagrinėjame po vieną, kol randamas norimas elementas arba tampa aišku, kad elemento lentelėje nėra.

Diegimas su pavyzdžiu:

1 žingsnis: Sukurkite HashTable klasę su lentelės ir dydžio pradinėmis savybėmis.

2 žingsnis: Pridėkite privačią funkciją setKey(key), kad raktus paverstumėte indeksais.

3 veiksmas: Pridėkite funkcijas insert() ir get() norėdami pridėti ir pasiekti raktų ir verčių poras iš lentelės.

4 veiksmas: Pridėkite funkciją Remove(), kad pašalintumėte raktą iš maišos lentelės.

1 pavyzdys: Tarkime, kad maišos lentelėje turime išsaugoti 5 skaičius 100, 87, 86, 12, 25 ir 9. Tokiu atveju sukursime funkciją setKey, kurioje reikšmę paimsime kaip argumentą ir konvertuosime į maišos lentelės indeksą. Žemiau pateikiamas įgyvendinimas.

Javascript

Išvestis:

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

Išvestyje arba rodo, kad lentelėje yra 1 arba 3 iš eilės tuščios vietos / indeksai.

2 pavyzdys: Tarkime, kad maišos lentelėje norime išsaugoti 5 narių šeimos kontaktinius numerius. Tam sukursime 10 dydžio maišos lentelę ir išsaugosime kontaktinius duomenis. Indeksas bus nustatytas naudojant setKey privačią funkciją, kuri paskutinį kontaktinio numerio skaitmenį pavers maišos lentelės indeksu.

Javascript

Išvestis:

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

Išvestyje arba rodo, kad lentelėje yra 1 arba 3 iš eilės tuščios vietos / indeksai.