Ի՞նչ է հեշ աղյուսակը։

Հեշ աղյուսակ, կամ ասոցատիվ զանգված, տվյալների կառուցվածք է, որը իրականացնում է ասոցատիվ զանգվածի ինտերֆեյսը, այսինքն՝ այն կապում է բանալիները արժեքների հետ: Այն օգտագործում է հեշային ֆունկցիա՝ հաշվարկելու ինդեքսը, կամ «հեշը», տուփի կամ սլոտի, որտեղ պետք է գտնվի որոնվող արժեքը:

Հիմնական բաղադրիչները՝

• Բանալին: տարրի եզակի նույնականացուցիչ:
• Արժեք: տվյալներ, որոնք կապված են բալնին:
• Հեշային ֆունկցիա: փոխում է բալնին թվային արժեք (հեշ), որը օգտագործվում է ինդեքսը որոշելու համար:
• Տուփեր (Buckets): զանգված, որտեղ պահվում են բանալիներ-արժեք զույգերը:
• Կոնֆլիկտների կառավարում (Collision Handling): մեխանիզմ՝ լուծելու իրավիճակները, երբ տարբեր բանալիներ տալիս են նույն հեշը (և հետևաբար ցույց են տալիս նույն տուփին): տարածված մեթոդներ՝
  • Ցանցային մեթոդ (Chaining): յուրաքանչյուր տուփում պահվում է ցանկ (օրինակ՝ կապված ցանկ), որի հեշը ցույց է տալիս այդ տուփին:
  • Բաց հասցեագրման մեթոդ (Open Addressing): կոնֆլիկտի դեպքում որոնվում է հաջորդ ազատ տուփը՝ օգտագործելով ալգորիթմներ՝ ինչպես գծային, քառակուսային կամ երկկողմ հեշավորում:

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

1. Ավելացում: Հեշային ֆունկցիան կիրառվում է բալնին՝ հեշ ստանալու համար: Հեշը օգտագործվում է տուփի ինդեքսը որոշելու համար: Բանալին-արժեք զույգը պահվում է այդ տուփում: Կոնֆլիկտի դեպքում կիրառվում է կոնֆլիկտների կառավարում:

   // Օրինակ՝ տարր ավելացնել հեշ աղյուսակում (ցանցային մեթոդ)
   function insert(key, value) {
     const hash = hashFunction(key); // Հաշվարկում հեշ
     const bucketIndex = hash % tableSize; // Տուփի ինդեքսի որոշում
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Ցանց ստեղծում, եթե չկա
     }
     buckets[bucketIndex].push({ key, value }); // զույգ ավելացնել ցանկում
   }
   

2. Որոնում: Հեշային ֆունկցիան կիրառվում է բալնին՝ հեշ ստանալու համար: Հեշը օգտագործվում է տուփի ինդեքսը որոշելու համար: Այնուհետև, այդ տուփում, որոնվում է տարր՝ նշված բալնով: Ցանցային մեթոդով, որոնվում է ցանկում: Բաց հասցեագրման դեպքում, հաջորդ տուփերը ստուգվում են հերթականությամբ՝ մինչև գտնել ցանկալի տարրն կամ որոշել նրա բացակայությունը:

   // Օրինակ՝ տարր որոնել հեշ աղյուսակում (ցանցային մեթոդ)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Հաշվարկում հեշ
     const bucketIndex = hash % tableSize; // Տուփի ինդեքսի որոշում
   
     if (buckets[bucketIndex]) {
       // Տուփի ցանկում տարր որոնել
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Եթե անհրաժեշտ է ջնջել
           return value; // Վերադարձնել արժեքը
         }
       }
     }
     return undefined; // Տարր չի գտնվել
   }
   

Առավելություններ՝

• Բարձր արագություն՝ ավելացման, որոնման և ջնջման գործողություններում միջինում (O(1)).
• Էֆեկտիվ օգտագործում հիշողության՝ համեմատած ուղղակի հասցեագրված զանգվածի հետ (եթե բանալիները տարածված չեն):

Թերություններ՝

• Գործողության արդյունավետությունը կարող է նվազել մեծ կոնֆլիկտների դեպքում (վատթարագույն դեպքում՝ O(n)).
• Բանալիների ներդրման կարգը չի պահպանվում:
• Պահանջվում է լավ հեշ ֆունկցիա՝ բանալիների հավասարաչափ բաշխման համար։