Таблиғи ҳеш чӣ гуна аст?

Ҳеш таблица ё ёдгории ҳамоҳанг, структураи маълумотест, ки интерфейси ёдгории ҳамоҳангро иҷро мекунад, яъне он калидҳоро бо арзишҳо пайванд мекунад. Вай аз функсияи ҳеш барои ҳисоб кардани индекс ё "ҳеш"-и кутӣ ё слот истифода мебарад, ки дар он арзонтаринамои ҷустуҷӯ бояд қарор гирад.

Компонентҳои асосӣ:

• Калид: Идентификатори беназири элемент.
• Арзиш: Маълумоте, ки бо калид алоқаманд аст.
• Функсияи ҳеш: Калидро ба арзиши рақамӣ (ҳеш) табдил медиҳад, ки барои муайян кардани индекс истифода мешавад.
• Кутҳо (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)).
• Тартиби воридшавии элементҳо нигоҳ дошта намешавад.
• Барои тақсимоти баробар кардани калидҳо, функсияи ҳеши хуб лозим аст.