主页 / 问题 / 1403972
Accepted
pixelm
Asked:2022-06-26 19:43:23 +0800 CST2022-06-26 19:43:23 +0800 CST

确定 unordered_map 中的碰撞次数

  • 772

你能告诉我如何实现文本中计算碰撞的功能吗？假设在unordered_map<size_t, unordered_set<string>> Hasher中通过哈希存储单词作为参数传递。冲突是指读取一个之前没有遇到过的单词，但哈希值与之前的哈希值匹配的情况。

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;
} ```
c++ stl

1 个回答

  1. Best Answer

    您可以使用函数查看碰撞次数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。）

    这是使用它的 (creepy... :)) 散列函数的样子：

    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;
}
    • 1

相关问题