微信，美团等应用都有查找附近的人或者地点，在我们自己应用开发过程，我们一般是存储地点的经纬度到数据库，然后通过画矩形的方式来确定经度和纬度的上下限，再通过数据库查询指定的数据集。这里介绍一种比较新颖的方式。利用奇偶哈希来存储地理信息。
先假设一个256*256的二维坐标系
给定点A(30, 20)，我们不采用直接横纵坐标来表示，而是用一个8位的二进制数字来表示
1. 横坐标：
30在0～127之间，那么第一位为 0
30在0～63之间，那么第二位为 0
30在0～31之间，那么第三位为 0
30在16～31之间，那么第四位位 1
30在24～31之间，那么第五位为 1
30在28～31之间，那么第六位为 1
30在30～31之间，那么第七位为 1
30在30～30.5之间，那么第八位为 0
从上往下，那么点A的横坐标表示为
2. 纵坐标:
20在0～127之间，那么第一位为 0
20在0～63之间，那么第二位为 0
20在0～31之间，那么第三位为 0
20在16～31之间，那么第四位为 1
20在16～23之间，那么第五位为 0
20在20～23之间，那么第六位为 1
20在20～21之间，那么第七位为 0
20在20～20.5之间，那么第八位为 0
从上往下排列，那么点A的横坐标表示为
将 x 和 y 交替合成新的16位二进制：
00 00 00 11 10 11 10 00
然后这个0000 0011 1011 1000就能表示点A的位置了，
假设点B的表示为 1000 1000 0011 0000
假设点C的表示为 0000 0011 1011 0000
那么B，C与A的距离哪个点更近？
当然是点C，因为A和C相同的前缀更多，所有我们要找A的附近的点，只有约定好相同前缀的个数就可以了，个数越多表示距离越近。
这个方式应该叫奇偶哈希法。
3. 扩展
如果用这种方式来表示地理位置的经纬度信息，会出现一个问题，因为地球是圆的，西经180和东经180是同一个经度。比如设置东经为正数，西经为负数，那么
假设 点A和点B的纬度相同
点A为东经170为 +170， 点B西经为 -170，
如果用上述方式来表示，那么AB的距离是比较远的，但实际上AB的距离很近。
怎么解决这个问题呢？
我想了一个比较简单的方式来处理：
如果以本初子午线为0，东经为正，西经为负来计算，那么AB距离为m；
如果以东(西)经180为0，东经为180-东经数，西经为 180 - 西经数 来计算，那么AB的距离为n
实际上来说，m和n必然有一个是正确的表示形式，并且小的那个数一定是正确的。
所以，我们以两种相反的规则来定义我们的奇偶哈希值，每次取小的那个数为最终值即可。
网友评论