引言

昨天一位公眾號粉絲和我討論了一道面試題，個人覺得比較有意義，這里整理了一下分享給大家，愿小伙伴們面試路上少踩坑。面試題目比較簡單：“讓你實現(xiàn)一個附近的人功能，你有什么方案？”，這道題其實主要還是考察大家對于技術(shù)的廣度，本文介紹幾種方案，給大家一點思路，避免在面試過程中語塞而影響面試結(jié)果，如有不嚴(yán)謹(jǐn)之處，還望親人們溫柔指正！

“附近的人”?功能生活中是比較常用的，像外賣app附近的餐廳，共享單車app里附近的車輛。既然常用面試被問的概率就很大，所以下邊依次來分析基于mysql數(shù)據(jù)庫、Redis、?MongoDB實現(xiàn)的 “附近的人” 功能。

?

科普：世界上標(biāo)識一個位置，通用的做法就使用經(jīng)、緯度。經(jīng)度的范圍在 (-180, 180]，緯度的范圍 在(-90, 90]，緯度正負(fù)以赤道為界，北正南負(fù)，經(jīng)度正負(fù)以本初子午線 (英國格林尼治天文臺) 為界，東正西負(fù)。比如：望京摩托羅拉大廈的經(jīng)、緯度（116.49141，40.01229）全是正數(shù)，就是因為我國位于東北半球。

一、“附近的人”原理

“附近的人”?也就是常說的?LBS?(Location Based Services，基于位置服務(wù))，它圍繞用戶當(dāng)前地理位置數(shù)據(jù)而展開的服務(wù)，為用戶提供精準(zhǔn)的增值服務(wù)。

“附近的人” 核心思想如下：

以 “我” 為中心，搜索附近的用戶

以 “我” 當(dāng)前的地理位置為準(zhǔn)，計算出別人和 “我” 之間的距離

按 “我” 與別人距離的遠(yuǎn)近排序，篩選出離我最近的用戶或者商店等

二、什么是GeoHash算法？

在說?“附近的人”?功能的具體實現(xiàn)之前，先來認(rèn)識一下GeoHash?算法，因為后邊會一直和它打交道。定位一個位置最好的辦法就是用經(jīng)、緯度標(biāo)識，但經(jīng)、緯度它是二維的，在進(jìn)行位置計算的時候還是很麻煩，如果能通過某種方法將二維的經(jīng)、緯度數(shù)據(jù)轉(zhuǎn)換成一維的數(shù)據(jù)，那么比較起來就要容易的多，因此GeoHash算法應(yīng)運而生。

GeoHash算法將二維的經(jīng)、緯度轉(zhuǎn)換成一個字符串，例如：下圖中9個GeoHash字符串代表了9個區(qū)域，每一個字符串代表了一矩形區(qū)域。而這個矩形區(qū)域內(nèi)其他的點（經(jīng)、緯度）都用同一個GeoHash字符串表示。

比如：WX4ER區(qū)域內(nèi)的用戶搜索附近的餐廳數(shù)據(jù)，由于這區(qū)域內(nèi)用戶的GeoHash字符串都是WX4ER，故可以把WX4ER當(dāng)作key，餐廳信息作為value進(jìn)行緩存；而如果不使用GeoHash算法，區(qū)域內(nèi)的用戶請求餐廳數(shù)據(jù)，用戶傳來的經(jīng)、緯度都是不同的，這樣緩存不僅麻煩且數(shù)據(jù)量巨大。

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

而且字符串越相似表示距離越相近，字符串前綴匹配越多的距離越近。比如：下邊的經(jīng)、緯度就代表了三家距離相近的餐廳。

商戶經(jīng)緯度Geohash字符串

串串香	116.402843,39.999375	wx4er9v
火鍋	116.3967,39.99932	wx4ertk
烤肉	116.40382,39.918118	wx4erfe

