Kas yra maišos lentelė?

Heshų lentelė, arba asociatyvus masyvas, yra duomenų struktūra, įgyvendinanti asociatyvaus masyvo sąsają, tai yra ji susieja raktus su reikšmėmis. Ji naudoja maišos funkciją indeksui arba "maišui" apskaičiuoti, kur turėtų būti ieškoma reikšmė.

Pagrindiniai komponentai:

• Raktas: Unikalus elemento identifikatorius.
• Reikšmė: Duomenys, susiję su raktu.
• Maišos funkcija: paverčia raktą skaitine reikšme (maišu), kuri naudojama nurodyti indeksą.
• Krepšiai (Buckets): masyvas, kuriame saugomos raktų-reikšmių poros.
• Kolizijų tvarkymas: mechanizmas spręsti situacijas, kai skirtingi raktai duoda tą patį maišą (ir taip nurodo tą patį krepšį). Paplitę metodai:
  • Grandinių metodas (Chaining): kiekviename krepšyje saugoma sąrašas (pvz., susietas sąrašas) elementų, kurių maišai nurodo į tą krepšį.
  • Atvirosios adresacijos metodas (Open Addressing): kolizijos atveju ieškoma kito laisvo krepšio naudojant algoritmus, tokius kaip linijinis, kvadratinis ar dvigubas maišavimas.

Darbo principas:

1. Įterpimas: Maišos funkcija taikoma raktui, kad gauti maišą. Maišas naudojamas nurodyti krepšio indeksą. Raktas-reikšmės pora saugoma šiame krepšyje. Jei įvyksta kolizija, taikomas kolizijų tvarkymo metodas.

   // Pavyzdys, kaip įterpti elementą į maišų lentelę (Grandinių metodas)
   function insert(key, value) {
     const hash = hashFunction(key); // Apskaičiuojame maišą
     const bucketIndex = hash % tableSize; // Nustatome krepšio indeksą
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Sukuriame sąrašą, jei jis dar neegzistuoja
     }
     buckets[bucketIndex].push({ key, value }); // Pridedame porą į sąrašą
   }
   

2. Paieška: Maišos funkcija taikoma raktui, kad gauti maišą. Maišas naudojamas nurodyti krepšio indeksą. Tada šiame krepšyje ieškoma elemento su nurodytu raktu. Jei naudojama grandinių metodas, ieškoma sąrašo viduje. Atvirosios adresacijos atveju, ieškoma kitų krepšių nuosekliai, kol bus rastas reikalingas elementas arba nustatoma jo nebuvimas.

   // Pavyzdys, kaip ieškoti elemento maišų lentelėje (Grandinių metodas)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Apskaičiuojame maišą
     const bucketIndex = hash % tableSize; // Nustatome krepšio indeksą
   
     if (buckets[bucketIndex]) {
       // Ieškome elemento krepšio sąraše
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Jei reikia ištrinti
           return value; // Grąžinti reikšmę
         }
       }
     }
     return undefined; // Elementas nerastas
   }
   

Privalumai:

• Aukšta operacijų įterpimo, paieškos ir ištrynimo greitis vidutiniškai (O(1)).
• Efektyvus atminties naudojimas palyginti su tiesioginiu adresų masyvu (jei raktai paskirstyti tolygiai).

Trūkumai:

• našumas gali sumažėti esant dideliam kolizijų skaičiui (blogiausiu atveju O(n)).
• Nėra išsaugomas elementų įterpimo tvarkos.
• Reikalinga gera maišos funkcija, kad raktai būtų tolygiai paskirstyti.

JavaScript'e maišų lentelės įgyvendintos naudojant įmontuotą objektą Map ir istoriškai Object. Map yra pageidautinas, nes leidžia naudoti bet kokio tipo duomenis kaip raktus ir išlaiko elementų pridėjimo tvarką. Object paverčia visus raktus į eilutes.