GeoHsah算法

一、 GeoHash的介绍

现在很多APP都有搜索附近的功能，比如附近的人、附近的店铺等。要实现这样的功能，我们可以用最笨的方法：根据经纬度计算距离，然后划定一个阈值，只要小于该阈值就算是附近的。这种方法在数据量小时基本没问题，但是，如果数据量特别大，那服务器就需要进行大量的计算，负担很重！为了解决这一类问题，一个比较常用的方法就是利用GeoHash。

二、GeoHash应用案例

之前工作中有一个需求，就是在给出若干个加油点的二维坐标，然后再给你一个当前坐标，你要搜索出距离当前周边一公里加油站的信息。

在考虑二维的附近点搜索时，最原始的方法肯定是将所有的加油点的坐标都加入到list中，然后遍历所有的节点，判断哪个节点的坐标在自己左边距离范围内。但是这样操作的话，由于我们要进行多次的附近点搜索，这样每次搜索的成本就会相当大，比如我们搜索 N次，一共有 M 个加油点，复杂度将达到 N*M ，降低搜索效率。
所以我们应该降低每次的搜索效率。然后查阅了一些资料，参阅到一些附近点搜索的经典算法，也就是将要介绍的GeoHash算法。能够将坐标变成特定的编码，然后进行对应哈希，还能够根据编码的前缀，来进行判断两点是否在附近。

加油站信息以String的方式存放在Redis中，如下：

三、GeoHash算法解析

GeoHash算法可以将一个二维的经纬度坐标转换成一个可比较的字符串信息，也就是一个降维的过程。具体的实现过程如下：

谷歌地图：39.1785816935,117.4612203712 (不同地图供应商所提供定位信息有差异)

纬度 longitude ：39.1785816935

经度 latitude：117.4612203712

将经纬度进行二分法的形式落于相对应的区间中，步骤如下图：39.17858169坐落于0-90的区间内，坐落于0-45的区间内，坐落于22.5-45的区间内，层层二分，数据分的越细，获取到的精度越准确；

最终获得纬度的二进制：101101...

经度的二进制：110100...

将经纬度的二进制数进行组合，以奇数为纬度，偶数为经度组合；

经纬度组合后：11100 11100 01...

这时候，将经纬度转GeoHash字符串的工作已经完成了一半了，是不是赶脚很简单~

四、Base32算法讲解~

在开发中，Base32、Base64加密解密相信大家都有遇到过和了解过，GeoHash将二维经纬度转换成可比较字符串的过程也就是一个转Base32的过程，Base32是由数据0~9及26个英文字母(减去’a’ , ’i’ , ’l’ , ’o’四个字符)

Base32

Base64( 了解一下 ~ ~  )

上面我们已经拿到了组合后的经纬度二进制序列111001110001...

Base32对应的二进制序列是5位，Base64对应的二进制序列是6位，我们需要将这个经纬度二进制序列转换成Base32的形式输出，将二进制序列每5位一组进行拆分得到：

11100  11100  01.....

11100转换成十进制得到 1*2^4 + 1*2^3 + 1*2^2 = 16 + 8 + 4 = 28 将28转换成Base32得到“W”

11100 11100 01111 11100

Base32图表

所以上面的这个二进制序列可以得到的字符串是 ww,所表示的区域范围是：

将经纬度转换成二进制序列的过程中，转换的次数越多，所表示的精度越细，标识的范围越小，我们日常生活中所描述的用户定位，在宏观上形容的并不是一个点，而是表示的一块区域信息，我们位于某一个区域范围内。

前面我们已经知道，国家电网某建筑在高德上的定位是39.1785816935,117.4612203712，如果完全转换成GeoHash可比较字符串的值是：

我们分别得到了wwgw和wwgwbuhxubfp，代表的不同精度，下面我们来验证一下；

WWGW基本上已经定位到了天津市内了；

在这里我们已经可以看到自己所在的位置了，而可比较字符串目前的精度还只是停留在7位，7位就已经拿到了如此详细的地址信息，而刚刚我们拿到的最大精度是12位wwgwbuhxubfp，可想而知这个定位是有多精准。