讓大家簡單了解什么是GeoHash算法，方便后邊內(nèi)容展開，GeoHash算法內(nèi)容比較高深，感興趣的小伙伴自行深耕一下，這里不占用過多篇幅（其實是我懂得太膚淺，哭唧唧~）。

三、基于Mysql

此種方式是純基于mysql實現(xiàn)的，未使用GeoHash算法。

1、設(shè)計思路

以用戶為中心，假設(shè)給定一個500米的距離作為半徑畫一個圓，這個圓型區(qū)域內(nèi)的所有用戶就是符合用戶要求的 “附近的人”。但有一個問題是圓形有弧度啊，直接搜索圓形區(qū)域難度太大，根本無法用經(jīng)、緯度直接搜索。

但如果在圓形外套上一個正方形，通過獲取用戶經(jīng)、緯度的最大最小值（經(jīng)、緯度 + 距離），再根據(jù)最大最小值作為篩選條件，就很容易將正方形內(nèi)的用戶信息搜索出來。

那么問題又來了，多出來一些面積腫么辦？

我們來分析一下，多出來的這部分區(qū)域內(nèi)的用戶，到圓點的距離一定比圓的半徑要大，那么我們就計算用戶中心點與正方形內(nèi)所有用戶的距離，篩選出所有距離小于等于半徑的用戶，圓形區(qū)域內(nèi)的所用戶即符合要求的“附近的人”。

2、利弊分析

純基于?mysql?實現(xiàn)?“附近的人”，優(yōu)點顯而易見就是簡單，只要建一張表存下用戶的經(jīng)、緯度信息即可。缺點也很明顯，需要大量的計算兩個點之間的距離，非常影響性能。

3、實現(xiàn)

創(chuàng)建一個簡單的表用來存放用戶的經(jīng)、緯度屬性。

CREATE?TABLE?`nearby_user`?(`id`?int(11)?NOT?NULL?AUTO_INCREMENT,`name`?varchar(255)?DEFAULT?NULL?COMMENT?'名稱',`longitude`?double?DEFAULT?NULL?COMMENT?'經(jīng)度',`latitude`?double?DEFAULT?NULL?COMMENT?'緯度',`create_time`?datetime?DEFAULT?NULL?ON?UPDATE?CURRENT_TIMESTAMP?COMMENT?'創(chuàng)建時間',PRIMARY?KEY?(`id`) )?ENGINE=InnoDB?DEFAULT?CHARSET=utf8mb4;

計算兩個點之間的距離，用了一個三方的類庫，畢竟自己造的輪子不是特別圓，還有可能是方的，啊哈哈哈~

<dependency><groupId>com.spatial4j</groupId><artifactId>spatial4j</artifactId><version>0.5</version> </dependency>

獲取到外接正方形后，以正方形的最大最小經(jīng)、緯度值搜索正方形區(qū)域內(nèi)的用戶，再剔除超過指定距離的用戶，就是最終的附近的人。

