分类 算法 下的文章

原文:https://juejin.im/post/5cd823f9e51d453abb1397d7

一、前言

最近有个需求,要计算出客户坐标附近5公里的所有门店,并按照步行距离排序。
最直接的方法就是遍历该城市下的所有门店,但是该方法明显不可取,因为在门店数量巨大,且还需要计算步行距离并排序的情况下,时间复杂度过高。
突然想到当年做图像遇见一个问题:给定一个视频中连续的三千帧,但是已经乱序,告诉你第一帧,将这三千帧进行排序。遍历图像的所有像素点同样不可取,当时的解决方案是利用感知哈希计算出所有图像的指纹,接着利用明氏距离计算距离第一张最近的图像作为第二张,然后计算距离第二张最近的作为第三张,以此类推。
同样,肯定也有哈希方法可将地理位置转换成某种编码,并且编码可用于地理计算。它就是 GeoHash




- 阅读剩余部分 -

原文:如何判断一个元素在亿级数据中是否存在?

Bloom Filter 原理

官方的说法是:它是一个保存了很长的二级制向量,同时结合 Hash 函数实现的。

听起来比较绕,但是通过一个图就比较容易理解了。
bloom filter原理

如图所示:

  • 首先需要初始化一个二进制的数组,长度设为 L(图中为 8),同时初始值全为 0 。
  • 当写入一个 A1=1000 的数据时,需要进行 H 次 hash 函数的运算(这里为 2 次);与 HashMap 有点类似,通过算出的 HashCode 与 L 取模后定位到 0、2 处,将该处的值设为 1。
  • A2=2000 也是同理计算后将 4、7 位置设为 1。
  • 当有一个 B1=1000 需要判断是否存在时,也是做两次 Hash 运算,定位到 0、2 处,此时他们的值都为 1 ,所以认为 B1=1000 存在于集合中。
  • 当有一个 B2=3000 时,也是同理。第一次 Hash 定位到 index=4 时,数组中的值为 1,所以再进行第二次 Hash 运算,结果定位到 index=5 的值为 0,所以认为 B2=3000 不存在于集合中。

整个的写入、查询的流程就是这样,汇总起来就是:

对写入的数据做 H 次 hash 运算定位到数组中的位置,同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。
一旦其中的有一位为 0 则认为数据肯定不存在于集合,否则数据可能存在于集合中。

所以布隆过滤有以下几个特点:

  1. 只要返回数据不存在,则肯定不存在。
  2. 返回数据存在,但只能是大概率存在。
  3. 同时不能清除其中的数据。

第一点应该都能理解,重点解释下 2、3 点。
为什么返回存在的数据却是可能存在呢,这其实也和 HashMap 类似。
在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。
这时拿 B 进行查询时那自然就是误报了。
删除数据也是同理,当我把 B 的数据删除时,其实也相当于是把 A 的数据删掉了,这样也会造成后续的误报。
基于以上的 Hash 冲突的前提,所以 Bloom Filter 有一定的误报率,这个误报率和 Hash 算法的次数 H,以及数组长度 L 都是有关的。