Оё дуруст аст, ки вақти ҷустуҷӯи унсури дар unordered_set доимӣ аст?

Бале, дар орташӣ вақти ҷустуҷӯи унсури дар std::unordered_set устувор аст — O(1).

Ин тавассути истифодаи ҷадвали хешӣ ба даст меояд. Калиди унсур хеш карда мешавад, ва ин арзиш барои муайян кардани ҷойгиршавии унсур дар ҷадвал истифода мешавад. Агар функсияи хешӣ хуб бошад ва шумораи коллизияҳо кам бошад, дастрасӣ ба унсур мустақим аст.

Аммо, дар ҳолати бадтарин (ҳангоми зиёд будани коллизияҳо), вақти ҷустуҷӯ метавонад хаттӣ шавад — O(n), ки дар он n шумораи унсурҳо мебошад. Ин вақте рӯй медиҳад, ки ҳама ё бештари унсурҳо дар як "бакет"-и хешӣ хеш мешаванд, ва ҷустуҷӯ ба гузаронидани унсурҳо дар он бакет маҳдуд мешавад.

Факторҳое, ки ба иҷроиш таъсир мерасонанд:

• Сифати функсияи хешӣ.
• Коэффициенти бор (load factor) ёфтан дар ҷадвали хешӣ (тафовут байни шумораи унсурҳо ва шумораи бакетҳо). Коэффициенти бор баландтар эҳтимолияти коллизияҳоро зиёд мекунад.

#include <unordered_set>
#include <string>
#include <iostream>

int main() {
    std::unordered_set<std::string> mySet;
    mySet.insert("apple");
    mySet.insert("banana");
    mySet.insert("cherry");

    // Ҷустуҷӯи унсур — дар миёна O(1)
    if (mySet.count("banana")) {
        std::cout << "Меъёри ёфт: banana" << std::endl;
    } else {
        std::cout << "Banana наёфта шуд" << std::endl;
    }

    // Мисол, ки дар он коллизияҳо метавонанд рӯй диҳанд (завис аз функсияи хешӣ ва татбиқ)
    // Аҳамияти коллизияҳо дар миқдори зиёди додаҳо
    // ва/ё функсияи хешии бад
    return 0;
}