布隆过滤器

  • Last updated on 2020-05-27
  • 1581
Redis   面试  

一、概述

1、概念

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数,它是一种比较巧妙的概率型数据结构,特点是高效地插入和查询。

布隆过滤器用于判断一个元素一定不存在于这个空间,比如黑名单系统。

 

2、布隆过滤器数据结构

布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:

如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:

Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:

值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。

当我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。

而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

这是为什么呢?答案很简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

 

3、布隆过滤器处理流程

第一步:开辟空间

开辟一个长度为m的位数组(或者称二进制向量),这个不同的语言有不同的实现方式,甚至你可以用文件来实现。

第二步:寻找hash函数

获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。

第三步:写入数据

将所需要判断的内容经过这些hash函数计算,得到几个值,比如用3个hash函数,得到值分别是1000,2000,3000。之后设置m位数组的第1000,2000,3000位的值位二进制1。

第四步:判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。可以对比上面的布隆过滤器数据结构,你可能会有更清晰的认识。

 
 

 

4、如何选择哈希函数个数和布隆过滤器长度

很显然,过小的布隆过滤器很快所有的 bit 位就会都被置为 1,那么查询任何值都会返回“可能存在”,也就起不到过滤的目的了。

布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置为 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

 

5、布隆过滤器的优缺点

优点:

使用更小的空间和更高的效率进行判断。

缺点:

存在一定的误判,并且不能删除元素。

注:想解决Bloom Filter 中不能删除元素的问题,可以使用 Counting Bloom Filter,它是网上提出来的 Bloom Filter 的改进版,Bloom Filter 本身只有0或1,而Bloom Filter 采用的是计数,比如0,4,9 等,删除元素,就将对应的bit位上值减1,这里不做过多介绍,实际生产中,采用这种方案的人也不多。

 

6、应用场景

(1)黑名单系统

(2)缓存穿透

 

二、代码实现

由于Redis实现了setbit和getbit操作,天然适合实现布隆过滤器,redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。

1、BloomFilterHash.php (hash函数类)

  1. <?php
  2. declare(strict_types = 1);
  3. /*
  4. * hash函数集合类,用于布隆过滤器使用
  5. */
  6. class BloomFilterHash
  7. {
  8. /**
  9. * 由Justin Sobel编写的按位散列函数
  10. *
  11. * @param $string
  12. * @param null $len
  13. * @return int
  14. */
  15. public function JSHash($string, $len = null)
  16. {
  17. $hash = 1315423911;
  18. $len || $len = strlen($string);
  19. for ($i=0; $i<$len; $i++) {
  20. $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
  21. }
  22. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  23. }
  24. /**
  25. * 该哈希算法基于AT&T贝尔实验室的Peter J. Weinberger的工作。
  26. * Aho Sethi和Ulman编写的“编译器(原理,技术和工具)”一书建议使用采用此特定算法中的散列方法的散列函数。
  27. *
  28. * @param $string
  29. * @param null $len
  30. * @return int
  31. */
  32. public function PJWHash($string, $len = null)
  33. {
  34. $bitsInUnsignedInt = 4 * 8; //(unsigned int)(sizeof(unsigned int)* 8);
  35. $threeQuarters = ($bitsInUnsignedInt * 3) / 4;
  36. $oneEighth = $bitsInUnsignedInt / 8;
  37. $highBits = 0xFFFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
  38. $hash = 0;
  39. $len || $len = strlen($string);
  40. for($i=0; $i<$len; $i++) {
  41. $hash = ($hash << (int) ($oneEighth)) + ord($string[$i]);
  42. }
  43. $test = $hash & $highBits;
  44. if ($test != 0) {
  45. $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
  46. }
  47. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  48. }
  49. /**
  50. * 类似于PJW Hash功能,但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。
  51. *
  52. * @param $string
  53. * @param null $len
  54. * @return int
  55. */
  56. public function ELFHash($string, $len = null)
  57. {
  58. $hash = 0;
  59. $len || $len = strlen($string);
  60. for ($i=0; $i<$len; $i++) {
  61. $hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xF0000000;
  62. if ($x != 0) {
  63. $hash ^= ($x >> 24);
  64. }
  65. $hash &= ~$x;
  66. }
  67. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  68. }
  69. /**
  70. * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
  71. * 它是一个简单的哈希函数,使用一组奇怪的可能种子,它们都构成了31 .... 31 ... 31等模式
  72. *
  73. * @param $string
  74. * @param null $len
  75. * @return int
  76. */
  77. public function BKDRHash($string, $len = null)
  78. {
  79. $seed = 131; # 31 131 1313 13131 131313 etc..
  80. $hash = 0;
  81. $len || $len = strlen($string);
  82. for ($i=0; $i<$len; $i++) {
  83. $hash = (int) (($hash * $seed) + ord($string[$i]));
  84. }
  85. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  86. }
  87. /**
  88. * 这是在开源SDBM项目中使用的首选算法。
  89. * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况。
  90. *
  91. * @param $string
  92. * @param null $len
  93. * @return int
  94. */
  95. public function SDBMHash($string, $len = null)
  96. {
  97. $hash = 0;
  98. $len || $len = strlen($string);
  99. for ($i=0; $i<$len; $i++) {
  100. $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
  101. }
  102. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  103. }
  104. /**
  105. * 由Daniel J. Bernstein教授制作的算法,首先在usenet新闻组comp.lang.c上向世界展示。
  106. * 它是有史以来发布的最有效的哈希函数之一。
  107. *
  108. * @param $string
  109. * @param null $len
  110. * @return int
  111. */
  112. public function DJBHash($string, $len = null)
  113. {
  114. $hash = 5381;
  115. $len || $len = strlen($string);
  116. for ($i=0; $i<$len; $i++) {
  117. $hash = (int) (($hash << 5) + $hash) + ord($string[$i]);
  118. }
  119. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  120. }
  121. /**
  122. * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法,主题是排序和搜索第6.4章。
  123. *
  124. * @param $string
  125. * @param null $len
  126. * @return int
  127. */
  128. public function DEKHash($string, $len = null)
  129. {
  130. $len || $len = strlen($string);
  131. $hash = $len;
  132. for ($i=0; $i<$len; $i++) {
  133. $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
  134. }
  135. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  136. }
  137. /**
  138. * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
  139. *
  140. * @param $string
  141. * @param null $len
  142. * @return int
  143. */
  144. public function FNVHash($string, $len = null)
  145. {
  146. $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
  147. $hash = 2166136261; //32位的offset
  148. $len || $len = strlen($string);
  149. for ($i=0; $i<$len; $i++) {
  150. $hash = (int) ($hash * $prime) % 0xFFFFFFFF;
  151. $hash ^= ord($string[$i]);
  152. }
  153. return ($hash % 0xFFFFFFFF) & 0xFFFFFFFF;
  154. }
  155. }

 
