为什么第 32769 次插入在 std::unordered_set 中失败？
Why does the 32769th insert fail in std::unordered_set?
我生成了大量 class 个实例并将它们存储在 std::unordered_set 中。我已经定义了一个散列函数和一个相等关系，到目前为止一切正常——我用 unordered_set::insert 插入 10000 个实例，我可以用 unordered_set::find 找到它们。所有对象都完好无损，并且没有内存损坏或任何其他问题的提示。
但是，当我继续插入时，第 32769 次插入失败 - 它不会抛出，但它 returns 一对迭代器是 == nullptr (0x00000000)。 insert 定义为：
pair<iterator, bool> insert(const value_type& Val);
通常，*iterator 是我插入的键，bool 是 true。
如果我（在错误之后）试图找到对象，它 是 在集合中；如果我再次尝试插入它，它会告诉我它已经存在；所以插入似乎工作正常。只是返回值是 pair<nullptr,true> 而不是 pair<iterator,bool>.
请注意，如果我手动填充迭代器并在调试器中继续，同样的问题会再次发生在 65536 之后的第一个插入处，然后是 131072 处，等等（因此对于 2^15+1、2^16+1、2 ^17+1, ...) - 但不在 3 * 32768+1 等
对我来说，这看起来有点 short 溢出。也许我的哈希值真的很糟糕，导致桶填充不均匀，并且在 32768 时它用完了桶？谷歌搜索时我找不到关于这种限制的更详细的信息，而且我对平衡树或内部的任何东西都不太了解。
尽管如此，std 库代码应该能够处理糟糕的散列，我理解它是否变得缓慢和低效，但它不应该 fail.
问题：为什么2^15th+1、2^16th+1等插入失败，如何避免？
这是 Microsoft Visual Studio 2017 V15.7.1（截至 2018-05-15 的最新版本）。编译器设置为使用 C++2017 规则，但我怀疑它会产生任何影响。
我无法粘贴最小可行解决方案的完整代码，因为对象生成在多个 classes 和方法中很复杂，并且有数百行代码，生成的哈希值显然取决于对象的细节，并且在虚拟代码中不容易重现。
### 一天后更新###：（我不能把这个放在答案里，因为q被搁置了）
在对标准库进行了大量调试（包括很多令人头疼的事情）之后，@JamesPoag 的回答证明指向了正确的事情。
n 插入后，我得到：
n load_factor max_load_factor bucket_count max_bucket_count
32766 0.999938965 1.00000000 32768 536870911 (=2^29-1)
32767 0.999969482 1.00000000 32768 536870911
32768 1.000000000 1.00000000 32768 536870911
32769 0.500000000 1.00000000 65536 536870911
不出意外，插入32768次后，负载因子已经达到了最大值。在内部方法 _Check_Size:
中，第 32769 次插入触发了对更大 table 的重新哈希
void _Check_size()
{ // grow table as needed
if (max_load_factor() < load_factor())
{ // rehash to bigger table
size_type _Newsize = bucket_count();
if (_Newsize < 512)
_Newsize *= 8; // multiply by 8
else if (_Newsize < _Vec.max_size() / 2)
_Newsize *= 2; // multiply safely by 2
_Init(_Newsize);
_Reinsert();
}
}
最后，调用 _Reinsert() 并将所有 32769 个键填充到新的桶中，并相应地设置所有 _next 和 _prev 指针。效果很好。
然而，调用这两个的代码看起来像这样（Plist 是 my 集的名称，此代码是从模板生成的）：
_Insert_bucket(_Plist, _Where, _Bucket);
_TRY_BEGIN
_Check_size();
_CATCH_ALL
erase(_Make_iter(_Plist));
_RERAISE;
_CATCH_END
return (_Pairib(_Make_iter(_Plist), true));
}
关键点在最后一行 - _Plist 用于构建对，但它持有指向 _next 的现已死指针，因为所有存储桶的地址都在 _Check_size() 中重建，一些线较早。
我认为这是 std 库中的一个错误 - 这里它需要在新集合中找到 _Plist，它看起来相同，但有一个有效的 _next 指针。
一个简单的 'fix' 是（已验证有效）在关键 insert:
之前扩展集合
if (mySet.size() == mySet.bucket_count()) mySet.rehash(mySet.bucket_count() * 2);.
### 进一步更新：###
我一直在广泛地（16 个多小时）尝试生成一个 最小代码 来重现该问题，但我还不能。我将尝试记录现有大型代码的实际计算哈希值。
我发现的一件事是，其中一个键的一个散列值 changed （无意中）在插入和重新散列之间。这 可能 是根本原因；如果我将重新散列移到插入之外，问题就消失了。
我不确定是否有哈希必须保持不变的规则，但这可能是有道理的，否则你怎么能再次找到密钥。
我在 godbolt.org 中插入了一些简单的代码以查看输出是什么，但没有任何结果跳出来。
我怀疑插入了Value并创建了迭代器，但是插入超过了max_load_factor并触发了rehash。在 Rehash 上，之前的迭代器都失效了。在这种情况下，return 迭代器可能会被清零（或者永远不会设置）（我再次在反汇编中找不到它）。
检查有问题的插入前后的 load_value()、max_load_value() 和 bucket_count()。
[这是一个自我回答]
正如假设的那样，问题不在标准库中，毕竟它在我的代码中（不足为奇）。事情是这样的：
我正在向 unordered_set 中插入复杂的对象，哈希是根据对象计算的。假设对象 1 具有哈希 H1，对象 2 具有哈希 H2，等等
进一步，我临时修改插入的对象，克隆它，将克隆插入unordered_set，并撤消修改。但是，如果 insert 触发了集合的重组（发生在 2^15、2^16 等处），则会重新计算所有现有对象的哈希值。
由于对象 1 当前是 'temporarily modified'，它的哈希值不会作为 H1 返回，而是不同的。这打乱了集合的内部结构，最终返回了一个无效的迭代器。伪代码：
myMap.insert(Object1); // hash H1 is internally calculated
Object1.DoChange(); // temporary modification
Object2 = Clone(Object1);
myMap.insert(Object2); // <-- problem - rehashes internally and finds different hash H1 for Object1 !
Object1.UndoChange(); // too late, damage done
如果我将重新哈希移动到 插入 之外，或者如果我在关键插入 之前 撤消对象的修改，问题就会消失（所以哈希再次正确）。
还有其他几种方法可以避免此问题（在修改之前克隆，将哈希值保存在对象中并且不重新计算等）。
核心课：哈希计算必须稳定。您不能修改集合或映射中的对象，如果它更改了计算的散列 - 集合或映射可能会在意外的时间点触发重新散列。
我生成了大量 class 个实例并将它们存储在 std::unordered_set 中。我已经定义了一个散列函数和一个相等关系，到目前为止一切正常——我用 unordered_set::insert 插入 10000 个实例，我可以用 unordered_set::find 找到它们。所有对象都完好无损，并且没有内存损坏或任何其他问题的提示。
但是，当我继续插入时，第 32769 次插入失败 - 它不会抛出，但它 returns 一对迭代器是 == nullptr (0x00000000)。 insert 定义为：
pair<iterator, bool> insert(const value_type& Val);
通常，*iterator 是我插入的键，bool 是 true。
如果我（在错误之后）试图找到对象，它 是 在集合中；如果我再次尝试插入它，它会告诉我它已经存在；所以插入似乎工作正常。只是返回值是 pair<nullptr,true> 而不是 pair<iterator,bool>.
请注意，如果我手动填充迭代器并在调试器中继续，同样的问题会再次发生在 65536 之后的第一个插入处，然后是 131072 处，等等（因此对于 2^15+1、2^16+1、2 ^17+1, ...) - 但不在 3 * 32768+1 等
对我来说，这看起来有点 short 溢出。也许我的哈希值真的很糟糕，导致桶填充不均匀，并且在 32768 时它用完了桶？谷歌搜索时我找不到关于这种限制的更详细的信息，而且我对平衡树或内部的任何东西都不太了解。
尽管如此，std 库代码应该能够处理糟糕的散列，我理解它是否变得缓慢和低效，但它不应该 fail.
问题：为什么2^15th+1、2^16th+1等插入失败，如何避免？
这是 Microsoft Visual Studio 2017 V15.7.1（截至 2018-05-15 的最新版本）。编译器设置为使用 C++2017 规则，但我怀疑它会产生任何影响。
我无法粘贴最小可行解决方案的完整代码，因为对象生成在多个 classes 和方法中很复杂，并且有数百行代码，生成的哈希值显然取决于对象的细节，并且在虚拟代码中不容易重现。
### 一天后更新###：（我不能把这个放在答案里，因为q被搁置了）
在对标准库进行了大量调试（包括很多令人头疼的事情）之后，@JamesPoag 的回答证明指向了正确的事情。
n 插入后，我得到：
n load_factor max_load_factor bucket_count max_bucket_count
32766 0.999938965 1.00000000 32768 536870911 (=2^29-1)
32767 0.999969482 1.00000000 32768 536870911
32768 1.000000000 1.00000000 32768 536870911
32769 0.500000000 1.00000000 65536 536870911
不出意外，插入32768次后，负载因子已经达到了最大值。在内部方法 _Check_Size:
中，第 32769 次插入触发了对更大 table 的重新哈希void _Check_size()
{ // grow table as needed
if (max_load_factor() < load_factor())
{ // rehash to bigger table
size_type _Newsize = bucket_count();
if (_Newsize < 512)
_Newsize *= 8; // multiply by 8
else if (_Newsize < _Vec.max_size() / 2)
_Newsize *= 2; // multiply safely by 2
_Init(_Newsize);
_Reinsert();
}
}
最后，调用 _Reinsert() 并将所有 32769 个键填充到新的桶中，并相应地设置所有 _next 和 _prev 指针。效果很好。
然而，调用这两个的代码看起来像这样（Plist 是 my 集的名称，此代码是从模板生成的）：
_Insert_bucket(_Plist, _Where, _Bucket);
_TRY_BEGIN
_Check_size();
_CATCH_ALL
erase(_Make_iter(_Plist));
_RERAISE;
_CATCH_END
return (_Pairib(_Make_iter(_Plist), true));
}
关键点在最后一行 - _Plist 用于构建对，但它持有指向 _next 的现已死指针，因为所有存储桶的地址都在 _Check_size() 中重建，一些线较早。
我认为这是 std 库中的一个错误 - 这里它需要在新集合中找到 _Plist，它看起来相同，但有一个有效的 _next 指针。
一个简单的 'fix' 是（已验证有效）在关键 insert:
之前扩展集合
if (mySet.size() == mySet.bucket_count()) mySet.rehash(mySet.bucket_count() * 2);.
### 进一步更新：###
我一直在广泛地（16 个多小时）尝试生成一个 最小代码 来重现该问题，但我还不能。我将尝试记录现有大型代码的实际计算哈希值。
我发现的一件事是，其中一个键的一个散列值 changed （无意中）在插入和重新散列之间。这 可能 是根本原因；如果我将重新散列移到插入之外，问题就消失了。
我不确定是否有哈希必须保持不变的规则，但这可能是有道理的，否则你怎么能再次找到密钥。
我在 godbolt.org 中插入了一些简单的代码以查看输出是什么，但没有任何结果跳出来。
我怀疑插入了Value并创建了迭代器，但是插入超过了max_load_factor并触发了rehash。在 Rehash 上，之前的迭代器都失效了。在这种情况下，return 迭代器可能会被清零（或者永远不会设置）（我再次在反汇编中找不到它）。
检查有问题的插入前后的 load_value()、max_load_value() 和 bucket_count()。
[这是一个自我回答]
正如假设的那样，问题不在标准库中，毕竟它在我的代码中（不足为奇）。事情是这样的：
我正在向 unordered_set 中插入复杂的对象，哈希是根据对象计算的。假设对象 1 具有哈希 H1，对象 2 具有哈希 H2，等等
进一步，我临时修改插入的对象，克隆它，将克隆插入unordered_set，并撤消修改。但是，如果 insert 触发了集合的重组（发生在 2^15、2^16 等处），则会重新计算所有现有对象的哈希值。
由于对象 1 当前是 'temporarily modified'，它的哈希值不会作为 H1 返回，而是不同的。这打乱了集合的内部结构，最终返回了一个无效的迭代器。伪代码：
myMap.insert(Object1); // hash H1 is internally calculated
Object1.DoChange(); // temporary modification
Object2 = Clone(Object1);
myMap.insert(Object2); // <-- problem - rehashes internally and finds different hash H1 for Object1 !
Object1.UndoChange(); // too late, damage done
如果我将重新哈希移动到 插入 之外，或者如果我在关键插入 之前 撤消对象的修改，问题就会消失（所以哈希再次正确）。
还有其他几种方法可以避免此问题（在修改之前克隆，将哈希值保存在对象中并且不重新计算等）。
核心课：哈希计算必须稳定。您不能修改集合或映射中的对象，如果它更改了计算的散列 - 集合或映射可能会在意外的时间点触发重新散列。