Hash Table

Hash

En datastruktur der mapper keys til values ved hjælp af en hash funktion for hurtig lookup.

Kompleksitet

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

Beskrivelse

En Hash Table (også kaldet Hash Map eller Dictionary) er en ekstremt effektiv datastruktur til at gemme key-value pairs. Den bruger en hash funktion til at konvertere keys til array indices, hvilket giver næsten konstant tidskompleksitet for lookup, insertion og deletion. Når flere keys hasher til samme indeks kaldes det en collision, som håndteres typisk via chaining (linked lists) eller open addressing (probing). En god hash funktion distribuerer keys jævnt for at minimere collisions. Hash tables har en load factor (antal elementer / antal buckets) der påvirker performance - når den bliver for høj, må tabellen resizes og alle elementer rehashes. Hash tables 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 key-value pair
  set(key, value) {
    const index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    // Check hvis key allerede findes
    for (let pair of this.keyMap[index]) {
      if (pair[0] === key) {
        pair[1] = value;
        return;
      }
    }
    this.keyMap[index].push([key, value]);
  }

  // Hent value baseret på key
  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 key-value pair
  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

•Database indexering for hurtig lookup
•Caching systemer og memoization
•Removing duplicates fra datasets
•Symbol tables i compilere
•Session management i web applikationer

Fordele

✓O(1) gennemsnitlig tid for alle operationer
✓Meget hurtig lookup af data
✓Fleksibel til forskellige datatyper som keys
✓Indbygget i de fleste sprog
✓Ideel til store datasets

Ulemper

✗Ingen ordering af elementer
✗Hash collisions kan reducere performance
✗Ekstra hukommelse til array buckets
✗Worst case O(n) ved mange collisions
✗Resizing er dyrt ved høj load factor

Eksempler fra den virkelige verden

•DNS lookup af domænenavne til IP-adresser
•Browser cookies og session storage
•Telefonbøger (navn til telefonnummer)
•Varelagre (produkt ID til lagerantal)
•Bruger credentials og authentication

Relaterede strukturer

HashMapDictionaryMapSetAssociative Array