背景 GeoHash基本原理介绍 GeoHash如何应用到这个问题当中？ 遗留问题
背景
不知道大家是否思考过一个问题，在一些场景下（如大家在使用高德地图打车的时候，邻近的司机是如何知道你在他的附近并将你的打车通知推送给他去接单的？）是如何实现的？
一般来讲，大家也许会想到，首先肯定需要知道每位乘客的经纬度(lng,lat)，也即是二维坐标（当然这是在绝对理想的情况，不考虑上下坡度）。
而在知道了经纬度之后，一个暴力简单且容易想到的思路就是将经纬度这个「二元组」 都存放在一个「数组」 当中，然后当我们需要拿到离我们规定范围内的用户（如获取当前位置方圆百米内正在打车的乘客），我们就可以去遍历维护的那个数组，以此去判断数组中的经纬度与自己所在经纬度的距离，然后判断是否在范围内。
显然这种方法一定是能够达到目的的，但是值得注意的点是，维护的数据量一般来讲是海量的,因此如果每次都需要遍历所有数据去进行计算，那这计算量以及存储量目前是无法满足的。那如何在此基础上去优化性能呢？？那么这个内容就是本篇文章主要想探讨的问题......
GeoHash基本原理介绍
首先我想先介绍一下GeoHash这种算法「基本原理」 ，再讨论如何进行应用。
对于每一个坐标都有它的经纬度(lng,lat) ，而GeoHash的原理就是将经纬度先通过一个二分的思路拿到一个二进制数组的字符串，然后再通过base32编码去进行压缩存储。
举一个例子，比如经纬度为（116.3111126，40.085003），对其进行二分步骤如下：
经度步骤：
| bit | left | mid | right |
|---|---|---|---|
| 1 | -180 | 0 | 180 |
| 1 | 0 | 90 | 180 |
| 0 | 90 | 135 | 180 |
| 1 | 90 | 112.5 | 135 |
| 0 | 112.5 | 123.75 | 135 |
| 0 | 112.5 | 118.125 | 123.75 |
| 1 | 112.5 | 115.3125 | 118.125 |
| 0 | 115.3125 | 116.71875 | 118.125 |
| 1 | 115.3125 | 116.015625 | 116.71875 |
| 0 | 116.015625 | 116.3671875 | 116.71875 |
| 1 | 116.015625 | 116.19140625 | 116.3671875 |
| 1 | 116.19140625 | 116.279296875 | 116.3671875 |
| 0 | 116.279296875 | 116.323242188 | 116.3671875 |
| 1 | 116.279296875 | 116.301269532 | 116.323242188 |
| 0 | 116.301269532 | 116.31225586 | 116.323242188 |
纬度步骤：
| bit | left | mid | right |
|---|---|---|---|
| 1 | -90 | 0 | 90 |
| 0 | 0 | 45 | 90 |
| 1 | 0 | 22.5 | 45 |
| 1 | 22.5 | 33.75 | 45 |
| 1 | 33.75 | 39.375 | 45 |
| 0 | 39.375 | 42.1876 | 45 |
| 0 | 39.375 | 40.78125 | 42.1876 |
| 1 | 39.375 | 40.078125 | 40.78125 |
| 0 | 40.078125 | 40.4296875 | 40.78125 |
| 0 | 40.078125 | 40.25390625 | 40.4296875 |
| 0 | 40.078125 | 40.166015625 | 40.25390625 |
| 0 | 40.078125 | 40.1220703125 | 40.166015625 |
| 0 | 40.078125 | 40.1000976563 | 40.1220703125 |
| 0 | 40.078125 | 40.0891113282 | 40.1000976563 |
| 1 | 40.078125 | 40.0836181641 | 40.0891113282 |
「其思路就是不断二分，如果原本值大于mid那本bit位就是1，以此往下递归，最终，我们递归二分得到纬度方向上的二进制字符串为 101110010000001，长度为 15 位」
那此时就拿到了30bit位的字符串，然后就开始进行拼接
结合经度字符串 110100101011010 和纬度字符串 101110010000001，我们遵循先经度后纬度的顺序，逐一交错排列，最终得到的一维字符串为 11100 11101 00100 11000 10100 01001.
然后再进行Base32编码，主要步骤就是首先会维护一个「0-9A-Za-z」 中32个字符的数组，如：['a','b','1','2','3','4','5','6','7','A'...]，然后再将这30位的字符串每五个一组（正好覆盖0-31的索引)去索引到指定字符以此拿到30/5=6位的base32编码去进行存储。
「ps:注意并不一定是必要将经纬度都二分得到15位长度，多少位都可以，只是精度越高结果也就越精确，但是算力就越大，只需在此做出权衡即可」
GeoHash如何应用到这个问题当中？
上面讲到了可以通过GeoHash将经纬度转换成bit位的字符串，那么怎么进行应用呢，其实答案很明显，其实如果经纬度越接近，他们的前缀匹配位数也就越长，比如
通过这个思路我们就比较容易得到我们想要的范围内的乘客了。
遗留问题
但是其实仅仅如此是不够的，因为一个base32其实是覆盖了一片区域的，它并不是说仅仅代表一个精确的ip地址，那这其实就衍生出了一些问题，就比如
用geohash那结果显然是AB更近，但是实际上A与B的距离比AE、AC、AD都远。这其实是一个边缘性的问题........后续我会更新如何去避免这种问题的出现
如喜欢本文，请点击右上角，把文章分享到朋友圈
因公众号更改推送规则，请点“在看”并加“星标”第一时间获取精彩技术分享
·END·
作者：6r0wn_Jay
来源：https://juejin.cn/post/7270916734138908672
我的Java踩坑专栏已经更新89篇啦，篇篇经典，都是我晚上下班和周末总结的代码踩坑点，花了很多心血，很实用的。后面会有200+篇，49.9永久买断~扫码加入即可（当前我切到新语啦，之前在小报童买过的伙伴，不用重复购买哈）
优网科技秉承"专业团队、品质服务" 的经营理念，诚信务实的服务了近万家客户，成为众多世界500强、集团和上市公司的长期合作伙伴！
优网科技成立于2001年，擅长网站建设、网站与各类业务系统深度整合，致力于提供完善的企业互联网解决方案。优网科技提供PC端网站建设（品牌展示型、官方门户型、营销商务型、电子商务型、信息门户型、DIY体验、720全景展厅及3D虚拟仿真）、移动端应用（手机站、APP开发）、微信定制开发（微信官网、微信商城、企业微信）、微信小程序定制开发等一系列互联网应用服务。
公安局备案号：
专属顾问
