c++ 我使用的unordered_map不正确吗？

xghobddn 于 2023-03-05 发布在其他

关注(0)|答案(1)|浏览(174)

我得到的感觉是我错误地使用了一个unordered_map，在这个意义上，我得到的不是平均O（1）复杂度，而是O（n）复杂度。
现在我将Map定义为：

unordered_map<my_class , double> objects_to_values;

关键是我如何定义my_class。
my_class此时由三个整数标识，将它们称为a、b和c。
backbone 看起来像：

class my_class  {
private:
        int _a, _b, _c;

public:
        my_class(int _a, int _b, int _c) {
                this->_a = _a;
                this->_b = _b;
                this->_c = _c;
        }

        int a() const {
                return _a;
        }

        int b() const {
                return _b;
        }

        int c() const {
                return _c;
        }

        bool operator==(const my_class& obj) const {
                return ((a() == obj.a()) && (b() == obj.b()) && (c() == obj.c()));
        }
};

另外，我还有

struct hash<my_class> {
public:
        size_t operator()(const my_class& k) const {
                return ( (hash<int>()(k.c())) ^ (( ((hash<int>()(k.a()))^ (hash<int>()(k.b())
                                << 1) >> 1) << 1) >> 1) );
        }
};

我观察到的是，随着unordered_map大小的增加，我的代码变得非常慢，这可能是因为我调用了find，通常我期望平均为O（1）。
我做得对吗？或者我应该改进散列函数（承认它不太好）？或者我做错了什么？有没有更好的方法来散列范围在0-100000左右的三个值？

c++

来源：https://stackoverflow.com/questions/75606137/am-i-using-unordered-map-incorrectly

1条答案

按热度按时间

vlju58qv1#

我很遗憾地通知您，您的散列函数是BAD™，会导致无数的冲突和性能下降。
a、B、c在-5和5之间的取样：

#include <iostream>
#include <iomanip>
#include <functional>
#include <set>

int main() {
    std::set<std::size_t> values;
    for (int a = -5 ; a <= 5 ; ++a) {
        for (int b = -5 ; b <= 5 ; ++b) {
            for (int c = -5 ; c <= 5 ; ++c) {
                auto const ha = std::hash<int>()(a);
                auto const hb = std::hash<int>()(b);
                auto const hc = std::hash<int>()(c);
                auto const hash = ( hc ^ ( ( (ha ^ (hb << 1) >> 1) << 1) >> 1) );
                values.insert(hash);
                std::cout << "hash(" << a << ", " << b << ", " << c << ") = " << std::hex << hash << std::dec << '\n';
            }
        }
    }
    std::cout << "Colision rate: " << 1.0 - (values.size() / (11.0*11*11)) << "\n";
}

得出的碰撞率约为98%。Demo。

赞(0）回复(0）举报 2023-03-05

我来回答

c++ 我使用的unordered_map不正确吗？

1条答案

相关问题

热门标签

最新问答