c++ - std::unordered map with custom key 在 ~ 31,000 个元素处失败

Question

我使用自定义键将指向组件类的指针存储在无序映射中。

(有关这样做的动机，请参阅 https://stackoverflow.com/a/56688344/16582)

我可以毫无问题地存储多达 30,000 个组件。当我存储 31,000 个组件时，容器完全无声地失效。

(我首先想到的是有符号的16位整数的最大值，但是在32767处稍大)

我怀疑自定义 key 的散列有问题，因为使用标准 key 不会显示此问题。对于这个可行性测试，我不关心性能，所以我使用了一个非常简单易懂的哈希函数。我尝试了几种不同的哈希函数，但都显示出相同的问题 - 下面的代码是最简单的。

下面的最小完整程序代码对于 30,000 个组件的行为符合预期

Map contains 30000
type 12 found type 12 found total 10, OK

但 31,000 个组件失败

Map contains 31000
type 12 found type 12 found total 0, ERROR! Incorrect component count recovered

代码如下:

#include <iostream>
#include <sstream>
#include <iomanip>
#include <unordered_map>

#define maxScene 10
#define maxLayer 10
#define maxType 100
#define maxID   10000

#define COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE 10

// OK for 30, but fails for 31
#define COUNT_TYPES 31

using namespace std;

class Component
{
public:
    int myID;
    static long long lastID;
    Component()
    {
        myID = ++lastID;
    }
};

long long Component::lastID = -1;

class cKey
{
public:
    size_t scene;
    size_t layer;
    size_t type;
    long long id;

    void Display() const;

};

struct KeyHash
{
public:
    size_t operator()(const cKey & key) const
    {
        std::hash<string> shash;
        stringstream ss;
        ss << setw(3) << key.scene << setw(3)<< key.layer << setw(4) << key.type;
        //key.Display();
        //cout << " " << ss.str() << "\n";
        return shash( ss.str() );
    }
};
struct KeyEqual
{
public:
    bool operator()(const cKey & key1, const cKey & key2) const
    {
        if( key1.scene != key2.scene )
            return false;
        if( key1.layer != key2.layer )
            return false;
        if( key1.type != key2.type )
            return false;
        if( key1.id != key2.id )
            return false;
        return true;
    }
};

void cKey::Display() const
{
    cout << scene <<" "<< layer <<" "<< type <<" "<<id ;
}

int main()
{

    unordered_map< cKey, Component*,
                   KeyHash, KeyEqual  > theMap;

    // store components
    int insertCount = 0;
    cKey key;
    for( key.scene = 0; key.scene < maxScene; key.scene++ )
    {
        for( key.layer = 0; key.layer < maxLayer; key.layer++ )
        {
            // store specified number of types
            for( key.type = 0; key.type < COUNT_TYPES; key.type++ )
            {
                // store specified number of components for this scene, layer and type
                for( int k = 0; k < COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE; k++ )
                {
                    insertCount++;
                    Component* pc = new Component;
                    key.id = pc->myID;

                    auto ret = theMap.insert( make_pair( key, pc ));
                    if( ! ret.second )
                    {
                        cout << "insert failed ";
                        key.Display();
                        return 1;
                    }
                }
            }
        }
    }

    cout << "Map contains " << theMap.size() << "\n";

    // iterate over components of one type in a particular scene and layer
    key.scene = 3;
    key.layer = 2;
    key.type  = 12;
    cout << "type " << key.type << " found ";
    int count = 0;
    for( key.id = 0; key.id < maxID; key.id++ )
    {
        auto it = theMap.find( key );
        if( it == theMap.end() )
            continue;
        count++;
    }
    cout << "type " << key.type << " found total "<< count << ", ";
    if( count != COUNT_COMPS_FOR_EACH_SCENE_LAYER_TYPE )
        cout << "ERROR! Incorrect component count recovered\n";
    else
        cout << "OK";

    return 0;
}

固定生产代码在 https://gist.github.com/JamesBremner/d71b158b32e4dd8ffaf8cbe93cf3f180如果有人想建议更快的散列 ...

Answer 1

如果您将以下内容编写为对元素进行计数的循环

for (key.id = 0; key.id <= Component::lastID; key.id++)
{
    auto it = theMap.find(key);
    if (it == theMap.end())
        continue;
    count++;
}

测试通过。我认为这只是一个跟踪最大可能 ID 的问题。