Geohash 算法学习 - 张日海 - 博客园
随笔 - 22, 文章 - 0, 评论 - 4, 引用 - 0
Geohash 算法：
& & 这是一套纬度/经度地理编码算法，把纬度/经度编码成base32位的字符串。这种编码和纬度/经度不是唯一对应，其实是一个纬度/经度区间。算法有一个精度概念，精度越高，字符串越长，所表示的区间越小。可以编码后的字符串想象成一个格子，里面存放一些纬度/经度值。格子趋近很小的时候，只能存放一纬度/经度值，那么编码和纬度/经度就是唯一对应的关系。但是这个不是重点，这套算法目的就是把纬度/经度编码成近似值，通过近似值搜索，就能很高效的缩小范围，然后再从小范围里查找精确值。
例如,坐标57.44(日德兰半岛的顶端附近,在丹麦)产生一个u4pruydqqvj字符串。参考Wikipedia：
算法原理：
以A[-170,42.6] &为例，纬度范围(-90, 90)平分成两个区间(-90, 0)、(0, 90)，位于前一个区间，则编码为0，否则编码为1。由于42.6属于(0, 90)，所以取编码为1。
再将(0, 90)分成 (0, 45), (45, 90)两个区间，而42.6位于(0, 45)，所以编码为0，
再将(0, 45)分成 (0, 22.5), (22.5, 45)两个区间，而42.6位于(22.5, 45)，所以编码为1，
再将(22.5, 45)分成 (22.5, 33.7.5), (33.7.5, 45)两个区间
最后划分四次后纬度编码为：1011
同理经度编码为：0000
如图绿色格子就是此编码代表的区间范围
算出经纬度编码后，从高到低，奇数为经度，偶数为纬度，合并经纬度编码。
然后再把二进制按每五个一组，按base 32 编码成字符串。
13 & & & 31 & & &24 & & & 4 & & & & 2
e & & & & z & & & & s & & & 4 & & & & &2
最后的Geohash 编码为：ezs42&
应用场景：
前面介绍了下编码的规则，现在来讨论下一些应用场景。我们知道，地球是一个近似球体。球面上两点相对球心的角度偏差，和两点的球面距离是一个等比关系。而Geohash 编码其实就是一个纬度/经度区间，区间的角度范围就决定了区间内的点之间的距离范围。通过这个原理，就可以通过一个坐标的经纬度，找出所在的区间和周边区间来搜索 该点周边的坐标。
Wikipedia上以纬度42.6 为例，统计出每次划分后的每个区间的纬度范围。
划分十二次后，每个区间的纬度范围 0.044 ，根据地球半径可心算出每个距离范围为4.8 公里。
& 当geohash length=5 时，通过搜索某点周边的8个相邻区间，可以大概找出周边5公里的坐标。
这个算法有一定限制，纬度越高，基于经度偏差和距离的比值越低，表格中的距离计算精度也随着降低，需要根据cos(纬度)的值进行调整。
下面是官方提供的代码，一个是根据经纬度计算HashCode ，另一个是根据HashCode&计算周边的8个HashCode&。在实际应用中就可以用这几个方法
构建地标的hashCode 并通过hashCode来检索。
public enum Direction
Right = 1,
Bottom = 2,
private const string Base32 = "bcdefghjkmnpqrstuvwxyz";
private static readonly int[] Bits = new[] { 16, 8, 4, 2, 1 };
private static readonly string[][] Neighbors = {
"p0rdcf5h7kjnmqesgutwvy", // Top
"bc01fgdeuvhjyznpkmstqrwx", // Right
"dcfesgujnmqp0r2twvyx8zb", // Bottom
"238967debc01fg45kmstqrwxuvhjyznp", // Left
"bc01fgdeuvhjyznpkmstqrwx", // Top
"p0rdcf5h7kjnmqesgutwvy", // Right
"238967debc01fg45kmstqrwxuvhjyznp", // Bottom
"dcfesgujnmqp0r2twvyx8zb", // Left
private static readonly string[][] Borders = {
new[] {"prxz", "bcfguvyz", "028b", "0145hjnp"},//Top,Right,Bottom,Left
new[] {"bcfguvyz", "prxz", "0145hjnp", "028b"}//Top,Right,Bottom,Left
public static String CalculateAdjacent(String hash, Direction direction)
if (string.IsNullOrEmpty(hash))
return "";
hash = hash.ToLower();
char lastChr = hash[hash.Length - 1];
int type = hash.Length % 2;
var dir = (int)
string nHash = hash.Substring(0, hash.Length - 1);
if (Borders[type][dir].IndexOf(lastChr) != -1)
nHash = CalculateAdjacent(nHash, (Direction)dir);
//南北极的纬度处理，直接返回原值
if (nHash == hash.Substring(0, hash.Length - 1) && (direction == Direction.Top || direction == Direction.Bottom))
return nHash + lastC
return nHash + Base32[Neighbors[type][dir].IndexOf(lastChr)];
public static void RefineInterval(ref double[] interval, int cd, int mask)
if ((cd & mask) != 0)
interval[0] = (interval[0] + interval[1]) / 2;
interval[1] = (interval[0] + interval[1]) / 2;
public static double[] GeohashDecode(String geohash)
bool even = true;
double[] lat = { -90.0, 90.0 };
double[] lon = { -180.0, 180.0 };
foreach (char c in geohash)
int cd = Base32.IndexOf(c);
for (int j = 0; j & 5; j++)
int mask = Bits[j];
RefineInterval(ref lon, cd, mask);
RefineInterval(ref lat, cd, mask);
return new[] { (lat[0] + lat[1]) / 2, (lon[0] + lon[1]) / 2 };
public static String GeohashEncode(double latitude, double longitude)
bool even = true;
int bit = 0;
int ch = 0;
int precision = 12;
string geohash = "";
double[] lat = { -90.0, 90.0 };
double[] lon = { -180.0, 180.0 };
while (geohash.Length & precision)
mid = (lon[0] + lon[1]) / 2;
if (longitude & mid)
ch |= Bits[bit];
mid = (lat[0] + lat[1]) / 2;
if (latitude & mid)
ch |= Bits[bit];
if (bit & 4)
geohash += Base32[ch];
JS代码&引用&
1 &script type="text/javascript"&
BITS = [16, 8, 4, 2, 1];
BASE32 = "bcdefghjkmnpqrstuvwxyz";
NEIGHBORS = { right: { even: "bc01fgdeuvhjyznpkmstqrwx" },
left: { even: "238967debc01fg45kmstqrwxuvhjyznp" },
top: { even: "p0rdcf5h7kjnmqesgutwvy" },
bottom: { even: "dcfesgujnmqp0r2twvyx8zb" }
BORDERS = { right: { even: "bcfguvyz" },
left: { even: "0145hjnp" },
top: { even: "prxz" },
bottom: { even: "028b" }
NEIGHBORS.bottom.odd = NEIGHBORS.left.
NEIGHBORS.top.odd = NEIGHBORS.right.
NEIGHBORS.left.odd = NEIGHBORS.bottom.
NEIGHBORS.right.odd = NEIGHBORS.top.
BORDERS.bottom.odd = BORDERS.left.
BORDERS.top.odd = BORDERS.right.
BORDERS.left.odd = BORDERS.bottom.
BORDERS.right.odd = BORDERS.top.
function refine_interval(interval, cd, mask) {
if (cd & mask)
interval[0] = (interval[0] + interval[1]) / 2;
interval[1] = (interval[0] + interval[1]) / 2;
function calculateAdjacent(srcHash, dir) {
srcHash = srcHash.toLowerCase();
var lastChr = srcHash.charAt(srcHash.length - 1);
var type = (srcHash.length % 2) ? 'odd' : 'even';
var base = srcHash.substring(0, srcHash.length - 1);
if (BORDERS[dir][type].indexOf(lastChr) != -1)
base = calculateAdjacent(base, dir);
return base + BASE32[NEIGHBORS[dir][type].indexOf(lastChr)];
function decodeGeoHash(geohash) {
var is_even = 1;
var lat = []; var lon = [];
lat[0] = -90.0; lat[1] = 90.0;
lon[0] = -180.0; lon[1] = 180.0;
lat_err = 90.0; lon_err = 180.0;
for (i = 0; i & geohash. i++) {
c = geohash[i];
cd = BASE32.indexOf(c);
for (j = 0; j & 5; j++) {
mask = BITS[j];
if (is_even) {
lon_err /= 2;
refine_interval(lon, cd, mask);
lat_err /= 2;
refine_interval(lat, cd, mask);
is_even = !is_
lat[2] = (lat[0] + lat[1]) / 2;
lon[2] = (lon[0] + lon[1]) / 2;
return { latitude: lat, longitude: lon };
function encodeGeoHash(latitude, longitude) {
var is_even = 1;
var i = 0;
var lat = []; var lon = [];
var bit = 0;
var ch = 0;
var precision = 12;
geohash = "";
lat[0] = -90.0; lat[1] = 90.0;
lon[0] = -180.0; lon[1] = 180.0;
while (geohash.length & precision) {
if (is_even) {
mid = (lon[0] + lon[1]) / 2;
if (longitude & mid) {
ch |= BITS[bit];
mid = (lat[0] + lat[1]) / 2;
if (latitude & mid) {
ch |= BITS[bit];
is_even = !is_
if (bit & 4)
geohash += BASE32[ch];Geohash算法 - 博客频道 - CSDN.NET
谨慎对事 低调行事 0与1的世界 浩瀚如海 学无止境
分类：Java算法
1.算法背景
& Geohash的初衷是如何用尽量短的URL来标志地图上的某个位置，而地图上的位置一般是用经纬度来表示，问题就转化为如何把经纬度转化为一个尽量短的URL。
Geohash的算法描述请参考:&,本文的主要目的是更加细致地解释该算法的原理及实用场景。
&& 算法的主要思想是对某一数字通过二分法进行无限逼近，比如纬度的区间是[-90,90]，假如给定一个纬度值：46.5，可以通过下面算法对46.5进行无限逼近:
&（1）把区间[-90,90]进行二分为[-90,0),[0,90]，称为左右区间，可以确定46.5属于右区间[0,90]
&（2）递归上述过程46.5总是属于某个区间，无论第几次迭代46.5总是属于某个区间[a,b]。随着每次迭代区间[a,b]总在缩小，根据极限可知[a,b]会收敛到46.5，用δ来描述就是，任意给定一个&ε，总存在一个N使得：&δ=|x-a/2N&|&&ε,x为任意给定的纬度
&（3）上述分析过程保证了算法收敛性的同时，再记录一下收敛的过程：如果给定的纬度x（46.5）属于左区间，则记录0，如果属于右区间则记录1，这样随着算法的进行会产生一个序列1011100，序列的长度跟给定的收敛次数N相关。
&&&&& 反过来，如果我们知道了序列1011100，我们就可以分别能确定纬度x（46.5）属于哪个更小的迭代区间，也就是说该算法是可逆的
&（4）算法的精度：显然的是，不可能让计算机执行无穷计算，加入执行N此计算，则x属于的区间长度为(b-a)/2N+1&,以纬度计算为例，则为180/2N&，误差近似计算为:err= 180/2N+1&=90/2N&,如果N=20，则误差最大为：0.00009。但无论如何这样表明Geohash是一种近似算法。
&& 在对纬度产生了序列1011100后，在对经度做相同的算法也会产生一个序列，比如0011101。根据偶数位放经度，奇数位放纬度（0被视为偶数），把2个串合二为一，产生一个新串：10，对该串进行Base32编码，则可获得一个ASIIC码的字符串，关于Base32编码，请参考：http://en.wikipedia.org/wiki/Base32
& 解码的过程相对比较简单
&（1）对拿到的字符串进行Base32解码
&（2）根据奇偶位取出纬度、经度
&（3）根据序列反向得到每个区间，并取中间值（0为左区间，1为右区间）
&&该算法目前主要用在地图的地址搜索，有了该算法可以为数据库中的地址建立索引，极大提高地图数据检索的速度。
& 仔细观察，该算法还有另为一个特点，对相近的x,y，会得到相同前缀的序列，原因是相近的x,y，在递归的绝大多数时间会处在同一个区间，故而，逼近的轨迹是一致的，这又可以解决地图中“离我最近的搜索“的问题，同时，对进行hash的模糊检索也有一定的启发作用。
& 下面的实现代码很精美，引用自：http://bloggermap.org/rss/readblog/70907，格式不太好，大家自己整理一下即可
排名：第10821名
（6）（47）（114）（2）（1）（3）（6）（3）（11）（1）（2）（13）（2）（3）（12）（3）（4）（29）（1）（4）（2）（4）（1）（1）（1）（7）（15）（15）（3）（3）（1）（4）（4）（3）（1）（13）（4）（8）（3）（5）（3）（1）（1）（2）（1）（6）（4）（3）（3）（2）（11）（2）import ch.hsr.geohash.GeoH
import ch.hsr.geohash.WGS84P
import ch.hsr.geohash.util.VincentyG
double longitude = 114.99;
double latitude = 22.113;
// 算出当关geoHash
&GeoHash userGeohash = GeoHash.withCharacterPrecision(latitude, longitude,NearByKeyUtils.getMaxRange());
String geoHash=userGeohash.toBase32();
&// 查询附近周围geoHash
GeoHash[] userGeohashs= userGeohash.getAdjacent();
// 装入所有的GeoHash
final List&String& geoHashs=Lists.newArrayList(geoHash);
&for(GeoHash gh:userGeohashs)
&&&&&&& &geoHashs.add(gh.toBase32());
&&&&&&& &System.out.println(gh.toBase32());
// 表示保留几位geohash
public static Integer getMaxRange(){
&&return 6;
需要用到geohash.jar包
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：13497次
排名：千里之外
转载：27篇
(5)(8)(6)(8)(1)(1)(2)