滴滴打车如何找出方圆一千米内的乘客？揭开 GeoHash 的神秘面纱

👉 这是一个或许对你有用 的社群

🐱 一对一交流/面试小册/简历优化/求职解惑，欢迎加入 「 芋道快速开发平台 」 知识星球。 下面是星球提供的部分资料：

• 《项目实战（视频）》 ：从书中学，往事中 “练 ”
• 《互联网高频面试题》 ：面朝简历学习，春暖花开
• 《架构 x 系统设计》 ：摧枯拉朽，掌控面试高频场景题
• 《精进 Java 学习指南》 ：系统学习，互联网主流技术栈
• 《必读 Java 源码专栏》 ：知其然，知其所以然

• 背景
• GeoHash基本原理介绍
• GeoHash如何应用到这个问题当中？
• 遗留问题

背景

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

一般来讲，大家也许会想到，首先肯定需要知道每位乘客的经纬度(lng,lat)，也即是二维坐标（当然这是在绝对理想的情况，不考虑上下坡度）。

而在知道了经纬度之后，一个暴力简单且容易想到的思路就是将经纬度这个 「二元组」 都存放在一个 「数组」 当中，然后当我们需要拿到离我们规定范围内的用户（如获取当前位置方圆百米内正在打车的乘客），我们就可以去遍历维护的那个数组，以此去判断数组中的经纬度与自己所在经纬度的距离，然后判断是否在范围内。

显然这种方法一定是能够达到目的的， 但是值得注意的点是，维护的数据量一般来讲是海量的 ,因此如果每次都需要遍历所有数据去进行计算，那这计算量以及存储量目前是无法满足的。那如何在此基础上去优化性能呢？？那么这个内容就是本篇文章主要想探讨的问题......

基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能

• 项目地址：https://github.com/YunaiV/ruoyi-vue-pro
• 视频教程：https://doc.iocoder.cn/video/

GeoHash基本原理介绍

首先我想先介绍一下GeoHash这种算法 「基本原理」 ，再讨论如何进行应用。

对于每一个坐标都有它的 经纬度(lng,lat) ，而GeoHash的原理就是将经纬度先通过一个 二分 的思路拿到一个 二进制数组 的字符串，然后再通过 base32编码 去进行压缩存储。

举一个例子，比如经纬度为（116.3111126，40.085003），对其进行二分步骤如下：

经度步骤：

纬度步骤：

「其思路就是不断二分，如果原本值大于mid那本bit位就是1，以此往下递归，最终，我们递归二分得到纬度方向上的二进制字符串为 101110010000001，长度为 15 位」

那此时就拿到了30bit位的字符串，然后就开始进行拼接

结合经度字符串 110100101011010 和纬度字符串 101110010000001 ，我们遵循先经度后纬度的顺序，逐一交错排列，最终得到的一维字符串为 11100 11101 00100 11000 10100 01001 .