利用 Redis 的 bitmap 实现简单的布隆过滤器

布隆过滤器原理和作用：
www.cnblogs.com/heihaozi/p/1217447...
这里使用goredis来实现一个简单的布隆过滤器，使用3个哈希函数
go的函数是第一公民，可以用函数变量来保存函数

创建hash.go保存哈希函数

package hash
type F func(string) uint64 //创建一个函数类型
//把所有hash函数放入切片中
func NewFunc() []F{
    m := make([]F,0)
    var f F
    f = BKDRHash
    m = append(m,f)
    f = SDBMHash
    m = append(m,f)
    f = DJBHash
    m = append(m,f)
    return m
}
func BKDRHash(str string) uint64 {
    seed := uint64(131) // 31 131 1313 13131 131313 etc..
    hash := uint64(0)
    for i := 0; i < len(str); i++ {
        hash = (hash * seed) + uint64(str[i])
    }
    return hash & 0x7FFFFFFF
}
func SDBMHash(str string) uint64{
    hash := uint64(0)
    for i := 0; i < len(str); i++ {
        hash = uint64(str[i]) + (hash << 6) + (hash << 16) - hash
    }
    return hash & 0x7FFFFFFF
}
func DJBHash(str string) uint64{
    hash := uint64(0)
    for i := 0; i < len(str); i++ {
        hash = ((hash << 5) + hash) + uint64(str[i])
    }
    return hash & 0x7FFFFFFF
}

创建bloom.go

type Bloom struct{
    Conn redis.Conn
    Key string
    HashFuncs []F //保存hash函数
}
 func NewBloom(con redis.Conn) *Bloom{
     return &Bloom{Conn:con,Key:"bloom",HashFuncs:NewFunc()}
 }
 func (b *Bloom)Add(str string) error{
     var err error
     for _,f := range b.HashFuncs {
         offset := f(str)
        _,err := b.Conn.Do("setbit", b.Key, offset,1)
        if err != nil {
            return err
        }
    }
     return err
 }
 func (b *Bloom)Exist(str string) bool{
     var a int64=1
     for _,f := range b.HashFuncs {
         offset := f(str)
        bitValue,_ := b.Conn.Do("getbit", b.Key, offset)
        if bitValue != a {
            return false
        }
    }
    return true
 }

func main() {
    con,err := redis.Dial("tcp", ":6379")//连接redis
    print(err,"connect")
    defer con.Close()

    bloom := hash.NewBloom(con) //创建过滤器
    bloom.Add("newClient") //往过滤器写入数据
    b := bloom.Exist("aaa") //判断是否存在这个值
    fmt.Println(b)
}

相关的redis命令

1、setbit

　　语法：setbit key offset value

　　描述：

　　　　对key所储存的字符串值，设置或清除指定偏移量上的位(bit)。

　　　　位的设置或清除取决于 value 参数，可以是 0 也可以是 1 。

　　　　当 key 不存在时，自动生成一个新的字符串值。

　　　　字符串会进行伸展(grown)以确保它可以将 value 保存在指定的偏移量上。当字符串值进行伸展时，空白位置以 0 填充。

　　注意：
　　　　offset 参数必须大于或等于 0 ，小于 2^32 (bit 映射被限制在 512 MB 之内)。
　　　　因为 Redis 字符串的大小被限制在 512 兆(megabytes)以内， 所以用户能够使用的最大偏移量为 2^29-1(536870911) ， 如果你需要使用比这更大的空间， 请使用多个 key。

2、getbit

　　语法：getbit key offset
　　描述：
　　　　对 key 所储存的字符串值，获取指定偏移量上的位(bit)。
　　　　当 offset 比字符串值的长度大，或者 key 不存在时，返回 0
3、bitcount
　　语法：bitcount key [start] [end]
　　返回值：被设置为 1 的位的数量
　　描述：
　　　　计算给定字符串中，被设置为 1 的比特位的数量
　　　　一般情况下，给定的整个字符串都会被进行计数，通过指定额外的 start 或 end 参数，可以让计数只在特定的位上进行。
　　　　start 和 end 参数的设置和 GETRANGE key start end 命令类似，都可以使用负数值： 比如 -1表示最后一个字节， -2 表示倒数第二个字节，以此类推。
　　　　不存在的 key 被当成是空字符串来处理，因此对一个不存在的 key 进行 BITCOUNT 操作，结果为 0 。

本作品采用《CC 协议》，转载必须注明作者和本文链接