"CuckooFilter" （数据结构）

"CuckooFilter"

代表一个集合，用于测试是否确定元素不是成员.

更多信息

  • 布谷鸟过滤器（cuckoo filter）通常用作一个概率集合，可以测试是否确定元素不是其成员.
  • 可将元素从布谷鸟过滤器中移除.
  • 同一元素可多次插入布谷鸟过滤器中.
  • 用布谷鸟过滤器测试一个元素是否属于某集合时，如果该元素不是集合的成员，则总是返回 False.
  • 用布谷鸟过滤器测试一个元素是否属于某集合时，即使该元素是集合的成员，也并不总是返回 True.
  • 如果布谷鸟过滤器中没有空间容纳某个元素，则插入过程可能会失败.
  • CreateDataStructure["CuckooFilter",capacity]新建一个指定 capacity 的 "CuckooFilter"
    Typed[x,"CuckooFilter"]将 x 设为类型 "CuckooFilter"
  • 对于 "CuckooFilter" 类型的数据结构，可以使用以下运算：
  • ds["Array"]ds 中的底层数据时间：O(1)
    ds["Capacity"]ds 的存储容量时间：O(1)
    ds["Copy"]返回 ds 的副本时间：O(n)
    ds["CouldContain",x]如果 ds 包含 x，则返回 True，否则返回 False时间：O(1)
    ds["Delete",x]如果 x 可能是一个元素，则从 ds 中删除 x 返回 True时间：O(1)
    ds["FalsePositiveProbability"]成员测试中假阳性的概率时间：O(1)
    ds["Insert",x]将 x 插入 ds时间：O(1)
    ds["Length"]存储在 ds 中的元素数量时间：O(1)
    ds["LoadFactor"]ds 的负载系数时间：O(1)
    ds["Visualization"]返回 ds 的可视化表示时间：O(n)
  • 还支持以下功能：
  • dsi===dsj若 dsi 等于 dsj，则为 True
    FullForm[ds]ds 的完整形式
    Information[ds]关于 ds 的信息
    InputForm[ds]ds 的输入形式
    Normal[ds]将 ds 转换为正则表达式

范例

打开所有单元关闭所有单元

基本范例  (1)

可使用 CreateDataStructure 创建一个新的 "CuckooFilter"：

任何表达式都可以插入 "CuckooFilter" 数据结构：

可以测试表达式是否不存在. 结果是 False 说明可以确定 f[2] 不在集合内：

结果为 True 说明 f[1] 可能在集合内：

可以从集合中删除一个元素：

现在可以确定该元素不在集合中：

在集合中插入一个元素：

返回 ds 的表达式版本：

可生成数据结构的可视化结果：

范围  (1)

信息  (1)

可用 CreateDataStructure 创建新的 "CuckooFilter"：

有关数据结构 ds 的信息：

可能存在的问题  (1)

如果布谷鸟过滤器中没有足够的空间，则插入可能会失败.

创建布谷鸟过滤器并插入若干元素. 可视化结果可看出分布情况：

负载系数有助于显示可用空间的大小：

插入失败的原因是没有空间容纳另一个具有相同哈希属性的元素：

删除某些元素后就可以进行插入了：