二进制与位运算 hash函数与布隆过滤器
2021-03-29 14:42:09 11 举报登录查看完整内容
hashmap的hash函数为什么是&运算而不是取模？ 如何设计一个布隆过滤器？
作者其他创作
大纲/内容
= 4
共28个0 ……
共27个0 ……
0
为什么hashmap的总容量必须是2的幂次方？
= 15
= 10
= 8
hashcode = 任何int值
客户端请求
扩容后 旧数据桶下标=原下标 或 (原下标+扩容长度)
1
add: 多个hash函数计算多个hash值，对应不同的桶下标为1.get: 必须当所有hash函数计算等到的桶下标都为1，才表示数据存在。
= 9
hash函数1
桶下标 = hashcode & （table.length -1）位运算比取模快27倍
因此，10&5=0 10|5=1510^5=15
一个超级大的二进制数 也是01byte数组 (图示为32 现实可能比较大)
&
int值 32位二进制数 占4个字节
get:id=10
= 5
？
id=10
数据A
mysql
= 0-15
计算得到相应的下标位
误判率：因存在hash碰撞不可避免会误判，会把不存在的Key判定为存在，但不会把存在的key拦截。误判率和bit数组长度、hash次数负相关，但和添加元素数量正相关。
=
二进制与位运算
布隆过滤器
= 2
index3forHash3
& 与运算 都为1才为1| 或运算 1个为1即为1^ 异或运算 两个都不同才为110&5是多少？
index1ForHash1
hash函数3
二进制
index2forHash2
= ?
收藏
收藏
0 条评论
回复 删除
下一页