在这里，大家有没有什么问题想问的呢？

已经替大家想好了，为何文本中多次提到“可比较字符串”，这个可比较字符串具体是怎样的一个可比较性呢，相信到了这里，大家心中都已经有了自己的答案了；

字符串越长，表示的范围越精确。5位的编码能表示10平方千米范围的矩形区域，而6位编码能表示更精细的区域（约0.34平方千米）

a）在纬度相等的情况下：

 经度每隔0.00001度，距离相差约1米；

 每隔0.0001度，距离相差约10米；

 每隔0.001度，距离相差约100米；

 每隔0.01度，距离相差约1000米；

 每隔0.1度，距离相差约10000米。

b）在经度相等的情况下：

 纬度每隔0.00001度，距离相差约1.1米；

 每隔0.0001度，距离相差约11米；

 每隔0.001度，距离相差约111米；

 每隔0.01度，距离相差约1113米；

 每隔0.1度，距离相差约11132米。

GeoHash算法利用Base32将全球划分成32个大的区域块，每一个区域块中再次划分成32个区域块，这样层层划分，获取到一个精准的地理位置；

Geohash的0、1串序列是经度0、1序列和纬度0、1序列中的数字交替进行排列的，偶数位对应的序列为经度序列，奇数位对应的序列为纬度序列，在进行第一次划分时，Geohash0、1序列中的前5个bits（11100），那么这5bits中有3bits是表示经度，2bits表示纬度，所以第一次划分时，是将经度划分成8个区段（2^3 = 8），将纬度划分为4个区段（2^2 = 4），这样就形成了32个区域(对应Base32)。

(维基百科上GeoHash位数精度参考表)

到了这里，利用用户GeoHash可比较字符串可以计算出附近的人距离范围，但是这里面还有一个很严重的问题，有没有小伙伴有想到或者考虑到？

五、GeoHash算法深度解析~

如下图所示，根据可比较字符串来划分区域，会存在一个边界问题；

解决的思路很简单，我们查询时，除了使用定位点的GeoHash编码进行匹配外，还使用周围8个区域的GeoHash编码，这样可以避免这个问题。
  

上文讲了GeoHash的计算步骤，仅仅说明是什么而没有说明为什么？为什么分别给经度和维度编码？为什么需要将经纬度两串编码交叉组合成一串编码？

新概念：Peano空间填充曲线(GeoHash采用的是Peano空间填充曲线)

需了解曲线突变(上图问题产生就是因为曲线突变而导致的)

空间索引

引入一个题外话：计算两个点的直线距离可以使用计算平方根的方式吗？ a^2 + b^2 = c^2

了解一下空间距离计算

l 将GeoHash字符串转换成二进制序列

package cn.jiayao.geohash.rediconf;

import java.util.HashMap;

        public class to2System {

            private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7',
                    '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n',
                    'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

            private static HashMap<Character, Integer> CHARSMAP;

            static {
                CHARSMAP = new HashMap<Character, Integer>();
                for (int i = 0; i < CHARS.length; i++) {
                    CHARSMAP.put(CHARS[i], i);
                }
            }

            private String getBase32BinaryString(int i) {
                if (i < 0 || i > 31) {
                    return null;
                }
                String str = Integer.toBinaryString(i + 32);
                return str.substring(1);
            }


            private String getGeoHashBinaryString(String geoHash) {
                if (geoHash == null || "".equals(geoHash)) {
                    return null;
                }
                StringBuffer sb = new StringBuffer();
                for (int i = 0; i < geoHash.length(); i++) {
                    char c = geoHash.charAt(i);
                    if (CHARSMAP.containsKey(c)) {
                        String cStr = getBase32BinaryString(CHARSMAP.get(c));
                        if (cStr != null) {
                            sb.append(cStr);
                        }
                    }
                }
                return sb.toString();
            }

            public static void main(String[] args) {
                String wwgwbuh = new Test03().getGeoHashBinaryString("wwgwbuhxubfp");
                System.out.println(wwgwbuh);
            }
        /**
         * 输出结果：111001110001111111000101011010100001110111010010100111010101
         */
        }

l 将二进制序列转换成GeoHash字符串

