Какво е хеш таблица?

Хеш таблица, или асоциативен масив, е структура от данни, която реализира интерфейса на асоциативен масив, тоест свързва ключове с стойности. Тя използва хеш функция за изчисляване на индекса, или "хеш", на кошницата или слота, където трябва да се намира търсената стойност.

Основни компоненти:

• Ключ: Уникален идентификатор на елемента.
• Стойност: Данните, свързани с ключа.
• Хеш функция: Преобразува ключа в числова стойност (хеш), която се използва за определяне на индекса на кошницата.
• Кошници (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)).
• Не се запазва редът на вмъкване на елементите.
• Необходима е добра хеш функция за равномерно разпределение на ключовете.