golang刷leetcode：redis布隆过滤器
golang刷leetcode：redis布隆过滤器
golangLeetcode
发布于 2022-12-17 16:13:35
发布于 2022-12-17 16:13:35
代码可运行
运行总次数：0
代码可运行
描述
请按照下列指示实现一个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
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-08-07，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 golang算法架构leetcode技术php 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
