Kako je strukturirana hash tabela u containeru…

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

Принцип рада:

Хеширање: Кључ се претвара у целобројни број — хеш-код — помоћу хеш-функције.
Индексирање: Хеш-код се користи за одређивање индекса (кошнице или бакета) у низу показивача или листа.
Складиштење: У свакој кошници се чувају парови кључ-вредност.

Особине:

Кошнице: Хеш-табела се састоји од низа кошница. Број кошница може се динамички мењати (ре-хеширање) када достигне одређени коефицијент оптерећења.
Колизије: Различити кључеви могу давати исти хеш-код. Ово се назива колизија. За решавање колизија у 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;

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

Израчунава се хеш-код кључа.
Одређује се индекс кошнице: bucket_index = hash(key) % num_buckets.
Пара кључ-вредност се додаје у листу елемената у тој кошници. Ако кључ већ постоји, вредност се ажурира.

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

Израчунава се хеш-код кључа.
Одређује се индекс кошнице.
Прође се кроз листу елемената у тој кошници, поредећи кључеве помоћу оператора ==.

Рехеширање се дешава када број елемената у односу на број кошница прелази задати праг (load factor). Тада се креира нови, већи низ кошница, и сви елементи из старих кошница се ре-хеширају и премештају у нове.

Kako je strukturirana hash tabela u containeru unordered_map?