Wat is een hash-tabel?

Een hash-tabel, of associatief array, is een datastructuur die de interface van een associatief array implementeert, dat wil zeggen dat het sleutels koppelt aan waarden. Het gebruikt een hashfunctie om een index, of "hash", te berekenen van de bak of slot waar de gezochte waarde zich zou moeten bevinden.

Belangrijke componenten:

• Sleutel: Unieke identificator van het element.
• Waarde: Gegevens die gekoppeld zijn aan de sleutel.
• Hashfunctie: Zet de sleutel om in een numerieke waarde (hash), die wordt gebruikt om de index van de bak te bepalen.
• Bakken (Buckets): Array waarin sleutel-waarde paren worden opgeslagen.
• Collision Handling: Mechanisme om situaties op te lossen waarin verschillende sleutels dezelfde hash genereren (en dus naar dezelfde bak wijzen). Veelgebruikte methoden:
  • Chaining: Elke bak bevat een lijst (bijvoorbeeld, gekoppelde lijst) van elementen waarvan de hashes naar die bak wijzen.
  • Open Adressering: Bij collision wordt de volgende vrije bak gezocht met behulp van algoritmen zoals lineair, kwadratisch of dubbele hashing.

Werking:

1. Invoegen: De hashfunctie wordt toegepast op de sleutel om de hash te verkrijgen. De hash wordt gebruikt om de index van de bak te bepalen. Het sleutel-waarde paar wordt in die bak opgeslagen. Bij collision wordt de collision handling methode toegepast.

   // Voorbeeld van invoegen in een hash-tabel (chaining)
   function insert(key, value) {
     const hash = hashFunction(key); // Bereken hash
     const bucketIndex = hash % tableSize; // Bepaal index
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Maak lijst als die nog niet bestaat
     }
     buckets[bucketIndex].push({ key, value }); // Voeg paar toe aan lijst
   }
   

2. Zoeken: De hashfunctie wordt toegepast op de sleutel om de hash te verkrijgen. De hash wordt gebruikt om de index van de bak te bepalen. Vervolgens wordt in die bak gezocht naar het element met de gegeven sleutel. Bij chaining wordt gezocht in de lijst binnen de bak. Bij open adressering worden andere bakken sequentieel gecontroleerd totdat het benodigde element wordt gevonden of vastgesteld dat het niet bestaat.

   // Voorbeeld van zoeken in een hash-tabel (chaining)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Bereken hash
     const bucketIndex = hash % tableSize; // Bepaal index
   
     if (buckets[bucketIndex]) {
       // Zoek element in de lijst van de bak
       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); // Indien verwijderen nodig
           return value; // Geef waarde terug
         }
       }
     }
     return undefined; // Element niet gevonden
   }
   

Voordelen:

• Snelle invoeg-, zoek- en verwijderbewerkingen gemiddeld (O(1)).
• Efficiënt gebruik van geheugen vergeleken met een directe adresseringsarray (als de sleutels verspreid zijn).

Nadelen:

• Prestaties kunnen afnemen bij veel collisions (slechtste geval O(n)).
• De volgorde van invoegen wordt niet behouden.
• Een goede hashfunctie is vereist voor een gelijkmatige verdeling van de sleutels.

In JavaScript worden hash-tabellen geïmplementeerd via het ingebouwde Map object en historisch via Object. Map is de voorkeur omdat het het gebruik van elk datatype als sleutel mogelijk maakt en de volgorde van toevoegen behoudt. Object converteert alle sleutels naar strings.