Ի՞նչ է հեշ-թաբլետի աշխատանքային սկզբունքը։

Հեշ-թաբլիթ (կամ ասոցացվող զանգված) պահպանում է " բանալի-արժեք" զույգեր։ Աշխատանքի սկզբունքը հիմնված է հեշ-ֆունկցիայի օգտագործման վրա, որը փոխում է բանալին թվային ինդեքսի (հեշ)՝ նշելով արժեքի պահեստավորման տեղը զանգվածում (կափարիչում):

Քայլեր:

1. Հաշվարկել հեշը: Տրված բանալիի համար հաշվարկվում է հեշը:

   <?php
   $key = "example";
   $hash = crc32($key); // Պարզ հեշ-ֆունկցիայի օրինակ
   

2. Նշել ինդեքսը: Հեշը փոխարկվում է զանգվածի ինդեքսի, սովորաբար մոդուլային գործողության միջոցով զանգվածի չափով:

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Մուտք գործել կափարիչ: Հաշվարկված ինդեքսով հասանելի է համապատասխան կափարիչը զանգվածում:
4. Կոլիզիաների լուծում: Քանի որ տարբեր բանալիներ կարող են ունենալ նույն հեշը (կոլիզիա), կափարիչը կարող է պարունակել մի քանի "բանալի-արժեք" զույգեր։ Կոլիզիաների լուծման տարբեր մեթոդներ կան՝
   • Կապերի մեթոդ (Separate Chaining): Ամեն մի կափարիչում պահվում է ցանկ (օրինակ՝ կապված ցանկ) "բանալի-արժեք" զույգերի, որոնց հեշերը համընկնում են:
   • Բաց հասցեագրման մեթոդ (Open Addressing): Կոլիզիայի դեպքում կատարվում է կրկնակի որոնում ազատ տեղակայում զանգվածում՝ որոշված կանոնով (ուղղահայաց, քառակուսային փորձարկում, երկակի հեշավորում):

Գործառույթներ:

• Ավելացում: Հաշվարկվում է բանալիի հեշը, որոշվում է ինդեքսը, և "բանալի-արժեք" զույգը տեղադրվում է համապատասխան կափարիչում: Կոլիզիայի դեպքում այն ավելացվում է ցանկում կամ որոնվում է ազատ տեղ:
• Որոնում: Հաշվարկվում է բանալիի հեշը, որոշվում է ինդեքսը։ Հետո որոնվում է արժեքը համապատասխան կափարիչում։
• Ջնջում: Հաշվարկվում է բանալիի հեշը, որոշվում է ինդեքսը։ Հետո գտնում և ջնջում է զույգը ըստ բանալի:

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

• Արագ հասանելիություն տարրերին (միջինում O(1)):
• Մտածողության արդյունավետ օգտագործում:

Կողմնակալություններ:

• Կոլիզիաների մեծ քանակության դեպքում կարող է վատթարանալ աշխատանքային արդյունավետությունը:
• Տախտակի չափը կարող է պահանջել կարգավորումներ (փոխել չափը՝ rehashing)՝ արդյունավետությունը պահպանելու համար։