提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

golang刷leetcode：redis布隆过滤器

2023-02-18 16:32:26 时间

描述

请按照下列指示实现一个redis布隆过滤器：

① 首先构造n个哈希方法，每个哈希方法字符串到key值映射公式为：key = ( i * key + s) % mod，其中key从0开始，s为字符串中每个字符的ASCII值，i为这是第几个哈希方法（从1开始），mod为每个方法对应的随机数，取值在10000～20000之间。

② 实现add函数，向布隆过滤器中添加一个字符串：使用每个构造的哈希方法得到n个key值，相应key值标记。

③ 实现contains函数，检查给定字符串是否在布隆过滤器中：检查是否每个哈希方法的key值都有标记。

输入字符串数组s1表示先将这些字符串加入到布隆过滤器中，再检验字符串数组s2中的字符串是否在布隆过滤器中。

示例1

输入：

["NiuNiu"],["Niu", "NiuN", "NiuNiu", "niu"],3

复制

返回值：

[0,0,1,0]

复制

说明：

0表示不在布隆过滤器中，1表示在布隆过滤器中

解题思路：

布隆过滤器通过位图来存储某个key的hash值是否不存在，为了防止hash冲突，一般算多个hash值，中间用到了置位和读取操作。需要注意运算符的优先级。

代码实现：

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s1 string字符串一维数组 
 * @param s2 string字符串一维数组 
 * @param n int整型 
 * @return int整型一维数组
*/
func BloomFilter( s1 []string ,  s2 []string ,  n int ) []int {
    // write code here
    mod:=10240
    bitSet:=make([]byte,1280)
    for _,s:=range s1{
       for i:=1;i<=n;i++{
           val:=hash(i,mod,s)
           bytes:=bitSet[val/8]
           bitSet[val/8]= bytes | (1<<(byte(val)%8))
          // fmt.Println( bitSet[val/8],val,bytes,byte(val)%8,1<<(byte(val)%8),1<<0)
       }   
    }
    
    var r []int
    for _,s:=range s2{
        exist:=1
       for i:=1;i<=n;i++{
           val:=hash(i,mod,s)
           bytes:=bitSet[val/8]
           if  ((bytes >> (val%8))&1)==0{
                exist=0
               break
           }
       }
        r=append(r,exist)
    }
    
    return r
}

func hash(i,mod int,str string)int{
    key:=0
    for j:=0;j<len(str);j++{
        key=(i*key+int(str[j]))%mod
    }
    return key
}

相关文章