unordered_map контейнеринде хеш-таблица кандай түзүлгөн?

unordered_map C++ да ишке ашырылганы хеш-таблица катары.

Ишке ашыруу принциби:

1. Хештөө: Ачкыч бүтүн санга — хеш-кодго — хеш-функция аркылуу айланат.
2. Индекстеу: Хеш-код массивдеги (кошик же бакет) индекс аныктоо үчүн колдонулат.
3. Сактоо: Ар бир кошикте ачкыч-маанилер жуптары сакталат.

Өзгөчөлүктөрү:

• Кошиктер: Хеш-таблица кошиктердин массивинен турат. Кошиктердин саны динамикалык өзгөрүшү мүмкүн (ре-хештөө) белгилүү бир жүктөө коэффициентине жеткенде.
• Коллизиялар: Ар башка ачкычтар бирдей хеш-кодду бере алат. Бул коллизия деп аталат. 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. Тизмек өтүлүп, ачкычтар == оператору менен салыштырылат.

Ре-хештөө, элементтердин саны кошиктердин санына караганда белгиленген чекке жеткенде жүргүзүлөт. Ошондо жаңы, чоңураак массив түзүлүп, бардык элементтер ре-хештелип, жаңы кошиктерге которулат.