Определять количество коллизий в unordered_map

Question

Подскажите, как можно реализовать функцию подсчета коллизий в тексте? Подразумевается хранить слова по хэшу в unordered_map<size_t, unordered_set<string>> Хэшер передается параметром. Под коллизией имеется ввиду ситуация когда прочитано слово, которое ранее не встречалось, но хэш совпадает с хэшем одного из предыдущих.

template <typename Hash>
int CollisionsCounter(const Hash& hasher, istream& text) {

}

struct Hasher {
    size_t operator() (const string& str) const {
        size_t result = 0;
        for (char c : str) {
            result += static_cast<size_t>(c);
        }
        return result;
    }
};

int main() {
    hash<string> hasher;
    int collisions = CollisionsCounter(hasher, cin);
    cout << "total collisions: "s << collisions << endl;
} ```

Answer 1

Посмотреть на количество коллизий можно с использованием функций bucket_. Например,

unordered_set<int> m;
m.max_load_factor(10);
for(int i = 0; i < 1000000; ++i) m.insert(i);
cout << "Bucket count: " << m.bucket_count() << endl;
for(int i = 0; i < m.bucket_count(); ++i)
    cout << i << ":  " << m.bucket_size(i) << endl;

(Я специально указал большой max_load_factor, чтобы коллизий было побольше. И использовал unordered_set — он в этом отношении ничем не отличается от unordered_map.)

Вот как это выглядит с использованием своей (жуткой... :)) функции хеширования:

struct myHash
{
    size_t operator()(int i) const
    {
        return i%3;
    };
};

int main()
{
    unordered_set<int,myHash> m;
    m.max_load_factor(10);
    for(int i = 0; i < 1000; ++i) m.insert(i);
    cout << "Bucket count: " << m.bucket_count() << endl;
    for(int i = 0; i < m.bucket_count(); ++i)
        cout << i << ":  " << m.bucket_size(i) << endl;
}

БЛОГ НА HUSL

Определять количество коллизий в unordered_map

Ответы (1 шт):