可悲的unordered_map插入性能/散列函数

Question

我一直在编写图像处理算法，并且在某些时候我需要收集一些有关转换像素的统计信息，以获得更多关于我应该跟随进一步开发的方向的更多信息。我需要收集什么信息是格式为：

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次迭代的结果（仅使用STL的散列函数对于int类型的键）：

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库的质量很高，但对于简单的基于int的关键声音，至少有奇怪的是639/640和640/1280。 或者我做错了什么？

---

这是我的散列函数（理论上，应该没有冲突可言 - 但数字非常接近）：

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 ] 

为什么？

ENV：MSVS2010

Answer 1

colls不测量碰撞。如果要测量碰撞，则对于[0, bucket_count())范围内的每个存储桶b，请获得bucket_size(b)。这会告诉你每个桶中有多少物品。如果存储桶中有两个或更多物品，则您有b存在bucket_size(b) - 1冲突。

Answer 2

如果我理解你正确地做什么，你可能刚刚开始，这些冲突，因为在你的图像的像素具有相同的颜色，你是重复调用diff_map.insert用于相同颜色的（所以你的散列值的质量是不相关的）。如果你这样做来计算颜色的直方图，你可能不想做“diff_map.insert（std :: make_pair（dst_it [x]，/ * some uint32 * /））;”，而只是做类似

auto it = diff_map.find（dst_it [x]）; if（it == diff_map.end（））it = 1; else（it-> second）++;

Answer 3

您的散列空间大小为24位。要有0个冲突，如果你的数据是完美的，你需要一个散列表来表示你的数据的大小，如果不是，则需要大于25-50％。我的猜测是你已经制作了很多散列表，比这个小得多，因此容器会重新映射数据并导致冲突。

Answer 4

我还编写自定义散列函数（它是一个完美的哈希函数：256^2×R + 256×G + B - 这样的碰撞应尽量少不管桶和哈希表的布局（以合理的。延长）

这个哈希函数并不好。好的哈希函数（当你不知道桶的数量）应该几乎相同的输入产生巨大不同的哈希值。在你的情况下，实现此目的的一个非常简单的方法是使用三个包含256个随机32位值的表：int32_t rand[3][256] - 然后hash ala rand[0][R]^rand[1][G]^rand[2][B]。这会随机地在整个存储桶中分散您的值，而无需为s imilar值：未知＃桶的理想哈希函数属性。

你也可以让库提供的哈希函数有一个破解它，他们不可能改善散列生成的随机表属性，但可能由于更少的内存查找或更慢，由于更多或更复杂的数学运算 - 如果你在乎的基准。

Answer 5

即使您的值可能不相等，值也可能足够接近。我试图为时间序列或未散布的数字找到好的散列函数，这段时间我很困难。当unordered_map以散列值的数量对散列值执行'％'（模）时，大多数值可能仅以最少的散列块结束（如果散列值分散不当），并导致O（n）搜索。

当散列值不够分散时，我会使用std :: map（RB树），我得到O（log n）。