unordered_map插入陷入停顿

Question

基本上，我有一个unordered_map，并试图向它添加几组对...大约500,000个。我注意到，当我添加对时，插入速度会变得越来越慢，直到最后完全停止。有没有想过为什么会发生这种情况，或者如何解决？

映射定义：

std::tr1::unordered_map<std::pair<int, int>, int, pairHash> x_map ;

哈希函数-请注意，对于我的情况，我不必担心pair.first==pair.second，所以我相信这个哈希函数应该足够了，如果我错了，请纠正我：

class pairHash
        {
        public:
            size_t operator()(const std::pair<int, int> & v) const
            {
                return v.first ^ v.second ;
            }
        } ;

方法将值添加到unordered_map...尝试添加大约200,000-500,000对：

initialize_map( EndPoint**& arr, std::tr1::unordered_map<std::pair<int, int>, int, pairHash> &my_map, int size )
{
    for( int i = 0 ; i < size ; i++ )   // add initial overlapping pairs
    {
        if( i % 100 == 0 )
            std::cout << "checking particle: " << i << " maxsize: " << my_map.max_size() << std::endl ;
        int j = 1 ;
        while( arr[i]->isMin && i+j < size &&    // while ys is a min, and not end of array
              arr[i]->v_id != arr[i+j]->v_id )      // anything between min and max is a possible collision
        {
            if( !arr[i]->isEdge || !arr[i+j]->isEdge )
            {
                my_map[std::make_pair( std::min( arr[i]->v_id, arr[i+j]->v_id ),
                        std::max( arr[i]->v_id, arr[i+j]->v_id ) )] = 1 ;
            }

            j++ ;
        }
    }
}

编辑:我实际上添加了接近50,000,000对...刚做了个测试。

EDIT2：

冻结之前的示例输出，其中count是映射中的条目数。我相信它正在尝试重新散列地图，但不确定为什么它无法做到这一点并冻结了计算机：

检测粒子: 87500计数: 35430415负荷率: 0.988477

检测粒子: 87600计数: 35470808负荷率: 0.989652

检测粒子: 87700计数: 35511049负荷率: 0.990818

检测粒子: 87800计数: 35555974负荷率: 0.992073

检测粒子: 87900计数: 35595646负荷率: 0.993163

检测粒子: 88000计数: 35642165负荷率: 0.994427

检测粒子: 88100计数: 35679608负荷率: 0.995434

检测粒子: 88200计数: 35721223负荷率: 0.996563

检测粒子: 88300计数: 35760313负荷率: 0.997616

检测粒子: 88400计数: 35799621负荷率: 0.9987

检测粒子: 88500计数: 35833445负荷率: 0.999649

Answer 1

为了获得更好的散列函数，最好还是使用Boost hash_combine解决方案：

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash< std::pair<S, T> >
  {
    inline std::size_t operator()(const std::pair<S, T> & v) const
    {
      std::size_t seed = 0;
      hash_combine(seed, v.first);
      hash_combine(seed, v.second);
      return seed;
    }
  };
}

Answer 2

试着看看unordered_map::load_factor()。此调用的结果理想情况下应小于1.0。如果它大于1.0，那么您的散列函数可能是不可靠的。你应该使用hash_combine，而不是对你的对进行异或运算。

Answer 3

您是否尝试过使用reserve()为所有配对预先分配足够的存储桶？添加这么多对可能会触发许多大小调整(和重新散列)。

我要检查的下一件事是你的散列函数。这看起来有点可疑，如果你有很多散列冲突，你可能会得到一堆溢出存储桶，这会减慢每次插入的查找速度-在这种情况下，你最好使用std::map。您可以修改代码以存储每一对的哈希，然后检查您生成的唯一哈希值的数量。