在我看来,
这就是 unordered_set 插入的工作原理。
调用 insert 时,会调用哈希函数。
在下面的代码中,我分别对
first
和 second
值进行哈希处理。Test(make_pair("good","james"))
(制作测试对象)->
return hasher(test.get_name().first) + hasher(test.get_name().second)
(哈希函数返回)->
8838398861423961495
(哈希值)
这是我的代码
#include <vector>
#include <string>
#include <iostream>
#include <unordered_set>
using namespace std;
class Test
{
public:
Test(pair<string, string> n):name(n){};
pair<string,string> get_name() const { return name; };
bool operator==(const Test &test) const
{
cout << "compare " << get_name().first << ',' << get_name().second << ':' << test.get_name().first << ',' << test.get_name().second << '\n';
return (name == test.get_name());
}
private:
pair<string,string> name;
};
namespace std
{
template<>
struct hash<Test>
{
hash<string> hasher;
size_t operator() (const Test& test) const noexcept
{
cout << test.get_name().first << ',' << test.get_name().second << ':' << (hasher(test.get_name().first) + hasher(test.get_name().second)) << '\n';
return hasher(test.get_name().first) + hasher(test.get_name().second);
}
};
}
int main()
{
unordered_set<Test> hash_set;
hash_set.insert(Test(make_pair("song","james")));
hash_set.insert(Test(make_pair("kim","james")));
hash_set.insert(Test(make_pair("kim","james")));
cout << hash_set.size() << '\n';
return 0;
}
它尝试在 hash_set 中插入三个 Test 对象。第一个和第二个不应具有相同的哈希值(但有可能发生)
每当它被调用时我都会制作
operator==
cout
来查看它何时被调用。还有
hash
功能。这就是结果。
song,james:1897374899324052084
kim,james:6658567258605789090
compare song,james:kim,james
kim,james:6658567258605789090
compare kim,james:kim,james
2
如何比较 (song, james) 和 (kim, james)(通过调用 ==
)即使它们不在同一个存储桶中(哈希值不同)?而且,如果我将“歌曲”更改为“好”,它会改变结果。
(我使用 Apple clang 版本 14.0.3 (clang-1403.0.22.14.1) 和 std=c++14 )
或者换句话说,
std::unordered_set
实现会将自己的散列应用于您的散列之上的较小范围(尽管这可能非常微不足道,例如获取散列的最低位)。哈希的重点是将可能的输入值的数量减少到一个小范围,希望是均匀分布的。因此,即使你的哈希函数计算出的哈希值不同,它们仍然可能被放入同一个桶中,然后由实现决定是否立即使用
==
来比较属于同一桶的元素,或者是否会首先尝试您的哈希函数的输出进行比较。更一般地说,原则上没有什么禁止实现进行不必要的比较
==
,尽管这当然不利于实现的质量。