知识卡片

问题卡 · 2274.e.1.a.4.v.1.h

删除需改用计数布隆

理解等级:未标注

两个元素若共享同一个位,删除其中一个并把该位改回 0,另一个仍在集合中的元素也会被判成不存在。把该位从是否置位改成计数:同时命中则加一,删除时减一,共享位才不会被一次删除清掉。计数不再是一个比特,内存会变大。用户标识几乎不删除时,普通布隆过滤器就够用;删除频繁就要接受计数带来的空间成本,或放弃这种结构。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《高并发系统设计40问》第15讲《缓存的使用姿势(三):缓存穿透了怎么办?》(源文件:_epub-src/text/part0017_split_002.html) - 结论依据:原文用共享哈希位说明直接清零会误删,并用计数递减作为替代。 - 原始内容:如果A和B同时命中了一个数组的索引,那么这个位置的值就是2