Хэш таблицасы эмне?

Хэш таблица, же ассоциативдүү массив, маалыматтардын структурасы болуп саналат, ал ассоциативдүү массив интерфейсин ишке ашырат, башкача айтканда ал ачкычтарды маанилер менен байланыштырат. Ал хэш-функцияны колдонуп, индекс же "хэш" эсептейт, ал жерде издөөчү мааниге ээ болушу керек.

Негизги компоненттери:

• Ачкыч: элементтин уникалдуу идентификатору.
• Маалымат: Ачкыч менен байланышкан маалыматтар.
• Хэш-функция: Ачкычты сандык мааниге (хэш) айлантат, ал индекс аныктоо үчүн колдонулат.
• Кутучалар (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)).
• Элементтердин кошулуу тартиби сакталбайт.
• Ачкычтардын бирдей бөлүштүрүлүшү үчүн жакшы хэш-функция талап кылынат.