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

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

Принципът на работа се базира на използването на хеш-функция, която преобразува ключа в индекс (хеш) вътре в масива (или кофата).

Основни операции:

1. Вмъкване: Изчислява се хешът на ключа и двойката "ключ-стойност" се поставя в съответната кофа.
2. Изтриване: Изчислява се хешът на ключа, намира се съответната кофа и двойката се изтрива.
3. Търсене: Изчислява се хешът на ключа, намира се съответната кофа и се търси двойка с желания ключ.

Хеш таблиците осигуряват средно висока производителност за операциите вмъкване, изтриване и търсене (в идеалния случай $O(1)$). Въпреки това, в най-лошия случай (при голям брой колизии, когато различни ключове се преобразуват в един и същ индекс) производителността може да се понижи до $O(n)$.

Съществуват различни стратегии за разрешаване на колизии:

• Метод на веригите (Separate Chaining): Във всяка кофа се съхранява списък (например свързан списък) от елементи с еднакъв хеш.
• Отворена адресация (Open Addressing): При възникване на колизия търсенето на свободно място се извършва по предварително определен алгоритъм (линейно, квадратично зондиране).

Пример за концепция (опростено):

// Пример за опростена хеш-функция
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Преобразуване в 32-битово цяло
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Метод на веригите
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Проверка за съществуване на ключ за обновяване на стойността
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Ключ не е намерен
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Успешно изтрито
      }
    }
    return false; // Ключ не е намерен
  }
}

// Използване
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

В JavaScript обектите ({}) и картите (Map) са примери за реализиране на хеш таблици. Map често е предпочитана, тъй като поддържа ключове от всякакъв тип и запазва реда на вмъкване.

Характеристики на добра хеш-функция:

• Бързо изчисление.
• Равномерно разпределение на хешовете за различни ключове.
• Минимизиране на колизиите.