golang刷leetcode:redis布隆过滤器
2023-06-13 09:15:58 时间
描述
请按照下列指示实现一个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
}
相关文章
- django配置文件详解_django配置redis
- SpringBoot 开启Redis缓存及使用方法
- Redis中文官网:开启数据库之旅(redis中文官网)
- 使用Redis Move命令移动元素(redismove命令)
- 策略Java利用Redis实现数据过期策略(redisjava过期)
- 体验极致用户体验:从 Redis 获益(redis用户)
- 使用Redis时,非root用户的权限设置有哪些注意事项?(redis非root)
- 如何快速清除Redis缓存(怎样清除redis)
- 深入了解Redis密码的查看方法(怎么查看redis 密码)
- 缓存实现更高效的Redis缓存以查询条件为基础(带查询条件的redis)
- 调用开源探索Redis之外的可能(类似redis项目)
- 新闻领域采用Redis加快信息传播(新闻类用redis)
- Vuejs 和 Redis 构建高效稳健Web应用(vue redis)
- redis与命令行让管理更便捷(命令行如何操作redis)
- 深入研究将对象存入Redis(向redis中存对象)
- 解决Redis雪崩问题有什么好办法(redis雪崩了怎么办)
- 错误Redis集群认证失败警告(redis集群提示认证)
- 研究Redis集群复制模型的优势与弊端(redis集群复制模型)
- 连接用Redis集群连接多个IP(redis集群几个ip)
- Redis集群使用指南快速上手(redis集群使用教学)
- 查看Redis集合长度的简单方法(redis 集合的长度)
- 为什么要使用Redis读写分离主节点(redis读写分离主节点)
- 利用Redis设置时间的正确命令(redis设置时间命令)
- 探索Redis订阅排他所激发的可能性(redis订阅排他除了)
- Redis解码器揭开神秘的底纹(redis解码器)
- 使用Redis获取当前计数值(redis获取当前计数)
- 热力图上Redis缓存热点数据分析(redis缓存热点数据)