Kas ir hash tabula?

Hēša tabula (vai asociatīvais masīvs, vārdnīca) ir datu struktūra, kas realizē asociatīvā masīva interfeisu, tas ir, tā ļauj glabāt "atslēgas-vērtības" pārus un ātri meklēt vērtību pēc atslēgas.

Darbības princips balstās uz hēša funkcijas izmantošanu, kas pārveido atslēgu par indeksu (hēšu) masīvā (vai kaudzē).

Galvenās operācijas:

1. Ievietošana: Aprēķina atslēgas hēšu, un "atslēgas-vērtības" pāris tiek ievietots atbilstošajā kaudzē.
2. Dzēšana: Aprēķina atslēgas hēšu, atrod atbilstošo kaudzi, un pāris tiek dzēsts.
3. Meklēšana: Aprēķina atslēgas hēšu, atrod atbilstošo kaudzi, un meklē pāri ar meklējamo atslēgu.

Hēša tabulas nodrošina vidēji augstu veiktspēju ievietošanas, dzēšanas un meklēšanas operācijās (ideālā gadījumā $O(1)$). Tomēr sliktākajā gadījumā (ja ir daudz kolīziju, kad dažādas atslēgas tiek pārveidotas vienā un tajā pašā indeksā) veiktspēja var samazināties līdz $O(n)$.

Ir dažādas kolīziju risināšanas stratēģijas:

• Aizķēdēšanas metode (Separate Chaining): Katram kaudzes elementam ir saraksts (piemēram, saistīts saraksts) ar vienādu hēšu.
• Atvērta adrešu izmantošana (Open Addressing): Kad rodas kolīzija, brīvās vietas meklēšana tiek veikta pēc iepriekš noteikta algoritma (lineāra, kvadrātiska zondēšana).

Piemērs (vienkāršots):

// Vienkāršotas hēša funkcijas piemērs
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; // Pārveidošana uz 32 bitu veselu
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Aizķēdēšanas metode
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Pārbaude, vai atslēga jau eksistē, lai atjauninātu vērtību
    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; // Atslēga nav atrasta
  }

  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; // Veiksmīgi dzēsts
      }
    }
    return false; // Atslēga nav atrasta
  }
}

// Piemērs izmantošanai
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 objekti ({}) un kartes (Map) ir hēša tabulu realizācijas piemēri. Map biežāk ir priekšroka, jo tas atbalsta jebkāda veida atslēgas un saglabā ievietošanas kārtību.

Laba hēša funkcijas īpašības:

• Ātra aprēķināšana.
• Vienmērīga hēšu sadalījums dažādām atslēgām.
• Kolīziju minimizēšana.