是否存在将同区间点映射为同哈希值的函数以实现O(1)区间识别

你需要的这类将同一分区内的点映射为唯一相同哈希值的函数是存在的，一维到高维场景都有成熟的实现方案，以下是具体说明：

你要求的「当且仅当两个点属于同一子区间时哈希值相等」的函数，本质是区间分桶的完美哈希，根据分桶规则不同有两种O(1)实现：

• 等宽分桶场景：直接通过算术运算计算桶号即可，比如所有子区间宽度固定为w，区间左端点为min_val，哈希函数可以写为h(x) = floor((x - min_val) / w)，计算完全是O(1)复杂度，不会产生碰撞。
• 非等宽分桶场景：就是你举例的[1,2)、[2,4)、[4,5]这类宽度不一致的分区，可以提前把所有区间的断点存储为有序数组，给每个区间分配唯一的固定哈希值，运行时如果数值范围较小，直接提前构建全量查询表，输入x直接查表得到哈希值，纯O(1)；如果数值范围较大，用插值查找匹配断点（有序数组+固定数值范围下插值查找的平均时间复杂度为O(1)），也能达到近似O(1)的效率。

针对二维及以上的轴对齐矩形分区场景，你期望的两种复杂度方案都可以实现：

• O(d)复杂度方案（d为维度数）：每个维度单独调用一维区间哈希得到该维度的桶编号，再把所有维度的桶号做无碰撞组合即可。比如二维场景下y维度总共有k个分区，组合哈希可以写为h(x,y) = h_x(x) * k + h_y(y)，只要k大于y维度的最大桶号，就完全不会出现碰撞，两个点同属一个二维分区当且仅当哈希值相等，整体时间复杂度就是O(d)，完全符合你提到的N维场景O(N)运算的要求。
• O(1)复杂度多元哈希：如果分区规则固定、维度和各维度的分区数量有限，可以提前构建完美哈希映射表，把所有可能的维度桶号组合直接映射到唯一的哈希值；如果各维度的数值范围可控，还可以直接把高维坐标编码为单个整数作为预查询数组的索引，查询时直接取值即可达到纯O(1)的效率。如果是非轴对齐的任意多边形分区，无碰撞的O(1)哈希需要提前做空间分区的预映射，仅适用静态分区场景。

内容的提问来源于stack exchange，提问作者user14904283