C++：无序容器如何防止重复？
C++: How do unordered containers prevent duplications?
我们以unordered_set为例。
判断两个元素是否相等的默认谓词是std::equal_to<T>(t1,t2)，
这就是 t1==t2。
现在让我们假设对于这个 T 类型我已经实现了 operator==() 这样并不是所有的成员变量都是这个比较的一部分，即两个不同的 T 元素 t1,t2 在比较时可以相等。
如果底层哈希表为每个 t1 和 t2 计算不同的哈希，它什么时候执行 t1==t2 检查键的重复？如果有更多的检查，它如何平均保持恒定时间？
If the underlying hashtable calculates a different hash for each of these t1 and t2, when does it even perform the t1==t2 check for duplication of keys?
当哈希函数导致新插入的元素被放入非空桶中时。将在该存储桶中预先存在的元素之间进行比较以确保唯一性。
how does it stay constant-time on average?
通过假设哈希函数将随机键均匀分布到桶中，并随着元素数量的增加而增加桶的数量。
how could std::hash know how i implement openrator==()
为您的 class 编写 std::hash 专业化的人必须知道您如何实现运算符==。
散列函数必须为比较相等的所有元素生成相同的散列。如果没有，那么程序的行为将是未定义的。标准参考：[unord.req], [defns.required.behavior]
我认为您遗漏的关键点是您为无序容器提供了两个仿函数，并且它们必须协同工作。
有哈希函数，它从一个对象计算出一个数字。
有一个比较函数，比较两个对象是否“等价”。
正如@Eljay在他的评论中所说，对于比较“等价”的两个对象（比较函数returns true），散列函数必须 return相同的值。
如果您的功能不提供此保证，则容器将无法正常工作。
比较好的参考（虽然不权威）
std::unordered_set: Meets the requirements of UnorderedAssociativeContainer.
UnorderedAssociativeContainer: are parameterized by Key/Hash/Pred.
With the requriement:
* If two Keys are equal according to Pred.
* Hash must return the same value for both keys.
无序关联容器要求任何两个比较相等的键也具有相同的散列。来自 [unord.req]:
The container's object of type Hash — denoted by hash — is called the hash function of the container. The container's object of type Pred — denoted by pred — is called the key equality predicate of the container.
Two values k1 and k2 are considered equivalent if the container's key equality predicate pred(k1, k2) is valid and returns true when passed those values. If k1 and k2 are equivalent, the container's hash function shall return the same value for both.
您的 operator== 和 std::hash 实现必须一致。如果不是，那么您还没有满足使用 class 作为无序关联容器中的键所需的先决条件。
我们以unordered_set为例。
判断两个元素是否相等的默认谓词是std::equal_to<T>(t1,t2)，
这就是 t1==t2。
现在让我们假设对于这个 T 类型我已经实现了 operator==() 这样并不是所有的成员变量都是这个比较的一部分，即两个不同的 T 元素 t1,t2 在比较时可以相等。
如果底层哈希表为每个 t1 和 t2 计算不同的哈希，它什么时候执行 t1==t2 检查键的重复？如果有更多的检查，它如何平均保持恒定时间？
If the underlying hashtable calculates a different hash for each of these t1 and t2, when does it even perform the t1==t2 check for duplication of keys?
当哈希函数导致新插入的元素被放入非空桶中时。将在该存储桶中预先存在的元素之间进行比较以确保唯一性。
how does it stay constant-time on average?
通过假设哈希函数将随机键均匀分布到桶中，并随着元素数量的增加而增加桶的数量。
how could std::hash know how i implement openrator==()
为您的 class 编写 std::hash 专业化的人必须知道您如何实现运算符==。
散列函数必须为比较相等的所有元素生成相同的散列。如果没有，那么程序的行为将是未定义的。标准参考：[unord.req], [defns.required.behavior]
我认为您遗漏的关键点是您为无序容器提供了两个仿函数，并且它们必须协同工作。
有哈希函数，它从一个对象计算出一个数字。
有一个比较函数，比较两个对象是否“等价”。
正如@Eljay在他的评论中所说，对于比较“等价”的两个对象（比较函数returns true），散列函数必须 return相同的值。
如果您的功能不提供此保证，则容器将无法正常工作。
比较好的参考（虽然不权威）
std::unordered_set: Meets the requirements of UnorderedAssociativeContainer.
UnorderedAssociativeContainer: are parameterized by Key/Hash/Pred.
With the requriement:
* If two Keys are equal according to Pred.
* Hash must return the same value for both keys.
无序关联容器要求任何两个比较相等的键也具有相同的散列。来自 [unord.req]:
The container's object of type
Hash— denoted byhash— is called the hash function of the container. The container's object of typePred— denoted bypred— is called the key equality predicate of the container.Two values
k1andk2are considered equivalent if the container's key equality predicatepred(k1, k2)is valid and returnstruewhen passed those values. Ifk1andk2are equivalent, the container's hash function shall return the same value for both.
您的 operator== 和 std::hash 实现必须一致。如果不是，那么您还没有满足使用 class 作为无序关联容器中的键所需的先决条件。