基于Redis实现布隆过滤器

加分技能 阅读量

布隆过滤器 (Bloom Filter) 是1970年由布隆提出的。 它实际上是一个很长的二进制向量和一系列随机映射函数。 布隆过滤器可以用于检索一个元素是否在一个集合中。

  • BloomFilterHash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
<?php

namespace App\Support\BloomFilter;

/**
 * Class BloomFilterHash
 * @package App\Support\BloomFilter
 */
class BloomFilterHash
{
    /**
     * 由Justin Sobel编写的按位散列函数
     * @param $string
     * @param null $len
     * @return int
     */
    public function JSHash($string, $len = null)
    {
        $hash = 1315423911;
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 该哈希算法基于AT＆T贝尔实验室的Peter J. Weinberger的工作。
     * Aho Sethi和Ulman编写的“编译器（原理，技术和工具）”一书建议使用采用此特定算法中的散列方法的散列函数。
     * @param $string
     * @param null $len
     * @return int
     */
    public function PJWHash($string, $len = null)
    {
        $bitsInUnsignedInt = 4 * 8; //（unsigned int）（sizeof（unsigned int）* 8）;
        $threeQuarters     = ($bitsInUnsignedInt * 3) / 4;
        $oneEighth = $bitsInUnsignedInt / 8;
        $highBits  = 0x7FFFFFFF << (int) ($bitsInUnsignedInt - $oneEighth);
        $hash = 0;
        $test = 0;
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash = ($hash << (int) ($oneEighth)) + ord($string[$i]);
        }
        $test = $hash & $highBits;
        if ($test != 0) {
            $hash = (($hash ^ ($test >> (int)($threeQuarters))) & (~$highBits));
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 类似于PJW Hash功能，但针对32位处理器进行了调整。它是基于UNIX的系统上的widley使用哈希函数。
     * @param $string
     * @param null $len
     * @return int
     */
    public function ELFHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash = ($hash << 4) + ord($string[$i]);
            $x = $hash & 0xF0000000;
            if ($x != 0) {
                $hash ^= ($x >> 24);
            }
            $hash &= ~$x;
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 这个哈希函数来自Brian Kernighan和Dennis Ritchie的书“The C Programming Language”。
     * 它是一个简单的哈希函数，使用一组奇怪的可能种子，它们都构成了31 .... 31 ... 31等模式，它似乎与DJB哈希函数非常相似。
     * @param $string
     * @param null $len
     * @return int
     */
    public function BKDRHash($string, $len = null)
    {
        $seed = 131;  # 31 131 1313 13131 131313 etc..
        $hash = 0;
        $len || $len = strlen($string);
        for ($i=0; $i<$len; $i++) {
            $hash = (int) (($hash * $seed) + ord($string[$i]));
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 这是在开源SDBM项目中使用的首选算法。
     * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的MSB存在高差异的情况
     * @param $string
     * @param null $len
     * @return int
     */
    public function SDBMHash($string, $len = null)
    {
        $hash = 0;
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash);
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 由Daniel J. Bernstein教授制作的算法，首先在usenet新闻组comp.lang.c上向世界展示。
     * 它是有史以来发布的最有效的哈希函数之一。
     * @param $string
     * @param null $len
     * @return int
     */
    public function DJBHash($string, $len = null)
    {
        $hash = 5381;
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash = (int) (($hash << 5) + $hash) + ord($string[$i]);
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * Donald E. Knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。
     * @param $string
     * @param null $len
     * @return int
     */
    public function DEKHash($string, $len = null)
    {
        $len || $len = strlen($string);
        $hash = $len;
        for ($i = 0; $i < $len; $i++) {
            $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]);
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }

    /**
     * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
     * @param $string
     * @param null $len
     * @return int
     */
    public function FNVHash($string, $len = null)
    {
        $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
        $hash = 2166136261; //32位的offset
        $len || $len = strlen($string);
        for ($i = 0; $i < $len; $i++) {
            $hash = (int) ($hash * $prime) % 0x7FFFFFFF;
            $hash ^= ord($string[$i]);
        }

        return ($hash % 0x7FFFFFFF) & 0x7FFFFFFF;
    }
}
  • BloomFilterRedis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
<?php

namespace App\Support\BloomFilter;

use App\Support\RedisTool;

abstract class BloomFilterRedis
{
    protected $redis;
    protected $hash;
    protected $bucket;
    protected $hashFunc;

    public function __construct()
    {
        if (!$this->bucket || !$this->hashFunc) {
            throw new \Exception("需要定义bucket和hashFunction", 4000);
        }

        $this->hash  = new BloomFilterHash();
        $this->redis = RedisTool::getInstance();
    }

    /**
     * 添加到集合中
     * @param $string
     * @return array
     */
    public function add($string)
    {
        $pipe = $this->redis->multi();
        foreach ($this->hashFunc as $func) {
            $hash = $this->hash->$func($string);
            $pipe->setBit($this->bucket, $hash, 1);
        }
        return $pipe->exec();
    }

    /**
     * 查询是否存在, 存在的一定会存在, 不存在有一定几率会误判
     * @param $string
     * @return bool
     */
    public function exists($string)
    {
        $pipe = $this->redis->multi();
        $len  = strlen($string);
        foreach ($this->hashFunc as $func) {
            $hash = $this->hash->$func($string, $len);
            $pipe = $pipe->getBit($this->bucket, $hash);
        }
        $res  = $pipe->exec();
        foreach ($res as $bit) {
            if ($bit == 0) return false;
        }

        return true;
    }
}
  • BloomFilter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
<?php

namespace App\Support\BloomFilter;

/**
 * Class BloomFilter
 * @package App\Support\BloomFilter
 */
class BloomFilter extends BloomFilterRedis
{
    /**
     * 表示判断重复内容的过滤器
     * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数)
     * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空.
     * @var string
     */
    protected $bucket = 'bfr';

    protected $hashFunc = ['BKDRHash', 'SDBMHash', 'JSHAsh'];
}
  • RedisController
1
2
3
4
5
6
7
8
9
10
11
/**
 * Redis-布隆过滤器
 *
 * @param BloomFilter $filter
 * @Post("/test_bloom")
 */
public function test_bloom(BloomFilter $filter)
{
    $filter->add('bloom');
    dd($filter->exists('bloom'));
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2023 Keep It Simple And Stupid All Rights Reserved.

访客数 : | 访问量 :