Kas ir hash tabula?

Hesh-tabula, vai asociatīvs masīvs, ir datu struktūra, kas realizē asociatīvā masīva interfeisu, tas ir, tā sasaista atslēgas ar vērtībām. Tā izmanto hash funkciju, lai aprēķinātu indeksu vai "hash" vietu, kurā meklējama vērtība.

Galvenās sastāvdaļas:

• Atslēga: Unikāls elementa identifikators.
• Vērtība: Dati, kas saistīti ar atslēgu.
• Hash funkcija: Pārvērš atslēgu skaitliskā vērtībā (hash), kas tiek izmantota, lai noteiktu indeksu.
• Korpusi (Buckets): masīvs, kurā glabājas atslēgu-vērtību pāri.
• Kolīziju apstrāde: mehānisms situācijām, kad dažādi atslēgas dod vienu un to pašu hash (t.i., norāda uz vienu korpusu). Izplatītās metodes:
  • ** ķēžu metode (Chaining):** katrā korpusā ir saraksts (piemēram, saistīts saraksts) elementiem, kuru hash norāda uz šo korpusu.
  • Atvērtās adresēšanas metode (Open Addressing): kolīzijas gadījumā meklē nākamo brīvo korpusu, izmantojot algoritmus, piemēram, lineāru, kvadrātisku vai dubultu hashēšanu.

Darba princips:

1. Ievietošana: Hash funkcija tiek piemērota atslēgai, lai iegūtu hash. Hash tiek izmantots, lai noteiktu korpusa indeksu. Atslēgu-vērtību pāris tiek glabāts šajā korpusā. Ja notiek kolīzija, tiek izmantota koliziju apstrādes metode.

   // Piemērs, kā ievietot elementu hash tabulā (ķēžu metode)
   function insert(key, value) {
     const hash = hashFunction(key); // Aprēķinām hash
     const bucketIndex = hash % tableSize; // Nosakām korpusa indeksu
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Izveidojam sarakstu, ja tas vēl nepastāv
     }
     buckets[bucketIndex].push({ key, value }); // Pievienojam pāri sarakstam
   }
   

2. Meklēšana: Hash funkcija tiek piemērota atslēgai, lai iegūtu hash. Hash tiek izmantots, lai noteiktu korpusa indeksu. Tad šajā korpusā meklē elementu ar norādīto atslēgu. Ja tiek izmantota ķēžu metode, meklē sarakstā. Atvērtās adresēšanas gadījumā, meklē citus korpusus secīgi, līdz tiek atrasts nepieciešamais elements vai tiek noteikts tā neesamība.

   // Piemērs, kā meklēt elementu hash tabulā (ķēžu metode)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Aprēķinām hash
     const bucketIndex = hash % tableSize; // Nosakām korpusa indeksu
   
     if (buckets[bucketIndex]) {
       // Meklējam elementu korpusa sarakstā
       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); // Ja nepieciešams, izdzēst
           return value; // Atgriezt vērtību
         }
       }
     }
     return undefined; // Elements nav atrasts
   }
   

Priekšrocības:

• Augsta operāciju ievietošanas, meklēšanas un dzēšanas ātrums vidēji (O(1)).
• Efektīva atmiņas izmantošana salīdzinājumā ar tiešo adresēšanas masīvu (ja atslēgas ir izplatītas vienmērīgi).

Trūkumi:

• veiktspēja var samazināties, ja ir liels koliziju skaits (sliktākajā gadījumā O(n)).
• Netiek saglabāts elementu ievietošanas secība.
• Nepieciešama laba hash funkcija, lai vienmērīgi sadalītu atslēgas.

JavaScript, hash tabulas ir realizētas ar iebūvēto objektu Map un vēsturiski Object. Map ir vēlams, jo tas ļauj izmantot jebkāda veida datus kā atslēgas un saglabā pievienošanas secību. Object pārveido visus atslēgas uz virknes.