查找是我们经常会碰到的问题，以前我做过一个这样的算法，在有序的数列（80万条左右），这批数据是根据维度由小到大排序的，寻找已知数据的位置，并且所相应的运算，由于这个算法要在嵌入式系统中做，如果一次在内存中载入80万条数据是不明智的。而且这个计算过程是每秒都要做一次，如果不在内存中载入数据时效性上又无法满足，那么只能根据已知数据在整个数列中的位置，然后将这个位置附近的数据载入内存。这个算法与在百度地图上查找最近的饭店基本是一个意思。我们需要对查找的数据库做处理，一维数据要变成二维数据，这是我自己的想法，将80万条数据放在一个个的方框里。然后确定每一个方框边界的经度值与维度值，如下图所示，然后将这些边界值根据经度与维度分别做两张索引表，当然这个表也是有序的，然后根据自己当前的经纬度坐标值(lat,lon)分别用二分法查找自己在表里的位置，得出自己坐标点所在方框的坐标。然后将方框里的数据全部读入内存。当然里面还有边界问题，实际上需要将自己所在方框的周围8个方框都读入内存。如下图所示：
这个其实就是哈希散列的思想。这个方法是可行的，而且已经实现，不过有一个问题是，如何将这80万比数据变成一个一个方框的数据结构按照线性保存起来。这个存储结构应该是这样的：
这是一个示意图，估算一下大概的计算量，如果要将80万笔数据分别根据经度维度一个一个对比放入框框中，这个时间复杂度是无法接受的。同样这也要设计一个哈希函数来完成这个工作，下面说重点：
所谓的GeoHash算法。
我们已知经纬度（22.527051,113.918646）先用逼近算法对其进行编码，具体做法如下：
以经度为例，value =113.918646，大于中间值为1，小于中间值为0。这个区间如何得来的呢？要知道经度的范围是[180,-180]，那么中间值就是0，判断是在[180,0]还是[0,-180]如果在[180,0]就是1，然后缩小区间，在[180,0]这个区间
与中间值90比较，以此类推。最后得到编码值是：11010 00100，一共10位，为什么是10位与后面混合编码转换成base32编码有关。
同理得到维度22.527051的编码值是：10100 00000，最后要将纬度编码与经度编码混合，偶数放经度，奇数放纬度，这个可能不好理解我做一张图：
合成之后在转换成Base32编码，Base32编码是0-9、b-z（去掉a, i, l, o），这种编码方式是32以内的十进制，正好是5位二进制数，所以之前经纬度编码选择的是10位，因此正好可以换成2个字符。如下表：
最后可得出对应的值：ws10。
这个GeoHash算法网上有很多，我参考的是这个：http://www.cnblogs.com/LBSer/p/3310455.html
至于为什么这样编码里面有解释自己理解吧。我用c写了一下实现，不具有普遍性。
void GeoHash(double lat,double lon,int flag,char* hashCode)
{
double left,right,middle,value;
int ret_lat,ret_lon,temp,temp1;
int mixLatLon=;
right = ;
left = -;
ret_lat = ret_lon = ;
temp = flag;
value = lon;
while(flag){
middle = (float)((right+left)/);
if(value>middle){
ret_lon |= (<<(flag-));
left = middle;
}else if(value < middle){
ret_lon |= (<<(flag-));
right = middle;
}else{
ret_lon |= (<<(flag-));
left = middle;
}
flag--;
}
flag = temp;
right = ;
left = -;
value = lat;
printf("value:%f\r\n",value);
while(flag){
middle = (float)((right+left)/);
if(value>middle){
ret_lat |= (<<(flag-));
left = middle;
}else if(value < middle){
ret_lat |= (<<(flag-));
right = middle;
}else{
ret_lat |= (<<(flag-));
left = middle;
}
flag--;
}
flag = temp;
flag = flag*;
temp1 = temp;
while(temp1){
if(ret_lon & (<<(temp1-))){
mixLatLon |= (<<(flag-));
}else{
mixLatLon |= (<<(flag-));
}
flag--;
if(ret_lat & (<<(temp1-))){
mixLatLon |= (<<(flag-));
}else{
mixLatLon |= (<<(flag-));
}
temp1--;
flag--;
}
flag = ;
while(flag){
hashCode[flag-] = ToBase32(mixLatLon&0x1F);
mixLatLon >>= ;
flag--;
}
} char ToBase32(int dec)
{
char ret;
switch(dec){
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='';break;
case :ret='b';break;
case :ret='c';break;
case :ret='d';break;
case :ret='e';break;
case :ret='f';break;
case :ret='g';break;
case :ret='h';break;
case :ret='j';break;
case :ret='k';break;
case :ret='m';break;
case :ret='n';break;
case :ret='p';break;
case :ret='q';break;
case :ret='r';break;
case :ret='s';break;
case :ret='t';break;
case :ret='u';break;
case :ret='v';break;
case :ret='w';break;
case :ret='x';break;
case :ret='y';break;
case :ret='z';break;
default:ret='a';
}
return ret;
}
调用代码：
int main(int argc, char *argv[]) {
char hashCode[];
GeoHash(22.527051,113.918646,,hashCode);
printf("hashCode:%s",hashCode);
printf("\r\n");
system("pause");
return ;
}
结果是：ws10
这里碰到一个问题，在c中，如果想要函数返回一个字符串有哪些做法呢：