package cn.jiayao.geohash.rediconf;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

import cn.jiayao.geohash.utils.LocationBean;

/**
 * @author: JiaYao
 * @demand: 将经纬度转换成GeoHash可比较字符串
 * @parameters:
 * @creationDate： 2018/6/28 0028 19:35
 */
public class ToGeoHash {
    private LocationBean location;
    /**
     * 1 2500km;2 630km;3 78km;4 30km
     * 5 2.4km; 6 610m; 7 76m; 8 19m 9 2m
     */
//    private int hashLength = 8; //经纬度转化为geohash长度
//    private int latLength = 20; //纬度转化为二进制长度
//    private int lngLength = 20; //经度转化为二进制长度
    private int hashLength = 12; //经纬度转化为geohash长度
    private int latLength = 30; //纬度转化为二进制长度
    private int lngLength = 30; //经度转化为二进制长度

    private double minLat;//每格纬度的单位大小
    private double minLng;//每个经度的单位大小
    private static final char[] CHARS = {'0', '1', '2', '3', '4', '5', '6', '7',
            '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n',
            'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
    private static HashMap<Character, Integer> CHARSMAP;

    static {
        CHARSMAP = new HashMap<Character, Integer>();
        for (int i = 0; i < CHARS.length; i++) {
            CHARSMAP.put(CHARS[i], i);
        }
    }

    public ToGeoHash(double lat, double lng) {
        location = new LocationBean(lat, lng);
        setMinLatLng();
    }

    public int gethashLength() {
        return hashLength;
    }

    /**
     * @Author:
     * @Description: 设置经纬度的最小单位
     */
    private void setMinLatLng() {
        minLat = LocationBean.MAXLAT - LocationBean.MINLAT;
        for (int i = 0; i < latLength; i++) {
            minLat /= 2.0;
        }
        minLng = LocationBean.MAXLNG - LocationBean.MINLNG;
        for (int i = 0; i < lngLength; i++) {
            minLng /= 2.0;
        }
    }

    /**
     * @return
     * @Author:
     * @Description: 求所在坐标点及周围点组成的九个
     */
    public List<String> getGeoHashBase32For9() {
        double leftLat = location.getLat() - minLat;
        double rightLat = location.getLat() + minLat;
        double upLng = location.getLng() - minLng;
        double downLng = location.getLng() + minLng;
        List<String> base32For9 = new ArrayList<String>();
        //左侧从上到下 3个
        String leftUp = getGeoHashBase32(leftLat, upLng);
        if (!(leftUp == null || "".equals(leftUp))) {
            base32For9.add(leftUp);
        }
        String leftMid = getGeoHashBase32(leftLat, location.getLng());
        if (!(leftMid == null || "".equals(leftMid))) {
            base32For9.add(leftMid);
        }
        String leftDown = getGeoHashBase32(leftLat, downLng);
        if (!(leftDown == null || "".equals(leftDown))) {
            base32For9.add(leftDown);
        }
        //中间从上到下 3个
        String midUp = getGeoHashBase32(location.getLat(), upLng);
        if (!(midUp == null || "".equals(midUp))) {
            base32For9.add(midUp);
        }
        String midMid = getGeoHashBase32(location.getLat(), location.getLng());
        if (!(midMid == null || "".equals(midMid))) {
            base32For9.add(midMid);
        }
        String midDown = getGeoHashBase32(location.getLat(), downLng);
        if (!(midDown == null || "".equals(midDown))) {
            base32For9.add(midDown);
        }
        //右侧从上到下 3个
        String rightUp = getGeoHashBase32(rightLat, upLng);
        if (!(rightUp == null || "".equals(rightUp))) {
            base32For9.add(rightUp);
        }
        String rightMid = getGeoHashBase32(rightLat, location.getLng());
        if (!(rightMid == null || "".equals(rightMid))) {
            base32For9.add(rightMid);
        }
        String rightDown = getGeoHashBase32(rightLat, downLng);
        if (!(rightDown == null || "".equals(rightDown))) {
            base32For9.add(rightDown);
        }
        return base32For9;
    }

    /**
     * @param length
     * @return
     * @Author:
     * @Description: 设置经纬度转化为geohash长度
     */
    public boolean sethashLength(int length) {
        if (length < 1) {
            return false;
        }
        hashLength = length;
        latLength = (length * 5) / 2;
        if (length % 2 == 0) {
            lngLength = latLength;
        } else {
            lngLength = latLength + 1;
        }
        setMinLatLng();
        return true;
    }

    /**
     * @return
     * @Author:
     * @Description: 获取经纬度的base32字符串
     */
    public String getGeoHashBase32() {
        return getGeoHashBase32(location.getLat(), location.getLng());
    }

    /**
     * @param lat
     * @param lng
     * @return
     * @Author:
     * @Description: 获取经纬度的base32字符串
     */
    private String getGeoHashBase32(double lat, double lng) {
        boolean[] bools = getGeoBinary(lat, lng);
        if (bools == null) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < bools.length; i = i + 5) {
            boolean[] base32 = new boolean[5];
            for (int j = 0; j < 5; j++) {
                base32[j] = bools[i + j];
            }
            char cha = getBase32Char(base32);
            if (' ' == cha) {
                return null;
            }
            sb.append(cha);
        }
        return sb.toString();
    }

