Lib.rs

bloom2

一个快速的二级布隆过滤器实现，与标准布隆过滤器相比，在空时内存消耗仅为2%。

• 稀疏分配与过滤器负载成正比增长内存使用量
• 低开销，快速 O(1) 查找，具有摊销的 O(1) 插入
• 32位和64位安全
• 保持与标准布隆过滤器相同的错误接受概率
• 没有'不安全'代码

CompressedBitmap保持与正常布隆过滤器相同的错误接受属性和类似性能属性，同时根据需要懒加载支持内存，从而使除完全加载的过滤器之外的所有过滤器的内存占用更小。

随着条目数量的增加，布隆过滤器的错误接受概率也会增加，因此它们通常被调整以保持较小的负载因子，从而导致底层位图的使用效率低下。

        ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
        │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │
        └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

这个二级布隆过滤器将位图分成usize位的块，并使用第二个位图来标记已填充的块，根据需要懒加载它们。

	                 ┌───┬───┬───┬───┐
	      Block map: │ 0 │ 1 │ 0 │ 0 │
	                 └───┴─┬─┴───┴───┘
	                       └──────┐
	    ┌ ─ ┬ ─ ┬ ─ ┬ ─ ┐ ┌───┬───▼───┬───┐ ┌ ─ ┬ ─ ┬ ─ ┬ ─ ┐
	      0   0   0   0   │ 1 │ 0 │ 0 │ 1 │   0   0   0   0
	    └ ─ ┴ ─ ┴ ─ ┴ ─ ┘ └───┴───┴───┴───┘ └ ─ ┴ ─ ┴ ─ ┴ ─ ┘

对于落在未填充块中的索引的查找将检查单个块映射位并立即返回。

对于已填充块中的索引的查找，首先检查块映射位，然后通过计算块映射中先于它的1位的数量来确定位图块在位图数组中的偏移量。这非常高效，因为它使用了现代CPU上的POPCNT指令。

用例

非常适合长时间运行、稀疏填充的布隆过滤器，存储在RAM或磁盘上。

如果过滤器比可用的RAM/存储在磁盘上的空间大，可以使用mmap来加载二级布隆过滤器以提高性能。操作系统将根据需要从磁盘懒加载位图块，而频繁访问的块映射将保留在内存中，以提供对未填充块快速负面响应。

序列化

启用可选序列化功能，使用serde功能 - 默认禁用。

请注意，使用默认的 RandomHasher 会导致不同的位图，该位图在不同进程中不可重用；对于序列化过滤器，应使用不同的哈希器。默认情况下，派生的 Hash 实现不被视为可移植的，但可以手动编写实现。