利用 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 协议》,转载必须注明作者和本文链接
讨论数量: 1

存在的不一定存在,不存在的则一定不存在。

2周前 评论
littlexiaoshuishui (楼主) 2周前

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!