此方法是否不适合在 std::unordered_map 中使用 2D 坐标作为键



我需要将 2D 坐标作为键存储在 std::unordered_map 中。我知道坐标的每个组成部分不会超过 16 位。

将坐标对 (x,y( 合并到这样的uint32_t是不是一种不好的做法

uint32_t coordinate_id = (x << 16) | y;

并使用coordinate_id作为地图的"哈希"?还是我应该使用专用的哈希函数来计算密钥?如果我没有错过任何东西,上面提供的方法不会导致任何冲突。

你的方法肯定会奏效。如果组件可以超过 16 位,它甚至可以工作:允许哈希发生冲突。

这里的问题是,您的哈希并不比整数的恒等函数更好。对点坐标的更改将导致易于预测的哈希更改。如果点坐标遵循某种定律,则很容易意外地遇到该定律与桶选择算法之间的相关性。
想象一下,如果unordered_map创建了 100 个存储桶,并根据哈希的最后两位数字将项目放入存储桶中。并且您有 y 坐标可被 100 整除的点。你所有的桥都会去同一个桶,违背哈希表的目的!

最新更新