为什么我的所有项目都转到 unordered_map 存储桶 0？

Question

这是我对哈希图的分析的日志（截断）：

unsigned nbuckets = octree->Nodes.bucket_count();

LOG(Error, "bucket size = {0}, kk = {1}", nbuckets, octree->Nodes.max_load_factor());

for (auto& x : octree->Nodes) {
   LOG(Warning, "Element [{0}:{1}] is in bucket {2}", x.first.morton, x.second.position, octree->Nodes.bucket(x.first));
}

[ 00:19:26.169 ]: [Error] bucket size = 512, kk = 1.0
[ 00:19:26.169 ]: [Warning] Element [132120576:X:384 Y:384 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [115343360:X:128 Y:384 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [98566144:X:384 Y:128 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [81788928:X:128 Y:128 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [65011712:X:384 Y:384 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [48234496:X:128 Y:384 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [31457280:X:384 Y:128 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [16515072:X:192 Y:192 Z:192] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [14417920:X:64 Y:192 Z:192] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [12320768:X:192 Y:64 Z:192] is in bucket 
....

地图定义如下：

[ 00:19:26.169 ]: [Error] bucket size = 512, kk = 1.0
[ 00:19:26.169 ]: [Warning] Element [132120576:X:384 Y:384 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [115343360:X:128 Y:384 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [98566144:X:384 Y:128 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [81788928:X:128 Y:128 Z:384] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [65011712:X:384 Y:384 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [48234496:X:128 Y:384 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [31457280:X:384 Y:128 Z:128] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [16515072:X:192 Y:192 Z:192] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [14417920:X:64 Y:192 Z:192] is in bucket 0
[ 00:19:26.169 ]: [Warning] Element [12320768:X:192 Y:64 Z:192] is in bucket 
....

其中 OctreeNode 是一个具有一些值的结构。和 Int3Pos：

std::unordered_map<Int3Pos, OctreeNode, Int3Pos::HashFunction> Nodes;

它告诉 512 个存储桶，但全部变为 0。或者我误解了某些内容？

Answer 1

你的哈希函数非常糟糕。您显示的莫顿值的最大公约数是

GCD(132120576, 115343360, 98566144, 81788928, 65011712, 48234496, 31457280, 16515072, 14417920, 12320768) = 2^18 = 262144

它被除以 512。所有值都进入（第一个）存储桶 0。

你可以试试

return pos.morton % 511;  // or pos.morton % 1023, or std::hash<decltype(pos.morton)>{}(pos.morton).