Ինչպիսի՞ եղանակներ կան հեշ-կոլիզիաները լուծելու համար։

1. Նարցախի մեթոդը (Separate Chaining):

   • Յուրաքանչյուր հեշ-սեղանի տարր (կաբել) ցույց է տալիս կապված ցանկի (կամ այլ տվյալների կառուցվածքի, օրինակ՝ ծառ)։
   • Բոլոր այն տարրերը, որոնք հեշավորվել են նույն կաբելում, ավելացվում են այդ ցանկին։

   // Օրինակ՝ կապված ցանկի հանգույցը նարցախների համար
   struct Node {
       int key;
       int value;
       Node* next;
   };
   
   // Կաբելում պահվում է ցուցիչ ցանկի գլխին
   Node* buckets[TABLE_SIZE];
   

2. Բաց հասցեագրման մեթոդներ (Open Addressing):

   • Բոլոր տարրերը անմիջապես պահվում են հեշ-սեղանի զանգվածում։
   • Կոլիզիայի դեպքում որոնվում է հաջորդ ազատ տեղը զանգվածում։
   • Տարբերակները տարբեր են հաջորդ տեղը որոշելու մեթոդով.

     • Գծային փորձարկում (Linear Probing): Ստուգվում են բջիջները հերթականությամբ՝ հաստատված քայլով i, i+1, i+2, ... mod TABLE_SIZE։

       // Գծային փորձարկման օրինակ
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + 1) % TABLE_SIZE;
       }
       // Այժմ table[i] կամ դատարկ է, կամ որոնվող տարրն է
       

     • Կվադրատիկ փորձարկում (Quadratic Probing): Ստուգվում են բջիջները՝ քայլով, որը կախված է փորձի քառակուսուց i, i+1², i+2², ... mod TABLE_SIZE։

       // Կվադրատիկ փորձարկման օրինակ
       int hash(int key) { return key % TABLE_SIZE; }
       
       int i = hash(key);
       int attempt = 0;
       while (table[i] != EMPTY && table[i].key != key && attempt < TABLE_SIZE) {
           attempt++;
           i = (hash(key) + attempt * attempt) % TABLE_SIZE;
       }
       // Այժմ table[i] կամ դատարկ է, կամ որոնվող տարրն է (կամ աղյուսակը լցված է)
       

     • Երկակի հեշավորում (Double Hashing): Օգտագործվում է երկրորդ հեշ-ֆունկցիան՝ փորձի քայլը որոշելու համար i, i + step, i + 2*step, ... mod TABLE_SIZE, որտեղ step հաշվարկվում է երկրորդ հեշ-ֆունկցիայից։

       // Երկակի հեշավորման օրինակ
       int hash1(int key) { return key % TABLE_SIZE; }
       int hash2(int key) { return 1 + (key % (TABLE_SIZE - 1)); }
       
       int i = hash1(key);
       int step = hash2(key);
       while (table[i] != EMPTY && table[i].key != key) {
           i = (i + step) % TABLE_SIZE;
       }
       // Այժմ table[i] կամ դատարկ է, կամ որոնվող տարրն է
       

3. Տարբերակային չափի փոփոխություն (Resizing):

   • Երբ լցվածության գործակիցը հասնում է որոշակի մակարդակի, ստեղծվում է նոր, ավելի մեծ հեշ-սեղան։
   • Բոլոր տարրերը հեշավորվում են նորից և տեղադրվում են նորում։

   // Լոգիկայի օրինակ resize-ի ժամանակ
   if (current_size / (double)table_size > max_load_factor) {
       // Նոր կրկնակի չափի սեղան ստեղծել
       // Բոլոր տարրերը հեշավորել և տեղադրել նոր սեղանում
       // Հին սեղանը ջնջել
   }
   

Ընտրությունը կախված է կատարողականության, հիշողության, իրականացման բարդության և սպասվող լցվածության գործակիցից։ Նարցախի մեթոդը սովորաբար ավելի պարզ է և լավ է աշխատում բարձր լցվածության գործակիցների դեպքում, բայց պահանջում է լրացուցիչ հիշողություն ցուցիչների համար։ Բաց հասցեագրման մեթոդները կարող են ավելի արդյունավետ օգտագործել հիշողությունը, բայց ավելի զգայուն են հեշ-ֆունկցիայի ընտրության և "հավաքման" խնդիրների նկատմամբ։ Resize-ը անհրաժեշտ է արդյունավետությունը պահպանելու համար՝ երբ տարրերի թիվը մեծանում է։