Kas yra žemės lentelė?

Hesh lentelė (arba asociatyvus masyvas, žodynas) yra duomenų struktūra, kuri įgyvendina asociatyvaus masyvo sąsają, tai yra leidžia saugoti "raktas-reikšmė" poras ir greitai ieškoti reikšmės pagal raktą.

Veikimo principas pagrįstas naudojimu hash funkcijos, kuri paverčia raktą į indeksą (hash) masyve (arba kibire).

Pagrindinės operacijos:

1. Įterpimas: Apskaičiuojamas rakto hash ir "raktas-reikšmė" pora įdedama į atitinkamą kibirą.
2. Šalinimas: Apskaičiuojamas rakto hash, randamas atitinkamas kibiras ir pora ištrinama.
3. Paieška: Apskaičiuojamas rakto hash, randamas atitinkamas kibiras ir ieškoma pora su pageidaujamu raktu.

Hash lentelės užtikrina vidutiniškai aukštą našumą įterpimo, šalinimo ir paieškos operacijoms (idealiu atveju $O(1)$). Tačiau blogiausiu atveju (kai yra daug kolizijų, kai skirtingi raktai paverčiami į tą patį indeksą) našumas gali sumažėti iki $O(n)$.

Yra įvairių strategijų kolizijų sprendimui:

• Ketenų metodas (Separate Chaining): Kiekviename kibire saugomas sąrašas (pvz., susietas sąrašas) elementų su tuo pačiu hash.
• Atvira adresacija (Open Addressing): Kolizijos atveju ieškoma laisva vieta pagal iš anksto nustatytą algoritmą (linijinis, kvadratinis zondavimas).

Pavyzdys (supaprastintas):

// Supaprastinta hash funkcija
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; // Konvertavimas į 32 bitų sveiką skaičių
  }
  return Math.abs(hash) % size;
}

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

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Patikrinimas, ar raktas jau yra, atnaujinant reikšmę
    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; // Raktas nerastas
  }

  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; // Sėkmingai ištrintas
      }
    }
    return false; // Raktas nerastas
  }
}

// Naudojimas
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

JavaScript'e objektai ({}) ir žemėlapiai (Map) yra pavyzdžiai, kaip įgyvendinti hash lenteles. Map dažnai yra pranašesnis, nes palaiko bet kokio tipo raktus ir išlaiko įterpimo tvarką.

Geros hash funkcijos savybės:

• Greitas skaičiavimas.
• Vienodai paskirstyti hash reikšmes skirtingiems raktams.
• Minimalizuoti kolizijas.