说出 4 种 “附近的人” 实现方式,面试官笑了
引言
昨天一位公众号粉丝和我讨论了一道面试题,个人觉得比较有意义,这里整理了一下分享给大家,愿小伙伴们面试路上少踩坑。面试题目比较简单:“让你实现一个附近的人功能,你有什么方案?”,这道题其实主要还是考察大家对于技术的广度,本文介绍几种方案,给大家一点思路,避免在面试过程中语塞而影响面试结果,如有不严谨之处,还望亲人们温柔指正!
“附近的人”
功能生活中是比较常用的,像外卖app附近的餐厅,共享单车app里附近的车辆。既然常用面试被问的概率就很大,所以下边依次来分析基于
mysql数据库
、
Redis
、
MongoDB
实现的 “附近的人” 功能。
科普 :世界上标识一个位置,通用的做法就使用经、纬度。经度的范围在 (-180, 180],纬度的范围 在(-90, 90],纬度正负以赤道为界,北正南负,经度正负以本初子午线 (英国格林尼治天文台) 为界,东正西负。比如:望京摩托罗拉大厦的经、纬度(116.49141,40.01229)全是正数,就是因为我国位于东北半球。
一、“附近的人”原理
“附近的人”
也就是常说的
LBS
(Location Based Services,基于位置服务),它围绕用户当前地理位置数据而展开的服务,为用户提供精准的增值服务。
“附近的人” 核心思想如下:
- 以 “我” 为中心,搜索附近的用户
- 以 “我” 当前的地理位置为准,计算出别人和 “我” 之间的距离
-
按 “我” 与别人距离的远近排序,筛选出离我最近的用户或者商店等
二、什么是GeoHash算法?
在说
“附近的人”
功能的具体实现之前,先来认识一下
GeoHash
算法,因为后边会一直和它打交道。定位一个位置最好的办法就是用
经、纬度
标识,但
经、纬度
它是二维的,在进行位置计算的时候还是很麻烦,如果能通过某种方法将二维的
经、纬度
数据转换成一维的数据,那么比较起来就要容易的多,因此
GeoHash
算法应运而生。
GeoHash
算法将二维的经、纬度转换成一个字符串,例如:下图中9个
GeoHash
字符串代表了9个区域,每一个字符串代表了一矩形区域。而这个矩形区域内其他的点(经、纬度)都用同一个
GeoHash
字符串表示。
比如
:
WX4ER
区域内的用户搜索附近的餐厅数据,由于这区域内用户的
GeoHash
字符串都是
WX4ER
,故可以把
WX4ER
当作
key
,餐厅信息作为
value
进行缓存;而如果不使用
GeoHash
算法,区域内的用户请求餐厅数据,用户传来的经、纬度都是不同的,这样缓存不仅麻烦且数据量巨大。
GeoHash
字符串越长,表示的位置越精确,字符串长度越长代表在距离上的误差越小。下图
geohash
码精度表:
geohash码长度 | 宽度 | 高度 |
---|---|---|
1 | 5,009.4km | 4,992.6km |
2 | 1,252.3km | 624.1km |
3 | 156.5km | 156km |
4 | 39.1km | 19.5km |
5 | 4.9km | 4.9km |
6 | 1.2km | 609.4m |
7 | 152.9m | 152.4m |
8 | 38.2m | 19m |
9 | 4.8m | 4.8m |
10 | 1.2m | 59.5cm |
11 | 14.9cm | 14.9cm |
12 | 3.7cm | 1.9cm |
而且字符串越相似表示距离越相近,字符串前缀匹配越多的距离越近。比如:下边的经、纬度就代表了三家距离相近的餐厅。
商户 | 经纬度 | Geohash字符串 |
---|---|---|
串串香 | 116.402843,39.999375 | wx4er9v |
火锅 | 116.3967,39.99932 | wx4ertk |
烤肉 | 116.40382,39.918118 | wx4erfe |
让大家简单了解什么是
GeoHash
算法,方便后边内容展开,
GeoHash
算法内容比较高深,感兴趣的小伙伴自行深耕一下,这里不占用过多篇幅(其实是我懂得太肤浅,哭唧唧~)。
三、基于Mysql
此种方式是纯基于
mysql
实现的,未使用
GeoHash
算法。
1、设计思路
以用户为中心,假设给定一个500米的距离作为半径画一个圆,这个圆型区域内的所有用户就是符合用户要求的 “附近的人”。但有一个问题是圆形有弧度啊,直接搜索圆形区域难度太大,根本无法用经、纬度直接搜索。
但如果在圆形外套上一个正方形,通过获取用户经、纬度的最大最小值(经、纬度 + 距离),再根据最大最小值作为筛选条件,就很容易将正方形内的用户信息搜索出来。
那么问题又来了, 多出来一些面积肿么办?
我们来分析一下,多出来的这部分区域内的用户,到圆点的距离一定比圆的半径要大,那么我们就计算用户中心点与正方形内所有用户的距离,筛选出所有距离小于等于半径的用户,圆形区域内的所用户即符合要求的
“附近的人”
。
2、利弊分析
纯基于
mysql
实现
“附近的人”
,优点显而易见就是简单,只要建一张表存下用户的经、纬度信息即可。缺点也很明显,需要大量的计算两个点之间的距离,非常影响性能。
3、实现
创建一个简单的表用来存放用户的经、纬度属性。
1CREATE TABLE `nearby_user` (
2 `id` int(11) NOT NULL AUTO_INCREMENT,
3 `name` varchar(255) DEFAULT NULL COMMENT '名称',
4 `longitude` double DEFAULT NULL COMMENT '经度',
5 `latitude` double DEFAULT NULL COMMENT '纬度',
6 `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创建时间',
7 PRIMARY KEY (`id`)
8) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
计算两个点之间的距离,用了一个三方的类库,毕竟自己造的轮子不是特别圆,还有可能是方的,啊哈哈哈~
1
2 <groupId>com.spatial4j</groupId>
3 spatial4j</artifactId>
4 0.5</version>
5</dependency>
获取到外接正方形后,以正方形的最大最小经、纬度值搜索正方形区域内的用户,再剔除超过指定距离的用户,就是最终的
附近的人
。
1 private SpatialContext spatialContext = SpatialContext.GEO;
2
3 /**
4 * 获取附近 x 米的人
5 *
6 * @param distance 搜索距离范围 单位km
7 * @param userLng 当前用户的经度
8 * @param userLat 当前用户的纬度
9 */
10 @GetMapping("/nearby")
11 public String nearBySearch(@RequestParam("distance") double distance,
12 @RequestParam("userLng") double userLng,
13 @RequestParam("userLat") double userLat) {
14 //1.获取外接正方形
15 Rectangle rectangle = getRectangle(distance, userLng, userLat);
16 //2.获取位置在正方形内的所有用户
17 List users = userMapper.selectUser(rectangle.getMinX(), rectangle.getMaxX(), rectangle.getMinY(), rectangle.getMaxY());
18 //3.剔除半径超过指定距离的多余用户
19 users = users.stream()
20 .filter(a -> getDistance(a.getLongitude(), a.getLatitude(), userLng, userLat) <= distance)
21 .collect(Collectors.toList());
22 return JSON.toJSONString(users);
23 }
24
25 private Rectangle getRectangle(double distance, double userLng, double userLat) {
26 return spatialContext.getDistCalc()
27 .calcBoxByDistFromPt(spatialContext.makePoint(userLng, userLat),
28 distance * DistanceUtils.KM_TO_DEG, spatialContext, null);
29 }
由于用户间距离的排序是在业务代码中实现的,可以看到SQL语句也非常的简单。
1 <select id="selectUser" resultMap="BaseResultMap">
2 SELECT * FROM user
3 WHERE 1=1
4 and (longitude BETWEEN ${minlng} AND ${maxlng})
5 and (latitude BETWEEN ${minlat} AND ${maxlat})
6 </select>
7
四、Mysql + GeoHash
1、设计思路
这种方式的设计思路更简单,在存用户位置信息时,根据用户经、纬度属性计算出相应的
geohash
字符串。 注意
:在计算
geohash
字符串时,需要指定
geohash
字符串的精度,也就是
geohash
字符串的长度, 参考上边的
geohash
精度表
。
当需要获取
附近的人
,只需用当前用户
geohash
字符串,数据库通过
WHERE geohash Like 'geocode%
‘ 来查询
geohash
字符串相似的用户,然后计算当前用户与搜索出的用户距离,筛选出所有距离小于等于指定距离(附近500米)的,即
附近的人
。
2、利弊分析
利用
GeoHash
算法实现
“附近的人”
有一个问题,由于
geohash
算法将地图分为一个个矩形,对每个矩形进行编码,得到
geohash
字符串。可我当前的点与邻近的点很近,但恰好我们分别在两个区域,明明就在眼前的点偏偏搜不到,实实在在的灯下黑。
如何解决这一问题?
为了避免类似邻近两点在不同区域内,我们就需要同时获取当前点(
WX4G0
)所在区域附近
8个
区域的
geohash
码,一并进行筛选比较。
3、实现
同样要设计一张表存用户的经、纬度信息,但区别是要多一个
geo_code
字段,存放geohash字符串,此字段通过用户经、纬度属性计算出。使用频繁的字段建议加上索引。
1CREATE TABLE `nearby_user_geohash` (
2 `id` int(11) NOT NULL AUTO_INCREMENT,
3 `name` varchar(255) DEFAULT NULL COMMENT '名称',
4 `longitude` double DEFAULT NULL COMMENT '经度',
5 `latitude` double DEFAULT NULL COMMENT '纬度',
6 `geo_code` varchar(64) DEFAULT NULL COMMENT '经纬度所计算的geohash码',
7 `create_time` datetime DEFAULT NULL ON UPDATE CURRENT_TIMESTAMP COMMENT '创建时间',
8 PRIMARY KEY (`id`),
9 KEY `index_geo_hash` (`geo_code`)
10) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
首先根据用户经、纬度信息,在指定精度后计算用户坐标的
geoHash
码,再获取到用户周边8个方位的
geoHash
码在数据库中搜索用户,最后过滤掉超出给定距离(500米内)的用户。
1 private SpatialContext spatialContext = SpatialContext.GEO;
2
3 /***
4 * 添加用户
5 * @return
6 */
7 @PostMapping("/addUser")
8 public boolean add(@RequestBody UserGeohash user) {
9 //默认精度12位
10 String geoHashCode = GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude());
11 return userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now()));
12 }
13
14
15/**
16 * 获取附近指定范围的人
17 *
18 * @param distance 距离范围(附近多远的用户) 单位km
19 * @param len geoHash的精度(几位的字符串)
20 * @param userLng 当前用户的经度
21 * @param userLat 当前用户的纬度
22 * @return json
23 */
24 @GetMapping("/nearby")
25 public String nearBySearch(@RequestParam("distance") double distance,
26 @RequestParam("len") int len,
27 @RequestParam("userLng") double userLng,
28 @RequestParam("userLat") double userLat) {
29
30
31 //1.根据要求的范围,确定geoHash码的精度,获取到当前用户坐标的geoHash码
32 GeoHash geoHash = GeoHash.withCharacterPrecision(userLat, userLng, len);
33 //2.获取到用户周边8个方位的geoHash码
34 GeoHash[] adjacent = geoHash.getAdjacent();
35
36 QueryWrapper queryWrapper = new QueryWrapper()
37 .likeRight("geo_code",geoHash.toBase32());
38 Stream.of(adjacent).forEach(a -> queryWrapper.or().likeRight("geo_code",a.toBase32()));
39
40 //3.匹配指定精度的geoHash码
41 List users = userGeohashService.list(queryWrapper);
42 //4.过滤超出距离的
43 users = users.stream()
44 .filter(a ->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<= distance)
45 .collect(Collectors.toList());
46 return JSON.toJSONString(users);
47 }
48
49
50 /***
51 * 球面中,两点间的距离
52 * @param longitude 经度1
53 * @param latitude 纬度1
54 * @param userLng 经度2
55 * @param userLat 纬度2
56 * @return 返回距离,单位km
57 */
58 private double getDistance(Double longitude, Double latitude, double userLng, double userLat) {
59 return spatialContext.calcDistance(spatialContext.makePoint(userLng, userLat),
60 spatialContext.makePoint(longitude, latitude)) * DistanceUtils.DEG_TO_KM;
61 }
五、Redis + GeoHash
Redis 3.2
版本以后,基于
geohash
和数据结构
Zset
提供了地理位置相关功能。通过上边两种
mysql
的实现方式发现,
附近的人
功能是明显的读多写少场景,所以用
redis
性能更会有很大的提升。
1、设计思路
redis
实现
附近的人
功能主要通过
Geo
模块的六个命令。
-
GEOADD
:将给定的位置对象(纬度、经度、名字)添加到指定的key; -
GEOPOS
:从key里面返回所有给定位置对象的位置(经度和纬度); -
GEODIST
:返回两个给定位置之间的距离; -
GEOHASH
:返回一个或多个位置对象的Geohash表示; -
GEORADIUS
:以给定的经纬度为中心,返回目标集合中与中心的距离不超过给定最大距离的所有位置对象; -
GEORADIUSBYMEMBER
:以给定的位置对象为中心,返回与其距离不超过给定最大距离的所有位置对象。
以
GEOADD
命令和
GEORADIUS
命令简单举例:
1GEOADD key longitude latitude member [longitude latitude member ...]
其中,
key
为集合名称,
member
为该经纬度所对应的对象。
GEOADD
添加多个商户“火锅店”位置信息:
1GEOADD hotel 119.98866180732716 30.27465803229662 火锅店
GEORADIUS
根据给定的经纬度为中心,获取目标集合中与中心的距离不超过给定最大距离(500米内)的所有位置对象,也就是
“附近的人”
。
1GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [ASC|DESC] [COUNT count] [STORE key] [STORedisT key]
范围单位:
m
|
km
|
ft
|
mi
–> 米 | 千米 | 英尺 | 英里。
-
WITHDIST
:在返回位置对象的同时,将位置对象与中心之间的距离也一并返回。距离的单位和用户给定的范围单位保持一致。 -
WITHCOORD
:将位置对象的经度和维度也一并返回。 -
WITHHASH
:以 52 位有符号整数的形式,返回位置对象经过原始 geohash 编码的有序集合分值。这个选项主要用于底层应用或者调试,实际中的作用并不大。 -
ASC | DESC
:从近到远返回位置对象元素 | 从远到近返回位置对象元素。 -
COUNT count
:选取前N个匹配位置对象元素。(不设置则返回所有元素) -
STORE key
:将返回结果的地理位置信息保存到指定key。 -
STORedisT key
:将返回结果离中心点的距离保存到指定key。
例如下边命令:获取当前位置周边500米内的所有饭店。
1GEORADIUS hotel 119.98866180732716 30.27465803229662 500 m WITHCOORD
Redis
内部使用有序集合(
zset
)保存用户的位置信息,
zset
中每个元素都是一个带位置的对象,元素的
score
值为通过经、纬度计算出的52位
geohash
值。
2、利弊分析
redis
实现
附近的人
效率比较高,集成也比较简单,而且还支持对距离排序。不过,结果存在一定的误差,要想让结果更加精确,还需要手动将用户中心位置与其他用户位置计算距离后,再一次进行筛选。
3、实现
以下就是
Java
redis
实现版本,代码非常的简洁。
1 @Autowired
2 private RedisTemplate<String, Object> redisTemplate;
3
4 //GEO相关命令用到的KEY
5 private final static String KEY = "user_info";
6
7 public boolean save(User user) {
8 Long flag = redisTemplate.opsForGeo().add(KEY, new RedisGeoCommands.GeoLocation(
9 user.getName(),
10 new Point(user.getLongitude(), user.getLatitude()))
11 );
12 return flag != null && flag > 0;
13 }
14
15 /**
16 * 根据当前位置获取附近指定范围内的用户
17 * @param distance 指定范围 单位km ,可根据{@link org.springframework.data.geo.Metrics} 进行设置
18 * @param userLng 用户经度
19 * @param userLat 用户纬度
20 * @return
21 */
22 public String nearBySearch(double distance, double userLng, double userLat) {
23 List users = new ArrayList();
24 // 1.GEORADIUS获取附近范围内的信息
25 GeoResults<RedisGeoCommands.GeoLocation<Object>> reslut =
26 redisTemplate.opsForGeo().radius(KEY,
27 new Circle(new Point(userLng, userLat), new Distance(distance, Metrics.KILOMETERS)),
28 RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs()
29 .includeDistance()
30 .includeCoordinates().sortAscending());
31 //2.收集信息,存入list
32 List<GeoResult<RedisGeoCommands.GeoLocation<Object>>> content = reslut.getContent();
33 //3.过滤掉超过距离的数据
34 content.forEach(a-> users.add(
35 new User().setDistance(a.getDistance().getValue())
36 .setLatitude(a.getContent().getPoint().getX())
37 .setLongitude(a.getContent().getPoint().getY())));
38 return JSON.toJSONString(users);
39 }
六、MongoDB + 2d索引
1、设计思路
MongoDB
实现附近的人,主要是通过它的两种地理空间索引
2dsphere
和
2d
。两种索引的底层依然是基于
Geohash
来进行构建的。但与国际通用的
Geohash
还有一些不同,具体参考
官方文档
。
2dsphere
索引仅支持球形表面的几何形状查询。
2d
索引支持平面几何形状和一些球形查询。虽然
2d
索引支持某些球形查询,但
2d
索引对这些球形查询时,可能会出错。所以球形查询尽量选择
2dsphere
索引。
尽管两种索引的方式不同,但只要坐标跨度不太大,这两个索引计算出的距离相差几乎可以忽略不计。
2、实现
首先插入一批位置数据到
MongoDB
,
collection
为起名
hotel
,相当于
MySQL
的表名。两个字段
name
名称,
location
为经、纬度数据对。
1db.hotel.insertMany([
2 {'name':'hotel1', location:[115.993121,28.676436]},
3 {'name':'hotel2', location:[116.000093,28.679402]},
4 {'name':'hotel3', location:[115.999967,28.679743]},
5 {'name':'hotel4', location:[115.995593,28.681632]},
6 {'name':'hotel5', location:[115.975543,28.679509]},
7 {'name':'hotel6', location:[115.968428,28.669368]},
8 {'name':'hotel7', location:[116.035262,28.677037]},
9 {'name':'hotel8', location:[116.024770,28.68667]},
10 {'name':'hotel9', location:[116.002384,28.683865]},
11 {'name':'hotel10', location:[116.000821,28.68129]},
12])
接下来我们给
location
字段创建一个
2d
索引,索引的精度通过
bits
来指定,
bits
越大,索引的精度就越高。
1db.coll.createIndex({'location':"2d"}, {"bits":11111})
用
geoNear
命令测试一下,
near
当前坐标(经、纬度),
spherical
是否计算球面距离,
distanceMultiplier
地球半径,单位是米,默认6378137,
maxDistance
过滤条件(指定距离内的用户),开启弧度需除
distanceMultiplier
,
distanceField
计算出的两点间距离,字段别名(随意取名)。
1db.hotel.aggregate({
2 $geoNear:{
3 near: [115.999567,28.681813], // 当前坐标
4 spherical: true, // 计算球面距离
5 distanceMultiplier: 6378137, // 地球半径,单位是米,那么的除的记录也是米
6 maxDistance: 2000/6378137, // 过滤条件2000米内,需要弧度
7 distanceField: "distance" // 距离字段别名
8 }
9})
看到结果中有符合条件的数据,还多出一个字段
distance
刚才设置的别名,代表两点间的距离。
1{ "_id" : ObjectId("5e96a5c91b8d4ce765381e58"), "name" : "hotel10", "location" : [ 116.000821, 28.68129 ], "distance" : 135.60095397487655 }
2{ "_id" : ObjectId("5e96a5c91b8d4ce765381e51"), "name" : "hotel3", "location" : [ 115.999967, 28.679743 ], "distance" : 233.71915803517447 }
3{ "_id" : ObjectId("5e96a5c91b8d4ce765381e50"), "name" : "hotel2", "location" : [ 116.000093, 28.679402 ], "distance" : 273.26317035334176 }
4{ "_id" : ObjectId("5e96a5c91b8d4ce765381e57"), "name" : "hotel9", "location" : [ 116.002384, 28.683865 ], "distance" : 357.5791936927476 }
5{ "_id" : ObjectId("5e96a5c91b8d4ce765381e52"), "name" : "hotel4", "location" : [ 115.995593, 28.681632 ], "distance" : 388.62555058249967 }
6{ "_id" : ObjectId("5e96a5c91b8d4ce765381e4f"), "name" : "hotel1", "location" : [ 115.993121, 28.676436 ], "distance" : 868.6740526419927 }
总结
本文重点并不是在具体实现,旨在给大家提供一些设计思路,面试中可能你对某一项技术了解的并不深入,但如果你的知识面宽,可以从多方面说出多种设计的思路,能够侃侃而谈,那么会给面试官极大的好感度,拿到offer的概率就会高很多。而且
“附近的人”
功能使用的场景比较多,尤其是像电商平台应用更为广泛,所以想要进大厂的同学,这类的知识点还是应该有所了解的。
代码实现借鉴了一位大佬的开源项目,这里有前三种实现方式的demo,感兴趣的小伙伴可以学习一下,GitHub地址:
https://github.com/larscheng/larscheng-learning-demo/tree/master/NearbySearch
,。
END
和一些志同道合的小伙伴们,共同建了一个技术交流群,一起探讨技术、分享技术资料,旨在共同学习进步,如果感兴趣就
扫码
加入
我们吧!
小福利:
获取到一些付费课程 ,嘘~,
免费
送给小伙伴们。关注公众号回复【
666
】自行领取