空间布隆过滤器,可以在不经过地图服务提供商的情况下,告知用户其是否在某位置附近。
如果你不知道什么是布隆过滤器,请看看我写的这篇文章:Bloom Filter
构建
给定集合:,其中每一项都是一个感兴趣的目标地点
在添加元素时,将 中的所有元素设为1,将 中的所有元素设为2,直到集合S被添加完
在判断时,找到对应最小的值
代码实现
原作者的代码仓库
我的Java实现
SBF类需要的参数:
- byteSet:用于存储地区信息
- cellSize:一个单位占多少字节。在这里考虑区域数可能超过255,在超过255时取2字节作为一个单位
- m:数组长度,表示包含多少个单位
- k:哈希函数个数
- 还有一些统计信息,如插入次数,冲突数,等等