Чӣ тавр кор мекунад ҷадвали ҳеш?

Ҳеш-таблица (hash table) — это структура данных, реализующая ассоциативный массив.

Принцип работы:

1. Ҳешлаш. Барои ҳар як калид (key) ҳеш-код (hash code) бо ёрии функсияи ҳеш (hash function) ҳисоб карда мешавад. Ҳеш-код — ин рақами бутун аст.
2. Индексикунонӣ. Ҳеш-код барои муайян кардани индекс (index) дар массив (ё вектор) дар сохтори дохилии ҳеш-таблица истифода мешавад. Одатан индекс ҳамчун hash_code % array_size ҳисоб карда мешавад, ки дар он array_size андозаи массив аст.
3. Захира. Дар индекс ёфтаро бо арзиши (value) ки бо калид алоқаманд аст, нигоҳ медоранд.

Масъалаҳо ва ҳалли онҳо:

• Коллизияҳо. Калидҳои гуногун метавонанд як ҳеш-кодро диҳанд ва, бинобар ин, як ва ҳамон индекс дар массив. Инро коллизия меноманд.
  • Роҳҳои ҳалли коллизияҳо:
    • Методи занҷиркунии ҷудошаванда (Separate Chaining): Дар ҳар як ҳуҷраи массив рӯйхат (ё вектор ва ғайра) аз ҷуфтҳои "калид-арзиш" нигоҳ дошта мешавад. Дар ҳолати коллизия, ҷуфти нав ба ин рӯйхат илова карда мешавад. Дар ҷустуҷӯ ба индекс, рӯйхати дахлдор барои ёфтани калиди лозимро мебаранд.
    • Методи суръатбахшии дари кушод (Open Addressing): Дар ҳолати коллизия, ҷустуҷӯи ҳуҷраи дигар дар массив бо истифода аз қоидаҳои муайян (пробкунии) дигар мешавад.
      • Пробкунии хаттӣ (Linear Probing): Ҳуҷраҳо index + 1, index + 2 ва ғайра, бо модулу андозаи массив, санҷида мешаванд.
      • Пробкунии квадратики (Quadratic Probing): Ҳуҷраҳо index + 1^2, index + 2^2 ва ғайра, бо модулу андозаи массив, санҷида мешаванд.
      • Двуҳештӣ (Double Hashing): Барои муайян кардани қадами пробкунии функсияи ҳеши дуввум истифода мешавад.

Фоидаҳо:

• Дар миёна, амалиётҳои ворид кардан, тоза кардан ва ҷустуҷӯ бо мураккабии O(1) иҷро мешаванд.

Норасоиҳо:

• Дар ҳолати бадтарин (масалан, дар ҳолати зиёд шудани коллизияҳо ё функсияи ҳеши бад), мураккабии амалиётҳо метавонад ба O(n) расад, ки дар он n шумораи элементҳо аст.
• Ниёз ба ёрии ёддоштӣ (масалан, барои рӯйхатҳо дар методи занҷиркунии ё барои пробкунии дар ҳолати дари кушод).

Масалан дар C++ (std::unordered_map):

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

int main() {
    // Эҷоди ҳеш-таблица (unordered_map)
    std::unordered_map<std::string, int> синну сол;

    // Ворид кардани элементҳо
    синну сол["Alice"] = 30;
    синну сол["Bob"] = 25;
    синну сол["Charlie"] = 35;

    // Гирифтани арзиш бо калид
    std::cout << "Синну соли Alice: " << синну сол["Alice"] << std::endl;

    // Ҷустуҷӯи элемент
    if (синну сол.count("Bob")) {
        std::cout << "Bob дар харита аст." << std::endl;
    }

    // Тоза кардани элемент
    синну сол.erase("Charlie");

    return 0;
}