一文了解geohash原理，实践实战设计思路

前言

Hello，小伙们好，我是阿沐！一个喜欢通过实际项目实践来分享技术点的程序员！

你们有没有遇到被面试官嘲讽的场景；之前有位刚毕业的小学弟在上海魔都某某某大公司面试，二面主要是问了关于redis的相关知识点，回答的也是磕磕绊绊的，其中一个问题是如何实现搜索附近人加好友功能；想跟小伙伴们一起分享、一起探讨下。如果有不正确的地方，欢迎指正批评，共同进步~~~

面试官的主要考点

• 考点一：面试官考点之Geohash是什么 知识存储量，没用过但是不能不知道
• 考点二：面试官考点之原理与算法 考验算法基本功
• 考点三：面试官考点之redis的geohash的基础命令 考察底子
• 考点四：面试官考点之实现想法与方案 考察思维能力
• 考点五：面试官考点之实际项目应用 实战经验

当你看到面试官想考验你这些知识点的时候；你在面试官问的过程中，就脑海在飞快的转动着，组合一系列的数据场景准备应战。

Geohash概念介绍

geohash就是一种地理位置编码。用来查询附近的POI(POI是“Point of Interest”的缩写，中文可以翻译为“兴趣点”。在地理信息系统中，一个POI可以是一栋房子、一个商铺、一个邮筒、一个公交站等)，也是一种算法的思想。

通过将地球看成一个二维的平面图，然后将平面递归切分成更小的模块，然后将空间经纬度数据进行编码生成一个二进制的字符串，再通过base32将其转换为一个字符串。最终是通过比较geohash的值的相似程度查询附近目标元素。

Geohash能实现什么功能？

• 地图导航； 高德地图、百度地图、腾讯地图
• 附近人功能；微信附近人、微信摇一摇、拼夕夕附近人、扣扣附近人

Geohash 算法原理

讲真地，当我要准备讲解原理和算法的时候，也很纠结，毕竟算法不是我的强项且百度一下千篇一律；并且都是大神级人物总结，且不敢妄自菲薄，所以还是站在前人的肩膀上来理解下geohash原理与算法。

“附近的人”也就是常说的 LBS (Location Based Services，基于位置服务)，它围绕用户当前地理位置数据而展开的服务，为用户提供精准的增值服务。

“附近的人” 核心思想如下：

① 以“自己”为中心，搜索附近的用户

② 以“自己”当前的地理位置为准，计算出别人和 “我” 之间的距离

③ 按“自己”与别人距离的远近排序，筛选出离我最近的用户或者商店等

那么我们按照我们以往的操作方式：我们在搜索附近人时，会将整个站点的用户信息塞到一个list中，然后去遍历所有节点，检查哪一个节点在自己的范围内；时间复杂度就变成了n*m(n搜索次数，m用户数据)这谁顶得住啊，就是全部放redis一旦数据量上来也顶不住，搜索效率极低。

附近人

上面大家应该可以看出来吧，其实就是把自己的坐标作为一个中心；哎，然后我们要找到围绕我们方圆10公里以内的附近小伙伴：

X轴：我们可以看做是纬度，左半边范围是-180°~~ 0°；右半边是0° ~~ 180° Y轴：我们可以看做是经度，上半边范围是0° ~~ 90°；下半边是-90° ~~ 0° 原点：我们就看做是(0,0)位置；就好像是我们自己的位置

举例子

假如我们现在地点在广州字节跳动有限公司(广州市天河区珠江东路6号)经纬度是：113.326059(经度),23.117596(纬度)

geohash实质就是将经纬度进行二分法的形式落于相对应的区间中，越分越细一直到趋近于某一个临界值，那么分的层数越多，精确度越准确。

原则是：左区间标注 0；右区间标注 1。

例如我们用代码实现上面经纬度二分法生成的二进制：

代码语言：javascript复制

/**
 * @desc 利用递归思想 找出经纬度的二进制编码
 * @param float $place 经度或纬度
 * @param string $binary_array 每次递归拿到的bit值
 * @param int $max_separate_num递归总次数
 * @param array $section 区间值
 * @param int $num 递归次数
 * @return array
 */
public function binary($place = 0, $binary_array = [], $max_recursion_num = 20, $section = [], $num = 1)
{
    if (!$section) return $binary_array;

    // 获取中间值
    $count = ($section['max'] - $section['min']) / 2;

    // 左半边区间
    $left = [
        'min' => $section['min'],
        'max' => $section['min']   $count
    ];

    // 右半边区间
    $right = [
        'min' => $section['min']   $count,
        'max' => $section['max']
    ];

    // 假如给点的经纬度值大于右边最小值 则属于右半边区间为1 否则就是左半边区间 0
    array_push($binary_array, $place > $right['min'] ? 1 : 0);

    // 如果递归次数已经达到最大值 则直接返回结果集
    if ($max_recursion_num <= $num) return $binary_array;

    // 下一次递归我们需要传入的经纬度 区间值
    $section = $place > $right['min'] ? $right : $left;

    // 继续针对自身做的递归处理  一直到出现结果
    return $this->binary($place, $binary_array, $max_recursion_num, $section, $num   1);
}

