知识卡片
删除需改用计数布隆
两个元素若共享同一个位,删除其中一个并把该位改回 0,另一个仍在集合中的元素也会被判成不存在。把该位从是否置位改成计数:同时命中则加一,删除时减一,共享位才不会被一次删除清掉。计数不再是一个比特,内存会变大。用户标识几乎不删除时,普通布隆过滤器就够用;删除频繁就要接受计数带来的空间成本,或放弃这种结构。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 缓存的使用姿势(三):缓存穿透了怎么办? · 查看原书依据
如果A和B同时命中了一个数组的索引,那么这个位置的值就是2
参考来源
- 位置:《高并发系统设计40问》第15讲《缓存的使用姿势(三):缓存穿透了怎么办?》(源文件:_epub-src/text/part0017_split_002.html)
- 结论依据:原文用共享哈希位说明直接清零会误删,并用计数递减作为替代。
- 原始内容:如果A和B同时命中了一个数组的索引,那么这个位置的值就是2