网上一篇关于geohash的文章
代码可以引用这里：http://code.google.com/p/geospatialweb/source/browse/trunk/geohash/src/Geohash.java?r=104
| import java.util.BitSet; |
| import java.util.HashMap; |
| public class Geohash { |
| private static int numbits = 6 * 5; |
| final static char[] digits = { '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' }; |
| |
| final static HashMap<Character, Integer> lookup = new HashMap<Character, Integer>(); |
| static { |
| int i = 0; |
| for (char c : digits) |
| lookup.put(c, i++); |
| } |
| public static void main(String[] args) { |
| double[] latlon = new Geohash().decode("dj248j248j24"); |
| System.out.println(latlon[0] + " " + latlon[1]); |
| |
| Geohash e = new Geohash(); |
| String s = e.encode(30, -90.0); |
| System.out.println(s); |
| latlon = e.decode(s); |
| System.out.println(latlon[0] + ", " + latlon[1]); |
| } |
| public double[] decode(String geohash) { |
| StringBuilder buffer = new StringBuilder(); |
| for (char c : geohash.toCharArray()) { |
| int i = lookup.get(c) + 32; |
| buffer.append( Integer.toString(i, 2).substring(1) ); |
| } |
| |
| BitSet lonset = new BitSet(); |
| BitSet latset = new BitSet(); |
| |
| //even bits |
| int j =0; |
| for (int i=0; i< numbits*2;i+=2) { |
| boolean isSet = false; |
| if ( i < buffer.length() ) |
| isSet = buffer.charAt(i) == '1'; |
| lonset.set(j++, isSet); |
| } |
| |
| //odd bits |
| j=0; |
| for (int i=1; i< numbits*2;i+=2) { |
| boolean isSet = false; |
| if ( i < buffer.length() ) |
| isSet = buffer.charAt(i) == '1'; |
| latset.set(j++, isSet); |
| } |
| |
| double lon = decode(lonset, -180, 180); |
| double lat = decode(latset, -90, 90); |
| |
| return new double[] {lat, lon}; |
| } |
| |
| private double decode(BitSet bs, double floor, double ceiling) { |
| double mid = 0; |
| for (int i=0; i<bs.length(); i++) { |
| mid = (floor + ceiling) / 2; |
| if (bs.get(i)) |
| floor = mid; |
| else |
| ceiling = mid; |
| } |
| return mid; |
| } |
| |
| |
| public String encode(double lat, double lon) { |
| BitSet latbits = getBits(lat, -90, 90); |
| BitSet lonbits = getBits(lon, -180, 180); |
| StringBuilder buffer = new StringBuilder(); |
| for (int i = 0; i < numbits; i++) { |
| buffer.append( (lonbits.get(i))?'1':'0'); |
| buffer.append( (latbits.get(i))?'1':'0'); |
| } |
| return base32(Long.parseLong(buffer.toString(), 2)); |
| } |
| private BitSet getBits(double lat, double floor, double ceiling) { |
| BitSet buffer = new BitSet(numbits); |
| for (int i = 0; i < numbits; i++) { |
| double mid = (floor + ceiling) / 2; |
| if (lat >= mid) { |
| buffer.set(i); |
| floor = mid; |
| } else { |
| ceiling = mid; |
| } |
| } |
| return buffer; |
| } |
| public static String base32(long i) { |
| char[] buf = new char[65]; |
| int charPos = 64; |
| boolean negative = (i < 0); |
| if (!negative) |
| i = -i; |
| while (i <= -32) { |
| buf[charPos--] = digits[(int) (-(i % 32))]; |
| i /= 32; |
| } |
| buf[charPos] = digits[(int) (-i)]; |
| if (negative) |
| buf[--charPos] = '-'; |
| return new String(buf, charPos, (65 - charPos)); |
| } |
| } |
版权声明：可以任意转载，但转载时必须标明原作者charlee、原始链接http://tech.idv2.com/2011/07/05/geohash-intro/以及本声明。
上回说到了用经纬度范围实现附近地点搜索。 一些小型应用中这样做没问题，但在大型应用中它有个显著的缺点：速度慢。慢的原因有两个， 第一是范围比较的索引利用率并不高，第二是SQL语句极其不稳定(不同的当前位置会产生完全不同的SQL查询)，很难缓存。
geohash是一种地址编码，它能把二维的经纬度编码成一维的字符串。比如，北海公园的编码是wx4g0ec1。
geohash有以下几个特点：
首先，geohash用一个字符串表示经度和纬度两个坐标。某些情况下无法在两列上同时应用索引 （例如MySQL 4之前的版本，Google App Engine的数据层等），利用geohash，只需在一列上应用索引即可。
其次，geohash表示的并不是一个点，而是一个矩形区域。比如编码wx4g0ec19，它表示的是一个矩形区域。 使用者可以发布地址编码，既能表明自己位于北海公园附近，又不至于暴露自己的精确坐标，有助于隐私保护。
第三，编码的前缀可以表示更大的区域。例如wx4g0ec1，它的前缀wx4g0e表示包含编码wx4g0ec1在内的更大范围。 这个特性可以用于附近地点搜索。首先根据用户当前坐标计算geohash（例如wx4g0ec1）然后取其前缀进行查询 （SELECT * FROM place WHERE geohash LIKE 'wx4g0e%'），即可查询附近的所有地点。
geohash的算法
下面以(39.92324, 116.3906)为例，介绍一下geohash的编码算法。首先将纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)， 如果目标纬度位于前一个区间，则编码为0，否则编码为1。由于39.92324属于(0, 90)，所以取编码为1。然后再将(0, 90)分成(0, 45), (45, 90)两个区间，而39.92324位于(0, 45)，所以编码为0。以此类推，直到精度符合要求为止，得到纬度编码为1011 1000 1100 0111 1001。
| 纬度范围 | 划分区间0 | 划分区间1 | 39.92324所属区间 |
| (-90, 90) | (-90, 0.0) | (0.0, 90) | 1 |
| (0.0, 90) | (0.0, 45.0) | (45.0, 90) | 0 |
| (0.0, 45.0) | (0.0, 22.5) | (22.5, 45.0) | 1 |
| (22.5, 45.0) | (22.5, 33.75) | (33.75, 45.0) | 1 |
| (33.75, 45.0) | (33.75, 39.375) | (39.375, 45.0) | 1 |
| (39.375, 45.0) | (39.375, 42.1875) | (42.1875, 45.0) | 0 |
| (39.375, 42.1875) | (39.375, 40.7812) | (40.7812, 42.1875) | 0 |
| (39.375, 40.7812) | (39.375, 40.0781) | (40.0781, 40.7812) | 0 |
| (39.375, 40.0781) | (39.375, 39.7265) | (39.7265, 40.0781) | 1 |
| (39.7265, 40.0781) | (39.7265, 39.9023) | (39.9023, 40.0781) | 1 |
| (39.9023, 40.0781) | (39.9023, 39.9902) | (39.9902, 40.0781) | 0 |
| (39.9023, 39.9902) | (39.9023, 39.9462) | (39.9462, 39.9902) | 0 |
| (39.9023, 39.9462) | (39.9023, 39.9243) | (39.9243, 39.9462) | 0 |
| (39.9023, 39.9243) | (39.9023, 39.9133) | (39.9133, 39.9243) | 1 |
| (39.9133, 39.9243) | (39.9133, 39.9188) | (39.9188, 39.9243) | 1 |
| (39.9188, 39.9243) | (39.9188, 39.9215) | (39.9215, 39.9243) | 1 |
经度也用同样的算法，对(-180, 180)依次细分，得到116.3906的编码为1101 0010 1100 0100 0100。
| 经度范围 | 划分区间0 | 划分区间1 | 116.3906所属区间 |
| (-180, 180) | (-180, 0.0) | (0.0, 180) | 1 |
| (0.0, 180) | (0.0, 90.0) | (90.0, 180) | 1 |
| (90.0, 180) | (90.0, 135.0) | (135.0, 180) | 0 |
| (90.0, 135.0) | (90.0, 112.5) | (112.5, 135.0) | 1 |
| (112.5, 135.0) | (112.5, 123.75) | (123.75, 135.0) | 0 |
| (112.5, 123.75) | (112.5, 118.125) | (118.125, 123.75) | 0 |
| (112.5, 118.125) | (112.5, 115.312) | (115.312, 118.125) | 1 |
| (115.312, 118.125) | (115.312, 116.718) | (116.718, 118.125) | 0 |
| (115.312, 116.718) | (115.312, 116.015) | (116.015, 116.718) | 1 |
| (116.015, 116.718) | (116.015, 116.367) | (116.367, 116.718) | 1 |
| (116.367, 116.718) | (116.367, 116.542) | (116.542, 116.718) | 0 |
| (116.367, 116.542) | (116.367, 116.455) | (116.455, 116.542) | 0 |
| (116.367, 116.455) | (116.367, 116.411) | (116.411, 116.455) | 0 |
| (116.367, 116.411) | (116.367, 116.389) | (116.389, 116.411) | 1 |
| (116.389, 116.411) | (116.389, 116.400) | (116.400, 116.411) | 0 |
| (116.389, 116.400) | (116.389, 116.394) | (116.394, 116.400) | 0 |
接下来将经度和纬度的编码合并，奇数位是纬度，偶数位是经度，得到编码 11100 11101 00100 01111 00000 01101 01011 00001。
最后，用0-9、b-z（去掉a, i, l, o）这32个字母进行base32编码，得到(39.92324, 116.3906)的编码为wx4g0ec1。
| 十进制 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
| 十进制 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
| base32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
解码算法与编码算法相反，先进行base32解码，然后分离出经纬度，最后根据二进制编码对经纬度范围进行细分即可，这里不再赘述。 不过由于geohash表示的是区间，编码越长越精确，但不可能解码出完全一致的地址。
geohash的应用：附近地址搜索
geohash的最大用途就是附近地址搜索了。不过，从geohash的编码算法中可以看出它的一个缺点：位于格子边界两侧的两点， 虽然十分接近，但编码会完全不同。实际应用中，可以同时搜索当前格子周围的8个格子，即可解决这个问题。
以geohash的python库为例，相关的geohash操作如下：
>>> import geohash
>>> geohash.encode(39.92324, 116.3906, 5) # 编码，5表示编码长度
'wx4g0'
>>> geohash.expand('wx4g0') # 求wx4g0格子及周围8个格子的编码
['wx4ep', 'wx4g1', 'wx4er', 'wx4g2', 'wx4g3', 'wx4dz', 'wx4fb', 'wx4fc', 'wx4g0']
最后，我们来看看本文开头提出的两个问题：速度慢，缓存命中率低。使用geohash查询附近地点，用的是字符串前缀匹配：
SELECT * FROM place WHERE geohash LIKE 'wx4g0%';
而前缀匹配可以利用geohash列上的索引，因此查询速度不会太慢。另外，即使用户坐标发生微小的变化， 也能编码成相同的geohash，这就保证了每次执行相同的SQL语句，使得缓存命中率大大提高。
相关资源
- python-geohash: http://code.google.com/p/python-geohash/
- geohash演示: http://openlocation.org/geohash/geohash-js/