Mi az a hash-tábla?

Hash-tábla (vagy asszociatív tömb, szótár) egy olyan adatszerkezet, amely megvalósítja az asszociatív tömb felületét, vagyis lehetővé teszi kulcs-érték párok tárolását és gyors keresését kulcs alapján.

A működés alapja egy hash-függvény használata, amely a kulcsot indexre (hash-re) alakítja a tömbön (vagy vödörön) belül.

Fő műveletek:

1. Beszúrás: A kulcs hash értékét számítjuk, és a "kulcs-érték" párt a megfelelő vödörbe helyezzük.
2. Törlés: A kulcs hash értékét számítjuk, megtaláljuk a megfelelő vödröt, és töröljük a párt.
3. Keresés: A kulcs hash értékét számítjuk, megtaláljuk a megfelelő vödröt, és keresünk a kívánt kulccsal.

A hash-táblák átlagosan magas teljesítményt nyújtanak beszúrás, törlés és keresés műveleteknél (ideálisan $O(1)$). Azonban a legrosszabb esetben (amikor sok ütközés van, azaz különböző kulcsok ugyanabba az indexbe kerülnek) a teljesítmény csökkenhet $O(n)$-re.

Különböző ütközéskezelési stratégiák léteznek:

• Láncolási módszer (Separate Chaining): Minden vödörben egy lista (pl. összekapcsolt lista) tárolja ugyanazt a hash-t kapott elemeket.
• Nyitott címzés (Open Addressing): Ütközés esetén a szabad hely keresése egy előre meghatározott algoritmus szerint történik (lineáris, kvadratikus zárójelzés).

Egyszerűsített példa (konceptuálisan):

// Egyszerű hash-függvény példa
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; // 32 bites egészre alakítás
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Láncolási módszer
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Ellenőrzés a kulcs meglétére a frissítéshez
    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; // Kulcs nem található
  }

  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; // Sikeres törlés
      }
    }
    return false; // Kulcs nem található
  }
}

// Használat
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

A JavaScriptben az objektumok ({}) és a térképek (Map) példák hash-táblás megvalósításokra. A Map gyakran előnyösebb, mivel bármilyen típusú kulcsokat támogat, és megőrzi a beszúrás sorrendjét.

Egy jó hash-függvény tulajdonságai:

• Gyors számítás.
• Egyenletes eloszlás a különböző kulcsok között.
• Minimális ütközés.