摘自 怎么快速找到：附近的人 - 知乎
仅供个人使用
问题描述：如何实现 “附近的人” 功能？
暴力法：欧式距离
原理：计算这个用户与其他用户的欧氏距离，然后进行排序
优点：实现简单
缺点：时间复杂度高，当用户量大时，即使使用类似于 MR 的分布式运算，也需要消耗大量资源。
推荐：GeoHash
原理：将地图展开成一个平面，将平面切割成小格并为小格编号。将用户的位置转换成所处小格的编号。与当前用户同一个格子或附近格子的用户返回给当前用户。
GeoHash：为格子编号的一种编码方式： 『每次将范围折半，值处于前半部分，得 0；反之，得 1。』
// geohash的伪代码
public String getCode(double value, double min, double max, double codeLen){
StringBuilder sb = new StringBuilder();
// codeLen：对折次数，即code的长度
for(int i=0; i<codeLen; i++){
double mid = (max + min) / 2.0;
if(value < min){ // 说明 值处于前半区
sb.append('0');
} else{ // 说明 值处于后半区
sb.append('1');
}
}
return sb.toString();
}
GeoHash计算方式的示例
GeoHash完整的转换
问题：如何快速查找 “附近的人”？
1）将 (user_id, user_geoCode) 存入数据库并在 user_geoCode 建索引
2）select * from locTable where user_geoCode = curUser_geoCode 返回附近的人（即同一格子的人）
更多问题（如下）见参考文献
- 编码设置为多少位比较合适？
- 同一格子内没有人，该如何处理？
