Hash cədvəli nədir?

Hash cədvəli (və ya assosiativ massiv, sözlük) — bu məlumatlar quruluşudur və assosiativ massiv interfeysini həyata keçirir, yəni "açar-dəyər" cütlərini saxlamağa və açar vasitəsilə dəyəri sürətlə tapmağa imkan verir.

İş prinsipi hash funksiyasından istifadə etməyə əsaslanır, bu funksiya açarı indeksə (hash) çevirir və bu indeks array (və ya bucket) daxilində yerləşir.

Əsas əməliyyatlar:

1. Yerləşdirmə: Açarın hash-i hesablanır və "açar-dəyər" cütü uyğun bucket-ə yerləşdirilir.
2. Silinmə: Açarın hash-i hesablanır, uyğun bucket tapılır və cüt silinir.
3. Axtarış: Açarın hash-i hesablanır, uyğun bucket tapılır və axtarılan açara malik cüt axtarılır.

Hash cədvəlləri orta hesabla yüksək performans təmin edir; yerləşdirmə, silmə və axtarış əməliyyatları üçün ($O(1)$) idealdır. Lakin, ən pis halda (çox sayda toqquşma, yəni müxtəlif açarların eyni indeksi aldığı zaman) performans $O(n)$-ə enə bilər.

Toqquşmaları həll etmək üçün müxtəlif strategiyalar mövcuddur:

• Separate Chaining: Hər bir bucket-də, eyni hash-ə malik elementlərin siyahısı (məsələn, əlaqəli siyahı) saxlanılır.
• Open Addressing: Toqquşma baş verdikdə, boş yer axtarışı əvvəlcədən müəyyən olunmuş alqoritmlə (xətti, kvadrat sondaşma və s.) həyata keçirilir.

Konseptual nümunə (sadələşdirilmiş):

// Sadə hash funksiyasının nümunəsi
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-bit-ə çevrilmə
  }
  return Math.abs(hash) % size;
}

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

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Əgər açar artıq mövcuddursa, dəyəri yeniləyin
    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; // Açar tapılmadı
  }

  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; // Uğurla silindi
      }
    }
    return false; // Açar tapılmadı
  }
}

// İstifadə
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-də obyektlər ({}) və xəritələr (Map) hash cədvəllərinin nümunələridir. Map çox vaxt üstün tutulur, çünki hər hansı tipdə açarları dəstəkləyir və daxil etmə ardıcıllığını saxlayır.

Yaxşı hash funksiyasının xüsusiyyətləri:

• Tez hesablama.
• Müxtəlif açarlar üçün bərabər paylanma.
• Toqquşmaların minimuma endirilməsi.