geohash算法的学习笔记

最近公司项目在探究怎么找到附近的用户这个功能

说到了redis里面新增了空间索引，能够不计算在某个范围内最近的点这种问题

底层是用geohash算法实现的，所以就顺着去学习了下geohash算法的原理

总而言之，geohash是一种把距离变成前缀的算法

 

图片来自 https://blog.****.net/universe_ant/article/details/74785989

首先把地图看出一个正方形，然后切一刀变成左右，左边-180，右边180，左边用0表示，右边用1表示，地球是球型，所以左右加起来是一圈360，其实就是经度；然后再切一刀切出上下，上90，下-90，其实就是纬度；上边用1表示，下边用0表示。这样我们就可以得到一个十字型图，如上图左，然后每个小方格再循环切一次，就变成上图右（切的次数越多，精度越准，比如同在一个大格表示相距在2km之内，同在一个小格表示相距在2m之内），通过这样把二维的空间映射到一维上去，你会发现找距离近的就变成找前缀相同的。

比如我有一个点在1001，如果发现1001这个格子里面有一个点，那么这个点就是离1001最近的。但是可能会出现一种情况，就是边界问题，有两个点属于不同格子，挨得很近，另外两个点属于同个格子，离得很远，这个时候，如果还是选同个格子的，就可能会出错，因为隔壁格子那个挨得更近，为了解决这种问题，就是在找的时候，把周围八个格子里面的点都访问一遍，然后返回。

 

geohash跟之前研究的kd树的解决问题差不多但是有差异

geohash解决的是在给定的范围内（比如1km）最近的点

而kd数解决的是最近的点（没有范围）

但是两者都比线性搜索性能要好，原理都是通过树这种结构，减少了遍历的分支，大大降低了遍历的时间。

有时间的话可以自己实现一下geohash的代码，加深理解 //TODO