    /**
     * @param base32
     * @return
     * @Author:
     * @Description: 将五位二进制转化为base32
     */
    private char getBase32Char(boolean[] base32) {
        if (base32 == null || base32.length != 5) {
            return ' ';
        }
        int num = 0;
        for (boolean bool : base32) {
            num <<= 1;
            if (bool) {
                num += 1;
            }
        }
        return CHARS[num % CHARS.length];
    }

    /**
     * @param i
     * @return
     * @Author:
     * @Description: 将数字转化为二进制字符串
     */
    private String getBase32BinaryString(int i) {
        if (i < 0 || i > 31) {
            return null;
        }
        String str = Integer.toBinaryString(i + 32);
        return str.substring(1);
    }

    /**
     * @param geoHash
     * @return
     * @Author:
     * @Description: 将geoHash转化为二进制字符串
     */
    private String getGeoHashBinaryString(String geoHash) {
        if (geoHash == null || "".equals(geoHash)) {
            return null;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < geoHash.length(); i++) {
            char c = geoHash.charAt(i);
            if (CHARSMAP.containsKey(c)) {
                String cStr = getBase32BinaryString(CHARSMAP.get(c));
                if (cStr != null) {
                    sb.append(cStr);
                }
            }
        }
        return sb.toString();
    }

    /**
     * @param geoHash
     * @return
     * @Author:
     * @Description: 返回geoHash 对应的坐标
     */
    public LocationBean getLocation(String geoHash) {
        String geoHashBinaryStr = getGeoHashBinaryString(geoHash);
        if (geoHashBinaryStr == null) {
            return null;
        }
        StringBuffer lat = new StringBuffer();
        StringBuffer lng = new StringBuffer();
        for (int i = 0; i < geoHashBinaryStr.length(); i++) {
            if (i % 2 != 0) {
                lat.append(geoHashBinaryStr.charAt(i));
            } else {
                lng.append(geoHashBinaryStr.charAt(i));
            }
        }
        double latValue = getGeoHashMid(lat.toString(), LocationBean.MINLAT, LocationBean.MAXLAT);
        double lngValue = getGeoHashMid(lng.toString(), LocationBean.MINLNG, LocationBean.MAXLNG);
        LocationBean location = new LocationBean(latValue, lngValue);
        location.setGeoHash(geoHash);
        return location;
    }

    /**
     * @param binaryStr
     * @param min
     * @param max
     * @return
     * @Author:
     * @Description: 返回二进制对应的中间值
     */
    private double getGeoHashMid(String binaryStr, double min, double max) {
        if (binaryStr == null || binaryStr.length() < 1) {
            return (min + max) / 2.0;
        }
        if (binaryStr.charAt(0) == '1') {
            return getGeoHashMid(binaryStr.substring(1), (min + max) / 2.0, max);
        } else {
            return getGeoHashMid(binaryStr.substring(1), min, (min + max) / 2.0);
        }
    }

