我现在一直在编写图像处理算法，在某些时候我需要收集一些关于转换像素的统计信息，以便更深入地了解我应该遵循的进一步开发方向。我需要收集的信息格式如下:

key: RGB value
value: int

我所做的是打开转换后的图像并遍历它，将我需要的值保存到具有以下签名的 std::unordered_map:

typedef std::unordered_map<boost::gil::rgb8_pixel_t, unsigned int> pixel_map_t;

在循环中:

for(int y = 0; y < vi.height(); y++) {
    SrcView::x_iterator dst_it = src.row_begin(y);
    for(int x = 0; x < vi.width(); x++, hits++) {
        diff_map.insert(std::make_pair(dst_it[x], /* some uint32 */));
    } 

我还写了一个自定义哈希函数(这是一个完美的哈希函数:256^2 x R + 256 x G + B - 因此无论桶和哈希表的布局如何(合理扩展)，冲突都应该是最小的。

我注意到，插入速度非常慢! - 在达到第 11 次迭代后，插入速度下降了大约 100 倍。我有大量的碰撞! 尽管图像中的重复颜色数量非​​常少。

之后，我想消除代码中任何可能的错误，并开始使用具有原始键类型(如 int)的 STL 哈希函数对 unordered_map 进行基准测试。

基准测试的代码是:

std::size_t hits = 0, colls = 0;
for(int y = 0; y < vi.height(); y++) {
    SrcView::x_iterator dst_it = src.row_begin(y);

    for(int x = 0; x < vi.width(); x++, hits++) {
        if(diff_map.find(x*y) != diff_map.cend())
            colls++;
        diff_map.insert(std::make_pair(x*y, 10));
    } 
    std::cout << y << "/" << vi.height() << " -> buckets: " 
              << diff_map.bucket_count() << "(" 
              << std::floor(diff_map.load_factor() * 100) 
              << "% load factor) [ " << colls << " collisions / " <<  hits << " hits ]"  << std::endl;
}

...这里是外循环的前 20 次迭代的结果(仅对 int 类型的键使用 STL 的哈希函数):

0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]
10/480 -> buckets: 4096(77% load factor) [ 3872 collisions / 7040 hits ]
11/480 -> buckets: 4096(85% load factor) [ 4161 collisions / 7680 hits ]
12/480 -> buckets: 4096(90% load factor) [ 4612 collisions / 8320 hits ]
13/480 -> buckets: 4096(99% load factor) [ 4901 collisions / 8960 hits ]
14/480 -> buckets: 32768(13% load factor) [ 5315 collisions / 9600 hits ]
15/480 -> buckets: 32768(13% load factor) [ 5719 collisions / 10240 hits ]
16/480 -> buckets: 32768(14% load factor) [ 6148 collisions / 10880 hits ]
17/480 -> buckets: 32768(15% load factor) [ 6420 collisions / 11520 hits ]
18/480 -> buckets: 32768(16% load factor) [ 6870 collisions / 12160 hits ]
19/480 -> buckets: 32768(17% load factor) [ 7135 collisions / 12800 hits ]
20/480 -> buckets: 32768(17% load factor) [ 7584 collisions / 13440 hits ]
21/480 -> buckets: 32768(18% load factor) [ 7993 collisions / 14080 hits ]

这种情况下碰撞的次数是不是太多了？ STL 库一般都是高质量的，但是有 639/640 和 640/1280 用于简单的基于 int 的键听起来至少很奇怪。 还是我做错了什么？

这是我的哈希函数(理论上，应该完全没有冲突 - 但数字非常接近):

template<> 
struct std::hash<boost::gil::rgb8_pixel_t> :
    public std::unary_function<const boost::gil::rgb8_pixel_t&, size_t>
{
    size_t operator()(const boost::gil::rgb8_pixel_t& key) const
    {
        size_t ret =  (static_cast<size_t>(key[0]) << 16) |
                      (static_cast<size_t>(key[1]) << 8) |
                      (static_cast<size_t>(key[2]));
        //return 256 * 256 * key[0] + 256 * key[1] + key[2];
        return ret;
    }
};

现在，这不再有趣了......

我写了这个哈希函数:

template<> 
struct std::hash<int> :
    public std::unary_function<const int&, size_t>
{
    size_t operator()(const int& key) const
    {
        return 5;
    }
};

理论上我的碰撞率应该是100%吧？但结果是:

0/480 -> buckets: 8(12% load factor) [ 639 collisions / 640 hits ]
1/480 -> buckets: 4096(15% load factor) [ 640 collisions / 1280 hits ]
2/480 -> buckets: 4096(23% load factor) [ 960 collisions / 1920 hits ]
3/480 -> buckets: 4096(31% load factor) [ 1281 collisions / 2560 hits ]
4/480 -> buckets: 4096(37% load factor) [ 1654 collisions / 3200 hits ]
5/480 -> buckets: 4096(45% load factor) [ 1964 collisions / 3840 hits ]
6/480 -> buckets: 4096(51% load factor) [ 2370 collisions / 4480 hits ]
7/480 -> buckets: 4096(59% load factor) [ 2674 collisions / 5120 hits ]
8/480 -> buckets: 4096(65% load factor) [ 3083 collisions / 5760 hits ]
9/480 -> buckets: 4096(71% load factor) [ 3460 collisions / 6400 hits ]

为什么？

环境:MSVS2010

最佳答案

colls 不测量碰撞。如果您想测量碰撞，则对于 [0, bucket_count()) 范围内的每个桶 b，获取 bucket_size(b)。这将告诉您每个桶中有多少元素。如果桶中有 2 个或更多项，则桶 b 有 bucket_size(b) - 1 次碰撞。

关于c++ - 悲惨的 unordered_map 插入性能/哈希函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6085177/