Ինչպես է աշխատում հեշ-թերթը?

Հեշ-թերթ (hash table) — դա տվյալների կառուցվածք է, որը իրականացնում է ասոցատիվ զանգված:

Աշխատանքի սկզբունքը՝

1. Հեշավորում։ Յուրաքանչյուր բանալի (key) համար հաշվարկվում է հեշ-կոդ (hash code) հեշ-ֆունկցիայի (hash function) միջոցով։ Հեշ-կոդը ամբողջ թիվ է։
2. Ինդեքսավորում։ Հեշ-կոդը օգտագործվում է որոշելու ինդեքսը (index) ներսի կառուցվածքի զանգվածում (կամ վեկտորում)։ Սովորաբար ինդեքսը հաշվարկվում է որպես hash_code % array_size, որտեղ array_size զանգվածի չափն է։
3. Պահպանում։ Հետազոտվող ինդեքսում պահվում է բանալիին (key) կապված արժեքը (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;
}