Ինչպես է կառուցված hash-թերթը unordered_map կոնտեյներում?

unordered_map C++-ի մեջ իրականացվում է որպես հեշ-թերթ:

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

1. Հեշավորում: Կլիչը փոխարկվում է ամբողջ թիվ՝ հեշ-կոդ՝ հեշ-ֆունկցիայի միջոցով:
2. Ինդեքսավորում: Հեշ-կոդը օգտագործվում է որոշելու համար ինդեքսը (խցիկը կամ բաքը) ցուցակի կամ ցուցակների զանգվածում:
3. Պահպանում: Յուրաքանչյուր խցիկում պահվում են բանալին-արժեք զույգեր:

Հատկություններ:

• Խցիկներ: Հեշ-թերթը բաղկացած է խցիկների զանգվածից: Խցիկների քանակը կարող է դինամիկ փոխվել (վերահաշվարկ) որոշակի բեռնման գործակիցին հասնելիս:
• Կոլիզիաներ: Տարբեր բանալիները կարող են տալ նույն հեշ-կոդը: Սա կոչվում է կոլիզիա: Կոլիզիաները լուծելու համար unordered_map-ում օգտագործվում է շղթայման (chaining) մեթոդը՝ նույն հեշով տարրերը ավելացվում են կապված ցանկում կամ այլ տվյալների կառուցվածքում:
• Հեշ-ֆունկցիա և համեմատության ֆունկցիա: Ճիշտ աշխատանքի համար անհրաժեշտ են երկու բան.
  • Լավ հեշ-ֆունկցիա, որը հավասարաչափ տարածում է բանալիները խցիկների միջև՝ նվազեցնելով կոլիզիաները:
  • Համեմատության ֆունկցիա (== օպերատոր), որը տարբերում է նույն հեշ-կոդով բանալիները:
• Արդյունավետություն: Միջինում, ավելացման, հեռացման և որոնման գործողությունները ունեն ժամանակային բարդություն O(1): վատագույն դեպքում (օրինակ, շատ կոլիզիաներ կամ վատ ընտրված հեշ-ֆունկցիա) կարող է դեգրադացնել մինչև O(n), որտեղ n՝ տարրերի քանակը:

Նմուշային կառուցվածք (պարզեցված):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Կապված ցանկի համար
};

struct Bucket {
  Node* head; // Ցուցակ սկսելու համար
};

Bucket* buckets; // Խցիկների զանգված
size_t num_buckets;

Ավելացման գործընթաց:

1. Հաշվարկվում է բանալիի հեշ-կոդը:
2. Որոշվում է խցիկի ինդեքսը՝ bucket_index = hash(key) % num_buckets:
3. Բանալի-արժեք զույգը ավելացվում է այդ խցիկի ցանկում: Եթե բանալին արդեն կա, արժեքը թարմացվում է:

Որոնման գործընթաց:

1. Հաշվարկվում է բանալիի հեշ-կոդը:
2. Որոշվում է խցիկի ինդեքսը:
3. Գնահատվում է այդ խցիկի ցանկը՝ համեմատելով բանալիները == օպերատորով:

Վերահաշվարկը կատարվում է, երբ տարրերի քանակը գերազանցում է սահմանված շեմը (load factor): Այդ ժամանակ ստեղծվում է նոր, մեծածավալ զանգված և բոլոր տարրերը վերահաշվարկվում և տեղափոխվում նոր խցիկներ։