// 实例化调用该方法
require_once './Geohash.php';

$geohash = new Geohash();

echo  json_encode($geohash->binary(23.117596,[],$geohash->baseLengthGetNums(4, 1), $geohash->interval[0],1));

//结果集
[1,0,1,0,0,0,0,0,1,1]-> 二进制 101000 00011 这样是不是很清晰

//再看不明白的话  那么久打印出范围值：
[{"min":-90,"max":90},{"min":0,"max":90},{"min":0,"max":45},{"min":22.5,"max":45},{"min":22.5,"max":33.75},{"min":22.5,"max":28.125},{"min":22.5,"max":25.3125},{"min":22.5,"max":23.90625},{"min":22.5,"max":23.203125},{"min":22.8515625,"max":23.203125}]

从上面的脚本实现来看是不是更清晰了呢？那么我在使用lua语言给大家实现展示一下，本身原理基本一致：

代码语言：javascript复制

local cjson = require("cjson")

-- 定义经纬度区间范围
local interval = {
    { min = -90,  max = 90 },
    { min = -180, max = 180 }
}

--- @desc 利用递归思想 找出经纬度的二进制编码
--- @param place string 经度或纬度
--- @param binary_array table 每次递归拿到的bit值
--- @param max_separate_num number 递归总次数
--- @param section table 区间值
--- @param num number 递归次数
function binary(place, binary_array, max_recursion_num, section, num)
    -- body
    place        = tonumber(place) or 0
    binary_array = binary_array and binary_array or {}
    max_recursion_num = tonumber(max_recursion_num) or 20
    section      =  section and section or {}
    num          = tonumber(num) or 1

    if not next(section) then
       return binary_array
    end
    print(cjson.encode(section))
    -- 获取中间值
    local count = (section["max"] - section["min"]) / 2
    -- 左半边区间
    local left = {
        min = section["min"],
        max = section["min"]   count
    }
    -- 右半边区间
    local right = {
        min = section["min"]   count,
        max = section["max"]
    }

    -- 假如给点的经纬度值大于右边最小值 则属于右半边区间为1 否则就是左半边区间 0
    binary_array[#binary_array 1] = place > right["min"] and 1 or 0

    -- 如果递归次数已经达到最大值 则直接返回结果集
    if max_recursion_num <= num then
        return binary_array
    end

    -- 下一次递归我们需要传入的经纬度 区间值
    local _section = place > right["min"] and right or left

    return binary(place, binary_array, max_recursion_num, _section, num   1)
end


local res = binary(113.326059, {}, _base_length_get_nums(4, 1), interval[2], 1)

print(cjson.encode(res))

//打印结果
{"max":180,"min":-180}
{"max":180,"min":0}
{"max":180,"min":90}
{"max":135,"min":90}
{"max":135,"min":112.5}
{"max":123.75,"min":112.5}
{"max":118.125,"min":112.5}
{"max":115.3125,"min":112.5}
{"max":113.90625,"min":112.5}
{"max":113.90625,"min":113.203125}
[1,1,0,1,0,0,0,0,1,0]

我们可以实际手动打一遍执行下，聪明的朋友应该看到一个函数php($geohash->baseLengthGetNums)和lua中(_base_length_get_nums)私有方法，这个是干嘛用的，通过方法注释我们看到大概意思是我们二分层数：

代码语言：javascript复制

--- @desc 根据指定编码长度获取经纬度的 二分层数
--- @param int $length 编码精确度
--- @param int $type 类型 0-纬度；1-经度
--- @return mixed
local function _base_length_get_nums(length, typ)
    -- 第一种方法写死
    local list = { {2, 3}, {5, 5}, {7, 8}, {10, 10}, {12, 13}, {15, 15}, {17, 18}, {20, 20}, {22, 23}, {25, 25}, {27, 28}, {30, 30} }
    
    -- 第二种通过规律计算纬度位数组合成list
    local cycle_num = 12
    local list_res  = {}
    local lat, lng  = 0, 0
    for i = 1, 12, 1 do
        lat = i % 2 == 0 and lat   3 or lat   2
        lng = i % 2 == 0 and lng   2 or lng   3
        list_res[#list_res   1] = {lat, lng}
    end
   
    return list[length][typ]
end