Hash cədvəli necə işləyir?

Hash cədvəli (hash table) — əlaqəli massiv tətbiq edən məlumat quruluşudur.

İş prinsipi:

1. Hashing. Hər bir açar (key) üçün hash kodu (hash code) hash funksiyası (hash function) vasitəsilə hesablanır. Hash kodu tam ədəddir.
2. İndeksləmə. Hash kodu, daxili strukturun (məsələn, hash cədvəlinin) massivində (və ya vektor) indeks (index) müəyyən etmək üçün istifadə olunur. Adətən, indeks hash_code % array_size kimi hesablanır, burada array_size massiv ölçüsüdür.
3. Yadda saxlanma. Tapılan indeksdə, açarla əlaqəli dəyər (value) saxlanılır.

Məsələlər və həll yolları:

• Çatışmalar. Müxtəlif açarlar eyni hash kodu verə bilər və nəticədə eyni indeksə malik ola bilər. Bu, çatışma adlanır.
  • Çatışma həll üsulları:
    • Zəncir üsulu (Separate Chaining): Hər massiv hüceyrəsində "açar-dəyər" cütlərinin siyahısı (siyahı, vektor və s.) saxlanılır. Çatışma baş verdikdə, yeni cüt bu siyahıya əlavə olunur. İndeksə görə axtarışda, müvafiq siyahı yoxlanılır və lazım olan açar tapılır.
    • Açıq ünvanlama (Open Addressing): Çatışma baş verdikdə, müəyyən bir qayda (sınaq) ilə başqa boş hüceyrə axtarılır.
      • Xətti sınaq (Linear Probing): index + 1, index + 2, və s. hüceyrələr ardıcıl yoxlanılır, massiv ölçüsü ilə mod alınır.
      • Kvadrat sınaq (Quadratic Probing): index + 1^2, index + 2^2, və s. hüceyrələr yoxlanılır, massiv ölçüsü ilə mod alınır.
      • İkiqat hash (Double Hashing): İkinci hash funksiyası istifadə edilərək, sınaq addımı müəyyən edilir.

Üstünlüklər:

• Orta hesabla, əlavə etmə, silmə və axtarış əməliyyatları O(1) mürəkkəbliklə həyata keçirilir.

Çatışmazlıqlar:

• Ən pis halda (məsələn, çox sayda çatışma və ya pis hash funksiyası ilə) əməliyyatların mürəkkəbliyi O(n) çatır, burada n elementlərin sayıdır.
• Əlavə yaddaş tələb edir (məsələn, zəncir üsulunda siyahılar və ya açıq ünvanlamada sınaq üçün).

C++-da istifadə nümunəsi (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Hash cədvəli yaradılması (unordered_map)
    std::unordered_map<std::string, int> yaş;

    // Elementlərin əlavə olunması
    yaş["Alice"] = 30;
    yaş["Bob"] = 25;
    yaş["Charlie"] = 35;

    // Açar ilə dəyəri alma
    std::cout << "Alice-in yaşı: " << yaş["Alice"] << std::endl;

    // Elementin axtarışı
    if (yaş.count("Bob")) {
        std::cout << "Bob xəritədədir." << std::endl;
    }

    // Elementin silinməsi
    yaş.erase("Charlie");

    return 0;
}