Mis on hash-tabel?

Hash-tabel, või assotsiatiivne massiiv, on andmestruktuur, mis rakendab assotsiatiivse massiivi liidest, see tähendab, et see seob võtmeid väärtustega. See kasutab hash-funktsiooni indeksi või "hash" arvutamiseks, kus otsitav väärtus peaks asuma.

Peamised komponendid:

• Võti: Unikaalne elemendi identifikaator.
• Väärtus: Andmed, mis on seotud võtmega.
• Hash-funktsioon: Muudab võtme arvuliseks väärtuseks (hash), mida kasutatakse indeksi määramiseks.
• Kastid (Buckets): massiiv, kus hoitakse võti-väärtus paare.
• Kollisioonide käsitlemine: mehhanism olukordade lahendamiseks, kui erinevad võtmed annavad sama hash (ja seega viitavad ühele kastile). Levinud meetodid:
  • Jadade meetod (Chaining): igas kastis hoitakse nimekiri (näiteks seotud nimekiri) elementidest, mille hash viitab sellele kastile.
  • Ava aadressimise meetod (Open Addressing): kollisiooni korral otsitakse järgmine vaba kast, kasutades algoritme nagu lineaarne, kvadratuurne või topelt hashimine.

Tööpõhimõte:

1. Sisestamine: Hash-funktsioon rakendatakse võtmele, et saada hash. Hashi kasutatakse kastindeksi määramiseks. Võti-väärtus paar salvestatakse selles kastis. Kui toimub kollisioon, rakendatakse kollisioonide käsitlemise meetodit.

   // Näide, kuidas sisestada elementi hash-tabelisse (Jadade meetod)
   function insert(key, value) {
     const hash = hashFunction(key); // Arvutame hash
     const bucketIndex = hash % tableSize; // Määrame kasti indeksi
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Loome nimekirja, kui seda veel ei eksisteeri
     }
     buckets[bucketIndex].push({ key, value }); // Lisame paari nimekirja
   }
   

2. Otsing: Hash-funktsioon rakendatakse võtmele, et saada hash. Hashi kasutatakse kastindeksi määramiseks. Seejärel otsitakse selles kastis element määratud võtmega. Kui kasutatakse jadade meetodit, otsitakse nimekirjast. Ava aadressimise meetodil otsitakse teisi kaste järjest, kuni leitakse vajalik element või määratakse selle puudumine.

   // Näide, kuidas otsida elementi hash-tabelist (Jadade meetod)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Arvutame hash
     const bucketIndex = hash % tableSize; // Määrame kasti indeksi
   
     if (buckets[bucketIndex]) {
       // Otsime elementi kastinimekirjast
       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); // Kui vaja, kustuta
           return value; // Tagasta väärtus
         }
       }
     }
     return undefined; // Elementi ei leitud
   }
   

Eelised:

• Kõrge sisestus-, otsingu- ja kustutustempo keskmiselt (O(1)).
• Efektiivne mälu kasutus võrreldes otse aadressiga massiiviga (kui võtmed on jaotunud ühtlaselt).

Puudused:

• jõudlus võib halveneda suure kollisioonide arvu korral (halvim juhul O(n)).
• ei säilitata elementide sisestamise järjekorda.
• nõuab head hash-funktsiooni võtmete ühtlaseks jaotamiseks.

JavaScriptis on hash-tabelid realiseeritud sisseehitatud objekti Map ja ajalooliselt Object abil. Map on eelistatud, kuna see võimaldab kasutada mis tahes tüüpi andmeid võtmetena ja säilitab lisamise järjekorra. Object teisendab kõik võtmed stringideks.