????private?SpatialContext?spatialContext?=?SpatialContext.GEO;????/***?獲取附近?x?米的人**?@param?distance?搜索距離范圍?單位km*?@param?userLng??當(dāng)前用戶的經(jīng)度*?@param?userLat??當(dāng)前用戶的緯度*/@GetMapping("/nearby")public?String?nearBySearch(@RequestParam("distance")?double?distance,@RequestParam("userLng")?double?userLng,@RequestParam("userLat")?double?userLat)?{//1.獲取外接正方形Rectangle?rectangle?=?getRectangle(distance,?userLng,?userLat);//2.獲取位置在正方形內(nèi)的所有用戶List<User>?users?=?userMapper.selectUser(rectangle.getMinX(),?rectangle.getMaxX(),?rectangle.getMinY(),?rectangle.getMaxY());//3.剔除半徑超過指定距離的多余用戶users?=?users.stream().filter(a?->?getDistance(a.getLongitude(),?a.getLatitude(),?userLng,?userLat)?<=?distance).collect(Collectors.toList());return?JSON.toJSONString(users);}private?Rectangle?getRectangle(double?distance,?double?userLng,?double?userLat)?{return?spatialContext.getDistCalc().calcBoxByDistFromPt(spatialContext.makePoint(userLng,?userLat),?distance?*?DistanceUtils.KM_TO_DEG,?spatialContext,?null);}

由于用戶間距離的排序是在業(yè)務(wù)代碼中實現(xiàn)的，可以看到SQL語句也非常的簡單。

????<select?id="selectUser"?resultMap="BaseResultMap">SELECT?*?FROM?userWHERE?1=1and?(longitude?BETWEEN?${minlng}?AND?${maxlng})and?(latitude?BETWEEN?${minlat}?AND?${maxlat})</select>

四、Mysql + GeoHash

1、設(shè)計思路

這種方式的設(shè)計思路更簡單，在存用戶位置信息時，根據(jù)用戶經(jīng)、緯度屬性計算出相應(yīng)的geohash字符串。注意：在計算geohash字符串時，需要指定geohash字符串的精度，也就是geohash字符串的長度，參考上邊的geohash精度表。

當(dāng)需要獲取附近的人，只需用當(dāng)前用戶geohash字符串，數(shù)據(jù)庫通過WHERE geohash Like 'geocode%' 來查詢geohash字符串相似的用戶，然后計算當(dāng)前用戶與搜索出的用戶距離，篩選出所有距離小于等于指定距離（附近500米）的，即附近的人。

2、利弊分析

利用GeoHash算法實現(xiàn)“附近的人”有一個問題，由于geohash算法將地圖分為一個個矩形，對每個矩形進(jìn)行編碼，得到geohash字符串。可我當(dāng)前的點與鄰近的點很近，但恰好我們分別在兩個區(qū)域，明明就在眼前的點偏偏搜不到，實實在在的燈下黑。

如何解決這一問題？

為了避免類似鄰近兩點在不同區(qū)域內(nèi)，我們就需要同時獲取當(dāng)前點（WX4G0）所在區(qū)域附近?8個區(qū)域的geohash碼，一并進(jìn)行篩選比較。

3、實現(xiàn)

同樣要設(shè)計一張表存用戶的經(jīng)、緯度信息，但區(qū)別是要多一個geo_code字段，存放geohash字符串，此字段通過用戶經(jīng)、緯度屬性計算出。使用頻繁的字段建議加上索引。

CREATE?TABLE?`nearby_user_geohash`?(`id`?int(11)?NOT?NULL?AUTO_INCREMENT,`name`?varchar(255)?DEFAULT?NULL?COMMENT?'名稱',`longitude`?double?DEFAULT?NULL?COMMENT?'經(jīng)度',`latitude`?double?DEFAULT?NULL?COMMENT?'緯度',`geo_code`?varchar(64)?DEFAULT?NULL?COMMENT?'經(jīng)緯度所計算的geohash碼',`create_time`?datetime?DEFAULT?NULL?ON?UPDATE?CURRENT_TIMESTAMP?COMMENT?'創(chuàng)建時間',PRIMARY?KEY?(`id`),KEY?`index_geo_hash`?(`geo_code`) )?ENGINE=InnoDB?DEFAULT?CHARSET=utf8mb4;

首先根據(jù)用戶經(jīng)、緯度信息，在指定精度后計算用戶坐標(biāo)的geoHash碼，再獲取到用戶周邊8個方位的geoHash碼在數(shù)據(jù)庫中搜索用戶，最后過濾掉超出給定距離（500米內(nèi)）的用戶。

private?SpatialContext?spatialContext?=?SpatialContext.GEO;/****?添加用戶*?@return*/@PostMapping("/addUser")public?boolean?add(@RequestBody?UserGeohash?user)?{//默認(rèn)精度12位String?geoHashCode?=?GeohashUtils.encodeLatLon(user.getLatitude(),user.getLongitude());return?userGeohashService.save(user.setGeoCode(geoHashCode).setCreateTime(LocalDateTime.now()));}/***?獲取附近指定范圍的人**?@param?distance?距離范圍（附近多遠(yuǎn)的用戶）?單位km*?@param?len??????geoHash的精度（幾位的字符串）*?@param?userLng??當(dāng)前用戶的經(jīng)度*?@param?userLat??當(dāng)前用戶的緯度*?@return?json*/@GetMapping("/nearby")public?String?nearBySearch(@RequestParam("distance")?double?distance,@RequestParam("len")?int?len,@RequestParam("userLng")?double?userLng,@RequestParam("userLat")?double?userLat)?{//1.根據(jù)要求的范圍，確定geoHash碼的精度，獲取到當(dāng)前用戶坐標(biāo)的geoHash碼GeoHash?geoHash?=?GeoHash.withCharacterPrecision(userLat,?userLng,?len);//2.獲取到用戶周邊8個方位的geoHash碼GeoHash[]?adjacent?=?geoHash.getAdjacent();QueryWrapper<UserGeohash>?queryWrapper?=?new?QueryWrapper<UserGeohash>().likeRight("geo_code",geoHash.toBase32());Stream.of(adjacent).forEach(a?->?queryWrapper.or().likeRight("geo_code",a.toBase32()));//3.匹配指定精度的geoHash碼List<UserGeohash>?users?=?userGeohashService.list(queryWrapper);//4.過濾超出距離的users?=?users.stream().filter(a?->getDistance(a.getLongitude(),a.getLatitude(),userLng,userLat)<=?distance).collect(Collectors.toList());return?JSON.toJSONString(users);}/****?球面中，兩點間的距離*?@param?longitude?經(jīng)度1*?@param?latitude??緯度1*?@param?userLng???經(jīng)度2*?@param?userLat???緯度2*?@return?返回距離，單位km*/private?double?getDistance(Double?longitude,?Double?latitude,?double?userLng,?double?userLat)?{return?spatialContext.calcDistance(spatialContext.makePoint(userLng,?userLat),spatialContext.makePoint(longitude,?latitude))?*?DistanceUtils.DEG_TO_KM;}

五、Redis + GeoHash

Redis 3.2版本以后，基于geohash和數(shù)據(jù)結(jié)構(gòu)Zset提供了地理位置相關(guān)功能。通過上邊兩種mysql的實現(xiàn)方式發(fā)現(xiàn)，附近的人功能是明顯的讀多寫少場景，所以用redis性能更會有很大的提升。

1、設(shè)計思路

redis?實現(xiàn)附近的人功能主要通過Geo模塊的六個命令。

• GEOADD：將給定的位置對象（緯度、經(jīng)度、名字）添加到指定的key;

• GEOPOS：從key里面返回所有給定位置對象的位置（經(jīng)度和緯度）;

• GEODIST：返回兩個給定位置之間的距離;

• GEOHASH：返回一個或多個位置對象的Geohash表示;

• GEORADIUS：以給定的經(jīng)緯度為中心，返回目標(biāo)集合中與中心的距離不超過給定最大距離的所有位置對象;

• GEORADIUSBYMEMBER：以給定的位置對象為中心，返回與其距離不超過給定最大距離的所有位置對象。

以GEOADD?命令和GEORADIUS?命令簡單舉例：

GEOADD?key?longitude?latitude?member?[longitude?latitude?member?...]

其中，key為集合名稱，member為該經(jīng)緯度所對應(yīng)的對象。

GEOADD?添加多個商戶“火鍋店”位置信息：

GEOADD?hotel?119.98866180732716????30.27465803229662?火鍋店

GEORADIUS?根據(jù)給定的經(jīng)緯度為中心，獲取目標(biāo)集合中與中心的距離不超過給定最大距離（500米內(nèi)）的所有位置對象，也就是“附近的人”。

GEORADIUS?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：將位置對象的經(jīng)度和維度也一并返回。

• WITHHASH：以 52 位有符號整數(shù)的形式，返回位置對象經(jīng)過原始 geohash 編碼的有序集合分值。這個選項主要用于底層應(yīng)用或者調(diào)試，實際中的作用并不大。

• ASC | DESC：從近到遠(yuǎn)返回位置對象元素 | 從遠(yuǎn)到近返回位置對象元素。

• COUNT count：選取前N個匹配位置對象元素。（不設(shè)置則返回所有元素）

• STORE key：將返回結(jié)果的地理位置信息保存到指定key。

• STORedisT key：將返回結(jié)果離中心點的距離保存到指定key。

例如下邊命令：獲取當(dāng)前位置周邊500米內(nèi)的所有飯店。

GEORADIUS?hotel?119.98866180732716????30.27465803229662?500?m?WITHCOORD

Redis內(nèi)部使用有序集合(zset)保存用戶的位置信息，zset中每個元素都是一個帶位置的對象，元素的score值為通過經(jīng)、緯度計算出的52位geohash值。

2、利弊分析

redis實現(xiàn)附近的人效率比較高，集成也比較簡單，而且還支持對距離排序。不過，結(jié)果存在一定的誤差，要想讓結(jié)果更加精確，還需要手動將用戶中心位置與其他用戶位置計算距離后，再一次進(jìn)行篩選。

3、實現(xiàn)

以下就是Java?redis實現(xiàn)版本，代碼非常的簡潔。

@Autowiredprivate?RedisTemplate<String,?Object>?redisTemplate;//GEO相關(guān)命令用到的KEYprivate?final?static?String?KEY?=?"user_info";public?boolean?save(User?user)?{Long?flag?=?redisTemplate.opsForGeo().add(KEY,?new?RedisGeoCommands.GeoLocation<>(user.getName(),?new?Point(user.getLongitude(),?user.getLatitude())));return?flag?!=?null?&&?flag?>?0;}/***?根據(jù)當(dāng)前位置獲取附近指定范圍內(nèi)的用戶*?@param?distance?指定范圍?單位km?，可根據(jù){@link?org.springframework.data.geo.Metrics}?進(jìn)行設(shè)置*?@param?userLng?用戶經(jīng)度*?@param?userLat?用戶緯度*?@return*/public?String?nearBySearch(double?distance,?double?userLng,?double?userLat)?{List<User>?users?=?new?ArrayList<>();//?1.GEORADIUS獲取附近范圍內(nèi)的信息GeoResults<RedisGeoCommands.GeoLocation<Object>>?reslut?=?redisTemplate.opsForGeo().radius(KEY,?new?Circle(new?Point(userLng,?userLat),?new?Distance(distance,?Metrics.KILOMETERS)),RedisGeoCommands.GeoRadiusCommandArgs.newGeoRadiusArgs().includeDistance().includeCoordinates().sortAscending());//2.收集信息，存入listList<GeoResult<RedisGeoCommands.GeoLocation<Object>>>?content?=?reslut.getContent();//3.過濾掉超過距離的數(shù)據(jù)content.forEach(a->?users.add(new?User().setDistance(a.getDistance().getValue()).setLatitude(a.getContent().getPoint().getX()).setLongitude(a.getContent().getPoint().getY())));return?JSON.toJSONString(users);}

六、MongoDB + 2d索引

1、設(shè)計思路

MongoDB實現(xiàn)附近的人，主要是通過它的兩種地理空間索引?2dsphere?和?2d。兩種索引的底層依然是基于Geohash來進(jìn)行構(gòu)建的。但與國際通用的Geohash還有一些不同，具體參考官方文檔。

2dsphere?索引僅支持球形表面的幾何形狀查詢。

2d?索引支持平面幾何形狀和一些球形查詢。雖然2d?索引支持某些球形查詢，但?2d?索引對這些球形查詢時，可能會出錯。所以球形查詢盡量選擇?2dsphere索引。

盡管兩種索引的方式不同，但只要坐標(biāo)跨度不太大，這兩個索引計算出的距離相差幾乎可以忽略不計。

2、實現(xiàn)

首先插入一批位置數(shù)據(jù)到MongoDB，?collection為起名?hotel，相當(dāng)于MySQL的表名。兩個字段name名稱，location?為經(jīng)、緯度數(shù)據(jù)對。

db.hotel.insertMany([{'name':'hotel1',??location:[115.993121,28.676436]},{'name':'hotel2',??location:[116.000093,28.679402]},{'name':'hotel3',??location:[115.999967,28.679743]},{'name':'hotel4',??location:[115.995593,28.681632]},{'name':'hotel5',??location:[115.975543,28.679509]},{'name':'hotel6',??location:[115.968428,28.669368]},{'name':'hotel7',??location:[116.035262,28.677037]},{'name':'hotel8',??location:[116.024770,28.68667]},{'name':'hotel9',??location:[116.002384,28.683865]},{'name':'hotel10',?location:[116.000821,28.68129]}, ])

接下來我們給?location?字段創(chuàng)建一個2d索引，索引的精度通過bits來指定，bits越大，索引的精度就越高。

db.coll.createIndex({'location':"2d"},?{"bits":11111})

用geoNear命令測試一下，?near?當(dāng)前坐標(biāo)（經(jīng)、緯度），spherical?是否計算球面距離，distanceMultiplier地球半徑，單位是米，默認(rèn)6378137，?maxDistance?過濾條件（指定距離內(nèi)的用戶），開啟弧度需除distanceMultiplier，distanceField?計算出的兩點間距離，字段別名（隨意取名）。

db.hotel.aggregate({$geoNear:{near:?[115.999567,28.681813],?//?當(dāng)前坐標(biāo)spherical:?true,?//?計算球面距離distanceMultiplier:?6378137,?//?地球半徑,單位是米,那么的除的記錄也是米maxDistance:?2000/6378137,?//?過濾條件2000米內(nèi)，需要弧度distanceField:?"distance"?//?距離字段別名} })

看到結(jié)果中有符合條件的數(shù)據(jù)，還多出一個字段distance?剛才設(shè)置的別名，代表兩點間的距離。

{?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e58"),?"name"?:?"hotel10",?"location"?:?[?116.000821,?28.68129?],?"distance"?:?135.60095397487655?} {?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e51"),?"name"?:?"hotel3",?"location"?:?[?115.999967,?28.679743?],?"distance"?:?233.71915803517447?} {?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e50"),?"name"?:?"hotel2",?"location"?:?[?116.00009,?28.679402?],?"distance"?:?273.26317035334176?} {?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e57"),?"name"?:?"hotel9",?"location"?:?[?116.00238,?28.683865?],?"distance"?:?357.5791936927476?} {?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e52"),?"name"?:?"hotel4",?"location"?:?[?115.995593,?28.681632?],?"distance"?:?388.62555058249967?} {?"_id"?:?ObjectId("5e96a5c91b8d4ce765381e4f"),?"name"?:?"hotel1",?"location"?:?[?115.993121,?28.676436?],?"distance"?:?868.6740526419927?}

總結(jié)

本文重點并不是在具體實現(xiàn)，旨在給大家提供一些設(shè)計思路，面試中可能你對某一項技術(shù)了解的并不深入，但如果你的知識面寬，可以從多方面說出多種設(shè)計的思路，能夠侃侃而談，那么會給面試官極大的好感度，拿到offer的概率就會高很多。而且“附近的人”?功能使用的場景比較多，尤其是像電商平臺應(yīng)用更為廣泛，所以想要進(jìn)大廠的同學(xué)，這類的知識點還是應(yīng)該有所了解的。

總結(jié)

以上是生活随笔為你收集整理的一口气说出 4种 “附近的人” 实现方式，面试官笑了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。