Wat is een hash-tabel?

Een hashtabel (of associatief array, woordenboek) is een datastructuur die de interface van een associatief array implementeert, dat wil zeggen dat het paren "sleutel-waarde" opslaat en snel de waarde kan opzoeken op basis van de sleutel.

Het werkingsprincipe is gebaseerd op het gebruik van een hashfunctie, die de sleutel omzet in een index (hash) binnen de array (of bucket).

Belangrijkste operaties:

1. Invoegen: De hash van de sleutel wordt berekend, en het "sleutel-waarde" paar wordt in de juiste bucket geplaatst.
2. Verwijderen: De hash van de sleutel wordt berekend, de juiste bucket wordt gevonden, en het paar wordt verwijderd.
3. Zoeken: De hash van de sleutel wordt berekend, de juiste bucket wordt gevonden, en het paar met de gezochte sleutel wordt gezocht.

Hash-tabellen bieden gemiddeld een hoge prestaties voor invoeg-, verwijder- en zoekbewerkingen (idealiter $O(1)$). In het slechtste geval (bij veel collisions, wanneer verschillende sleutels op dezelfde index worden omgezet) kan de prestatie dalen tot $O(n)$.

Er zijn verschillende strategieën om collisions op te lossen:

• Separate Chaining: In elke bucket wordt een lijst (bijvoorbeeld een gekoppelde lijst) van elementen met dezelfde hash opgeslagen.
• Open Addressing: Bij een collision wordt de zoektocht naar een vrije plek uitgevoerd volgens een vooraf gedefinieerd algoritme (lineair, kwadratisch, etc.).

Voorbeeld (vereenvoudigd):

// Voorbeeld van een eenvoudige hashfunctie
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Omzetten naar 32-bit
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Separate chaining
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Controleren of de sleutel al bestaat om de waarde bij te werken
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Sleutel niet gevonden
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Succesvol verwijderd
      }
    }
    return false; // Sleutel niet gevonden
  }
}

// Gebruik
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

In JavaScript zijn objecten ({}) en kaarten (Map) voorbeelden van implementaties van hash-tabellen. Map wordt vaak de voorkeur omdat het sleutels van elk type ondersteunt en de volgorde van invoer behoudt.

Eigenschappen van een goede hashfunctie:

• Snelle berekening.
• Gelijkmatige verdeling van hashes voor verschillende sleutels.
• Minimaliseren van collisions.