Sobes.tech
Кӯмаки мусоҳиба
Захираҳо
Тайёрии мусоҳиба
Захираҳо
Ҷустуҷӯи кор
Захираҳо
Ҳуқуқӣ
Бозгашт ба саволҳо
Middle

Чӣ гуна хештаблица дар контейнери unordered_map сохта шудааст?

sobes.tech AI

Ҷавоб аз AI

unordered_map дар C++ ба хеш-таблица татбиқ шудааст.

Принсипи кор:

  1. Хешгирӣ: Калид ба рақами умумӣ — хеш-код — бо истифода аз функсияи хеш табдил дода мешавад.
  2. Индекси: Хеш-код барои муайян кардани индекс (қуттӣ ё бакет) дар массиви ишораҳо ё рӯйхатҳо истифода мешавад.
  3. Захира: Дар ҳар як қуттӣ ҷуфтҳои калид-арзиш нигоҳ дошта мешаванд.

Хусусиятҳо:

  • Қуттӣ: Хеш-таблиса аз массиви қуттӣ иборат аст. Миқдори қуттӣ метавонад динамикӣ тағир ёбад (реҳешинг) вақте ки нишондиҳандаи бориш (load factor) ба меъёр мерасад.
  • Коллизияҳо: Калидҳои гуногун метавонанд як хеш-кодро диҳанд. Ин коллизия номида мешавад. Барои ҳал кардани коллизияҳо дар 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. Рӯйхати элементҳо дар ин қуттӣ гузаронида мешавад, калидҳо бо истифода аз оператор == муқоиса карда мешаванд.

Рехешинг вақте ки шумораи элементҳо нисбат ба шумораи қуттӣ аз маржаи муайяншуда (load factor) зиёд мешавад, анҷом меёбад. Дар ин ҳолат, массиви нави калонтар сохта мешавад ва ҳамаи элементҳо аз қуттӣҳои кӯҳна реҳеш карда, ба қуттӣҳои нав интиқол дода мешаванд.

ГузаштаОянда