2、BloomFilterRedis.php (redis 添加、查询元素到/从 布隆过滤器)

  1. <?php
  2. declare(strict_types = 1);
  3. include_once 'BloomFilterHash.php'; // 项目中请用use替代
  4. /**
  5. * 使用redis实现的布隆过滤器
  6. */
  7. class BloomFilterRedis
  8. {
  9. protected $bucket; // 定义bucket的名字
  10. protected $hashFunction; // 定义使用的hash方法
  11. protected $Hash;
  12. protected $Redis;
  13. /**
  14. * BloomFilterRedis constructor.
  15. * @param string $bucket
  16. * @param array $hashFunction
  17. */
  18. public function __construct(string $bucket, array $hashFunction)
  19. {
  20. $this->bucket = $bucket;
  21. $this->hashFunction = $hashFunction;
  22. $this->Hash = new BloomFilterHash;
  23. $this->Redis = $this->getRedis();
  24. }
  25. /**
  26. * 添加到集合中
  27. *
  28. * @param $string
  29. * @return array
  30. */
  31. public function add($string)
  32. {
  33. $pipe = $this->Redis->multi();
  34. foreach ($this->hashFunction as $function) {
  35. $hash = $this->Hash->$function($string);
  36. $pipe->setBit($this->bucket, $hash, true);
  37. }
  38. return $pipe->exec();
  39. }
  40. /**
  41. * 查询是否存在(存在的一定会返回true, 不存在有一定几率返回true,但如果返回false,则说明一定不存在)
  42. *
  43. * @param $string
  44. * @return bool
  45. */
  46. public function exists($string)
  47. {
  48. $pipe = $this->Redis->multi();
  49. $len = strlen($string);
  50. foreach ($this->hashFunction as $function) {
  51. $hash = $this->Hash->$function($string, $len);
  52. $pipe = $pipe->getBit($this->bucket, $hash);
  53. }
  54. $res = $pipe->exec();
  55. if (in_array(0, $res)) {
  56. return false;
  57. }
  58. return true;
  59. }
  60. /**
  61. * 设置redis连接
  62. *
  63. * @return Redis
  64. */
  65. private function getRedis()
  66. {
  67. $redis = new Redis();
  68. $redis->connect('127.0.0.1', 6379);
  69. $redis->auth('haveyb');
  70. $redis->select(8);
  71. return $redis;
  72. }
  73. }

 
3、index.php (测试文件)

  1. <?php
  2. declare(strict_types = 1);
  3. include_once 'BloomFilterRedis.php'; // 在项目中应该使用use自动加载
  4. // 定义key,并自行从hash函数集中选取几个方法
  5. $object = new BloomFilterRedis('test_bloom', ['JSHash', 'DJBHash', 'ELFHash']);
  6. $object->add('老迟笔记');
  7. $object->add('DockerHub');
  8. // 添加元素到布隆过滤器
  9. var_dump($object->exists('老迟笔记')); // true
  10. echo '<br>';
  11. var_dump($object->exists('DockerHub')); // true
  12. echo '<br>';
  13. var_dump($object->exists('SiNa')); // false

注:使用上面的方法可以存储 2^32 个元素  

 



Top