c++ - unordered_map 插入爬行停止

Question

基本上，我有一个 unordered_map 并试图向其中添加成对的集合……大约有 500,000 个。我注意到，当我添加对时，插入速度变得越来越慢，直到它最终完全停止。关于为什么会这样或如何解决这个问题有什么想法吗？

map 定义:

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 对……刚刚进行了测试……

编辑2:

卡住前的示例输出，其中 count 是映射中的条目数。我相信它正在尝试重新散列 map ，但不确定为什么它没有这样做并卡住了计算机:

检查粒子: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;
    }
  };
}