Açar ilə sürətli axtarış üçün məlumat strukturu necə dizayn edərdiniz?

Açar açarına görə sürətli axtarış üçün adətən hash funksiyasından istifadə edən məlumat quruluşu — hash cədvəli (hash table) istifadə olunur. Dizaynın əsas elementləri:

1. Kovalar (sepetlər) massivləri — əsas konteyner elementləri saxlamaq üçün.
2. Hash funksiyası — açarı massiv indeksinə çevirir.
3. Çakışma idarəetməsi — iki açar eyni indeksi verdikdə.

Çakışma idarəetməsinin nümunəsi:

• Zəncirləmə (chaining): hər sepetdə eyni indeksi paylaşan elementlərin əlaqəli siyahısı saxlanılır.
• Açıq ünvanlama (open addressing): çakışma zamanı növbəti boş hüceyrə axtarılır.

C++-də zəncirləmə ilə nümunə:

#include <vector>
#include <list>
#include <string>

class HashTable {
    static const int SIZE = 100;
    std::vector<std::list<std::pair<std::string, int>>> table;

    int hash(const std::string& key) {
        int hashVal = 0;
        for (char c : key) {
            hashVal = (hashVal * 31 + c) % SIZE;
        }
        return hashVal;
    }

public:
    HashTable() : table(SIZE) {}

    void insert(const std::string& key, int value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                kv.second = value; // yeniləmə
                return;
            }
        }
        table[idx].emplace_back(key, value);
    }

    bool find(const std::string& key, int& value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                value = kv.second;
                return true;
            }
        }
        return false;
    }
};

Bu yanaşma orta hesabla axtarış vaxtını O(1)-ə yaxın təmin edir.