    /**
     * @param lat
     * @param lng
     * @return
     * @Author:
     * @Description: 获取坐标的geo二进制字符串
     */
    private boolean[] getGeoBinary(double lat, double lng) {
        boolean[] latArray = getHashArray(lat, LocationBean.MINLAT, LocationBean.MAXLAT, latLength);
        boolean[] lngArray = getHashArray(lng, LocationBean.MINLNG, LocationBean.MAXLNG, lngLength);
        return merge(latArray, lngArray);
    }

    /**
     * @param latArray
     * @param lngArray
     * @return
     * @Author:
     * @Description: 合并经纬度二进制
     */
    private boolean[] merge(boolean[] latArray, boolean[] lngArray) {
        if (latArray == null || lngArray == null) {
            return null;
        }
        boolean[] result = new boolean[lngArray.length + latArray.length];
        Arrays.fill(result, false);
        for (int i = 0; i < lngArray.length; i++) {
            result[2 * i] = lngArray[i];
        }
        for (int i = 0; i < latArray.length; i++) {
            result[2 * i + 1] = latArray[i];
        }
        return result;
    }

    /**
     * @param value
     * @param min
     * @param max
     * @return
     * @Author:
     * @Description: 将数字转化为geohash二进制字符串
     */
    private boolean[] getHashArray(double value, double min, double max, int length) {
        if (value < min || value > max) {
            return null;
        }
        if (length < 1) {
            return null;
        }
        boolean[] result = new boolean[length];
        for (int i = 0; i < length; i++) {
            double mid = (min + max) / 2.0;
            if (value > mid) {
                result[i] = true;
                min = mid;
            } else {
                result[i] = false;
                max = mid;
            }
        }
        return result;
    }


    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ToGeoHash g = new ToGeoHash(39.1785816935, 117.4612203712);
        String geoHash = g.getGeoHashBase32();
        System.out.println(geoHash);
        LocationBean bean = g.getLocation(geoHash);
//        System.out.println(JsonUtil.parseJson(bean));
        System.out.println(new ToGeoHash(bean.getLat(), bean.getLng()).getGeoHashBase32());
//        System.out.println(DistanceUtil.getDistance(bean.getLat(), bean.getLng(), bean.getLat() - g.minLat, bean.getLng() - g.minLng));
    }
}

六、Redis3.2支持GEO地理位置

Redis目前已经到了4.0版本，4.0可以很友好的支持大数据量的批量删除操作；今天需要引入的是Redis3.2版本，大家都知道Redis3.2可以很好的解决空值这个问题，很大程度上可以避免Redis的穿透，从而避免造成数据库雪崩的严重事故的产生，其实,在Redis3.2中还支持GEO地理位置的计算等神奇的操作。地理位置大概有6个命令，分别是：

• GEOADD  添加操作

    ·   GEODIST  计算两个位置之间距离

m 表示单位为米。

km 表示单位为千米。

mi 表示单位为英里。

ft 表示单位为英尺。

    ·   GEOHASH  返回一个或多个位置的GeoHash表示

    ·   GEOPOS   从Key中返回所有给定位置元素的位置

    ·   GEORADIUS 以给定经纬度为中心，返回以中心键距离不超过最大距离的所有位置元素

    ·   GEORADIUSBYMEMBER 和GEORADIUS相似，给定距离的所有元素，但是给的中心点有差异

Redis客户端，如下：

前面我们通过geohash计算出国网研一楼的GeoHash值是wwgwbuhxubfp

现在通过Redis3.2来计算，看看获取到的GeoHash的值会有多少的偏差

wwgwbuhxub0 和 wwgwbuhxubfp

我们发现，在第11位的时候GeoHash的值发生了不一样，通过维基百科提供的GeoHash的精准表我们可以知道，在第8位的时候，距离大概相差在19米，第9位的时候，距离大概相差在2米，那么第11位的时候，距离会相差在多少呢？

    通过两个已知的经纬度，即可计算出两个位置的距离，后期还可以结合高德地图API进行导航及自定义路标节点等。

    所以，实现附近的人的功能查看，是不是也一样很简单呢。

    例如：查看我附近的加油站信息