这个空间网格用的哈希函数是什么原理?

Question

要把一堆点分配到一个网格的不同格子里, 为了实现无限大的网格使用哈希表来实现, 找到一篇文章给出了如图的格子哈希函数, 请问选择这个函数的根据是什么呢?

Answer 1

hash算法的目的，就是为了让数据在空间中分布得尽量散开，这样就能保障使用hash时极佳的效果。
普通的hash算法通常只有一个因子，我们假设这个因子a在正常情况下就符合平均分布（也就是取每个值得概率一样），那我们就很容易得到一个良好的hash算法：hash(a) = a mod n。这能理解吧？
而你所阐述的hash算法有三个因子，这也不难，我们只要找到一个分布得又平均，又与能这三个因子扯上关系的数a，构建一个等式a = f(x, y, z)，在把a带入我们刚才的方程hash(a) = a mod n即可。
很多人很容易想到一些简单的算式，比如x + y + z、x * y * z等等，但这并不是我们想要的，因为它们的结果不够平均。就拿x + y + z来说吧，举个简单的例子，我们掷三个骰子（每个因子是平均分布得），取得3、18的概率显然要比取得7、8的概率低多了（结果没有符合平均分布），所以这些简单的算法不能直接采用。
这你所给的式子就利用xor异或来处理，取得的结果要比简单的相加更加平均，这就能让hash算法的结果更优秀。并且这个算法中还引入了p1、p2、p3三个参数，并给出了三个参考值，这三个参数的作用就是让结果更加平均的（有些数字就是这么神奇）。