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

Хеш таблицата (hash table) е структура от данни, реализираща асоциативен масив.

Принцип на работа:

1. Хеширане. За всеки ключ (key) се изчислява хеш-код (hash code) с помощта на хеш-функция (hash function). Хеш-кодът е цяло число.
2. Индексиране. Хеш-кодът се използва за определяне на индекс (index) в масива (или вектора) на вътрешната структура на хеш таблицата. Обикновено индексът се изчислява като hash_code % array_size, където array_size е размерът на масива.
3. Съхранение. На намерения индекс в масива се съхранява свързаното с ключа стойност (value).

Проблеми и решения:

• Колизии. Различни ключове могат да дават един и същ хеш-код и, следователно, един и същ индекс в масива. Това се нарича колизия.
  • Методи за разрешаване на колизии:
    • Метод на веригите (Separate Chaining): Във всяка клетка на масива се съхранява списък (списък, вектор и т.н.) от двойки "ключ-стойност". При колизия новата двойка се добавя към този списък. При търсене по индекс се преглежда съответният списък за намиране на желания ключ.
    • Метод на отворената адресация (Open Addressing): При колизия се търси друга свободна клетка в масива по определено правило (пробиране).
      • Линейно пробиране (Linear Probing): Последователно се проверяват клетките index + 1, index + 2 и т.н. по модул на размера на масива.
      • Квадратично пробиране (Quadratic Probing): Проверяват се клетките index + 1^2, index + 2^2 и т.н. по модул на размера на масива.
      • Двоенно хеширане (Double Hashing): Използва се втора хеш-функция за определяне на стъпката за пробиране.

Предимства:

• В средния случай операциите по вмъкване, изтриване и търсене се изпълняват с сложност O(1).

Недостатъци:

• В най-лошия случай (например при голям брой колизии или лоша хеш-функция) сложността на операциите може да достигне O(n), където n е броят на елементите.
• Изисква допълнителна памет (например за списъци при метода на веригите или за пробиране при отворена адресация).

Пример за използване в C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Създаване на хеш таблица (unordered_map)
    std::unordered_map<std::string, int> възрасти;

    // Вмъкване на елементи
    възрасти["Alice"] = 30;
    възрасти["Bob"] = 25;
    възрасти["Charlie"] = 35;

    // Получаване на стойност по ключ
    std::cout << "Възраст на Alice: " << възрасти["Alice"] << std::endl;

    // Търсене на елемент
    if (възрасти.count("Bob")) {
        std::cout << "Боб е в картата." << std::endl;
    }

    // Изтриване на елемент
    възрасти.erase("Charlie");

    return 0;
}