Как е структурирана хеш таблица в контейнера unordered_map?

unordered_map в C++ е реализиран като хеш таблица.

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

1. Хеширане: Ключът се преобразува в цяло число — хеш код — с помощта на хеш функция.
2. Индексиране: Хеш кодът се използва за определяне на индекса (кофа или bucket) в масив от указатели или списъци.
3. Съхранение: Във всеки коф се съхраняват двойки ключ-стойност.

Характеристики:

• Кофове: Хеш таблицата се състои от масив от кофове. Броят на кофовете може да се променя динамично (rehashing), когато се достигне определен коефициент на натоварване.
• Колизии: Различни ключове могат да дават един и същ хеш код. Това се нарича колизия. За решаване на колизиите unordered_map използва метода ** chaining **: елементите с един и същ хеш се добавят към свързан списък (или друга структура от данни) в съответния коф.
• Функция за хеширане и функция за сравнение: За правилната работа са необходими две неща:
  • Добра хеш функция, която равномерно разпределя ключовете по кофовете, минимизирайки колизиите.
  • Функция за еквивалентност (==), за да се различават ключовете с един и същ хеш код в един и същи коф.
• Производителност: Средно операциите по вмъкване, изтриване и търсене имат времева сложност O(1). В най-лошия случай (например, при много колизии или лошо подбран хеш-функция) производителността може да се влоши до O(n), където n е броят на елементите.

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

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // За свързан списък в кофата
};

struct Bucket {
  Node* head; // Указател към началото на списъка
};

Bucket* buckets; // Масив от кофове
size_t num_buckets;

Процес на добавяне на елемент:

1. Изчислява се хеш кодът на ключа.
2. Определя се индексът на кофата: bucket_index = hash(key) % num_buckets.
3. Парът ключ-стойност се добавя към списъка с елементи в тази кофа. Ако ключът вече съществува, стойността се актуализира.

Процес на търсене на елемент:

1. Изчислява се хеш кодът на ключа.
2. Определя се индексът на кофата.
3. Прохожда се списъкът с елементи в тази кофа, сравнявайки ключовете с търсения ключ с помощта на оператора ==.

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