总阅读量:次

⭐⭐⭐ Spring Boot 项目实战 ⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 juejin.cn/post/7270916734138908672 「6r0wn_Jay」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注微信公众号：【芋道源码】有福利：

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
  4. 新的源码解析文章实时收到通知。每周更新一篇左右。
  5. 认真的源码交流微信群。

背景

不知道大家是否思考过一个问题，在一些场景下（如大家在使用高德地图打车的时候，邻近的司机是如何知道你在他的附近并将你的打车通知推送给他去接单的？）是如何实现的？

一般来讲，大家也许会想到，首先肯定需要知道每位乘客的经纬度(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都远。这其实是一个边缘性的问题……..后续我会更新如何去避免这种问题的出现

文章目录
  1. 1. 背景
  2. 2. GeoHash基本原理介绍
  3. 3. GeoHash如何应用到这个问题当中？
  4. 4. 遗留问题