Hash-tabel

Hash

En datastruktur der mapper nøgler til værdier ved hjælp af en hash-funktion for hurtig opslag.

Kompleksitet

Operation	Tidskompleksitet
Access	`O(1)`
Search	`O(1)`
Insertion	`O(1)`
Deletion	`O(1)`

Beskrivelse

En hash-tabel (også kaldet HashMap eller Dictionary) er en ekstremt effektiv datastruktur til at gemme nøgle-værdi-par. Den bruger en hash-funktion til at konvertere nøgler til array-indekser, hvilket giver næsten konstant tidskompleksitet for opslag, indsættelse og sletning. Når flere nøgler hasher til samme indeks kaldes det en kollision, som håndteres typisk via chaining (lænkede lister) eller open addressing (probing). En god hash-funktion distribuerer nøgler jævnt for at minimere kollisioner. Hash-tabeller har en belastningsfaktor (antal elementer / antal buckets) der påvirker ydeevnen - når den bliver for høj, må tabellen ændres i størrelse og alle elementer rehashes. Hash-tabeller er fundamentale i moderne programmering og findes indbygget i næsten alle sprog som Map, HashMap, Dictionary eller Object.

Kode Eksempel

// JavaScript Hash Table implementation
class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  // Hash-funktion
  _hash(key) {
    let total = 0;
    const PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i];
      const value = char.charCodeAt(0) - 96;
      total = (total * PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  // Tilføj nøgle-værdi-par
  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    // Tjek om nøgle allerede findes
    for (let pair of this.keyMap[index]) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    this.keyMap[index].push([key, value]);
  }

  // Hent værdi baseret på nøgle
  get(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      for (let pair of this.keyMap[index]) {
        if (pair[0] === key) {
          return pair[1];
        }
      }
    }
    return undefined;
  }

  // Fjern nøgle-værdi-par
  delete(key) {
    const index = this._hash(key);
    if (this.keyMap[index]) {
      this.keyMap[index] = this.keyMap[index].filter(
        pair => pair[0] !== key
      );
      return true;
    }
    return false;
  }
}

Anvendelsesområder

•Databaseindeksering for hurtig opslag
•Caching-systemer og memoization
•Fjernelse af duplikater fra datasæt
•Symboltabeller i compilere
•Sessionshåndtering i webapplikationer

Fordele

✓O(1) gennemsnitlig tid for alle operationer
✓Meget hurtig opslag af data
✓Fleksibel til forskellige datatyper som nøgler
✓Indbygget i de fleste sprog
✓Ideel til store datasæt

Ulemper

✗Ingen ordning af elementer
✗Hash-kollisioner kan reducere ydeevne
✗Ekstra hukommelse til array-buckets
✗Værste tilfælde O(n) ved mange kollisioner
✗Størrelsesændring er dyrt ved høj belastningsfaktor

Eksempler fra den virkelige verden

•DNS-opslag af domænenavne til IP-adresser
•Browser-cookies og sessionslagring
•Telefonbøger (navn til telefonnummer)
•Varelagre (produkt-ID til lagerantal)
•Brugerlegitimationsoplysninger og autentificering

Relaterede strukturer

HashMapDictionaryMapSetAssociative Array