用户自定义哈希函数用于无序映射

Question

我为unordered_map定义了自己的哈希函数。但是使用find函数无法在容器中进行搜索。我尝试通过在哈希函数内部使用打印语句进行调试，它生成了插入键/值时生成的相同哈希值。如果有人能指出错误，那就太好了。我在Windows上使用Eclipse IDE，并使用-std=c++11进行编译。

typedef struct tree node;

struct tree
{
int id;
node *left;
node *right;
};

class OwnHash
{
public:
    std::size_t operator() (const node *c) const
    {
       cout << "Inside_OwnHash: " <<std::hash<int>()(c->id) + std::hash<node *>()(c->left) + std::hash<node *>()(c->right) << endl;
       return std::hash<int>()(c->id) + std::hash<node *>()(c->left) + std::hash<node *>()(c->right);
    }
};

int main()
{
std::unordered_map<node *,node *,OwnHash> ut;

node * one = new node;
one->id = -1;
one->left = nullptr;
one->right = nullptr;
ut.insert({one,one});

node * zero = new node;
zero->id = 0;
zero->left = NULL;
zero->right = NULL;
ut.insert({zero,zero});

node * cur = new node;
cur->id = 5;
cur->left = zero;
cur->right = one;
ut.insert({cur,cur});

for (auto& elem : ut)
{
    std::cout << "key: " << elem.first << "\t" << "value: " << elem.second->id << std::endl;
}

node * parse = new node;
parse->id = 5;
parse->left = zero;
parse->right = one;

std::unordered_map<node *,node *>::const_iterator got1 = ut.find (parse);

if ( got1 == ut.end() )
    std::cout << "not found";
else
    std::cout << got1->first << " is " << got1->second->id << std::endl;

return EXIT_SUCCESS;
}

    Output:
    Inside_OwnHash: 4294967295
    Inside_OwnHash: 0
    Inside_OwnHash: 22946517
    key: 0xaf11b0   value: 5
    key: 0xaf1180   value: 0
    key: 0xaf1150   value: -1
    Inside_OwnHash: 22946517
    not found

- rjk

---

除非是为了教育/学习目的...只是一个问题：你是第一千个问关于在调试模式下std c++容器的速度和效率的人吗？你可能有充分的理由重写哈希表，这没问题。只是一个反射性的问题。 - Stephane Rolland

如果可以的话，我会使用内置的哈希函数。但是出于特定原因，我需要定义自己的哈希函数。我正在使用它来构建二叉决策图。我发布的代码只是为了模拟我需要的情境。 - rjk

@StephaneRolland 这段代码使用了与标准哈希函数不同的语义 - 它基于指针所指向的对象内容进行哈希。这是自定义哈希的一个非常合理的原因。我在问题中没有看到任何关于 std 效率的担忧。 - Angew is no longer proud of SO

Answer 1

仅使用哈希是不够的，你还需要实现等值比较！

哈希函数必须是这样的一个函数：如果项目相等，则它们的哈希值也相等。但是，由于项目可能是任意复杂的，而哈希结果只是 size_t，所以相反的蕴含关系并不能成立。因此，要找到确切的元素，你需要进行等值比较。

在查找时，哈希函数将其指向正确的“桶”，但其中可能有多个元素，或者可能存在一个元素，但不是你要查找的那个元素。因此，它会获取桶中的所有元素，并将每个元素与你正在搜索的元素进行比较。

现在你提供了哈希函数，但没有提供等值比较器。因此，它使用默认值，即 operator==，对于指针，它被定义为比较地址。而这些地址是不相等的。你需要提供一个等值函数对象来比较值。

- Jan Hudec

---

太好了。非常感谢。这很有道理，而且也成功了。 - rjk