bloom

数据结构

v1.0.0 C 混编 0 依赖 ABI 1

布隆过滤器（Bloom Filter）— 以较小的内存占用判断一个元素「可能存在」或「一定不存在」，标准版未清空时不漏掉已添加项；计数版删除有额外约束。C 层实现全局位数组与计数器，xlang 层提供面向对象 API。

当前合同与验证

2026-09-26 原生 ABI、结构化错误与尺寸检查更新。公开 C 声明为 include/bloom.h，专项门禁为 tools/check_extlib_argon2_bloom.ps1，具体结果以保存的构建哈希为准。

2026-10-26 当前 Windows 联合门禁报告 passed、47 项检查；Linux C ASan/UBSan、中央与双语范例 JIT/AOT、内嵌 NUL 键 JIT/AOT 均通过。旧 AOT 缺符号不再复现。Bloom 由独立候选包维护，不计入普通扩展库 100 包完成数；同一可变对象的并发访问和跨架构持久化仍未验收。

fpRate 必须严格处于 (0,1)，NaN、无穷及非法边界抛 ValueError，不再隐式替换成默认值。
不可表示的容量抛 RangeError；真实分配失败保留 MemoryError，不伪装成损坏数据。
反序列化检查版本、保留字段、元数据范围、真实长度和乘法溢出。持久化状态不是承诺永久跨算法版本兼容的数据库格式。
XLang 键操作按 UTF-8 实际字节长度传递，内嵌 NUL 不会截成前缀；十六进制状态文本含 NUL 时明确拒绝。test/nul_keys.xl 已覆盖两种筛选器。
计数槽最大 15。删除未添加项、计数饱和后的删除、merge 后独立删除均可能影响其他项，不承诺计数版无条件“不漏判”。merge 逐槽取最大值，不是多重集合计数相加。
对象由调用方串行访问；C 拥有型句柄各释放一次，serialize 返回值借用 XRT 临时区。容量是预计元素数，不是硬性插入上限。
bloom_basic.xl 与 bloom_c.c 展示同结果的恢复、克隆和计数删除。固定键集误判回归和独立的 Windows/Linux C 性能基准已覆盖；基准仅提供当前环境参考，不保证任意键分布的误判率，也不设置跨机器吞吐率门槛。

典型场景

缓存穿透防护 URL 去重黑名单过滤爬虫去重垃圾邮件拦截推荐已读过滤

快速开始

quick_start.xl
import bloom

func main(...) as int
    // 一行创建：声明容量与期望误判率
    auto f = bloom.create(10000, 0.001)

    f.add("user:1001")
    f.add("user:1002")

    // 存在性判定：false 一定不存在，true 可能存在
    println(f.contains("user:1001"))  // true
    println(f.contains("user:9999"))  // false
    println(f.count)                  // 2
    return 0
end

核心特性

全局位数组 — 按目标误判率配置容量，避免分块负载不均抬高低目标误判率
双种子探测 — 两个 XRT 64 位哈希确定全部探针，热路径不分配内存
标准版筛选 — 未清空时不漏掉已添加项；计数版仅能在满足删除约束时使用这一推断
基数估计 — estimatedCount 由填充率反推去重基数，estimatedFpp 给出基于填充率的误判率估计
可持久化 — serialize/deserialize 导出/还原为可移植 hex 字符串
可合并 — merge 就地并集，clone 深拷贝支持非破坏性合并
计数版可删除 — CountingBloomFilter 用 4-bit 计数器支持 remove

包信息

包名	bloom
版本	1.0.0
实现方式	C 混编（核心引擎 C，API 层 xlang）
依赖	无
ABI 版本	1
导出符号	BloomFilter, CountingBloomFilter, create(), createCounting(), deserialize(), deserializeCounting()
源文件	extlibs/bloom/src/bloom.xl

工厂函数

export func create(int capacity, float fpRate = 0.01) as BloomFilter

创建标准布隆过滤器。capacity 为预期元素上限，fpRate 为期望误判率（可省略，默认 1%）。

capacity <= 0 抛出 ValueError。位数组大小与哈希数由容量与误判率自动推导。

export func createCounting(int capacity, float fpRate = 0.01) as CountingBloomFilter

创建计数布隆过滤器，支持 remove 删除元素。内存占用高于标准版（每槽 4-bit 计数器）。

export func deserialize(string data) as BloomFilter export func deserializeCounting(string data) as CountingBloomFilter

从 serialize 产出的 hex 字符串还原过滤器。

非法或损坏的数据抛出 ValueError。

BloomFilter 类

func add(string item) func addAll(array<string> items)

添加单个 / 批量元素。count 统计 add 调用次数（含重复）。

func contains(string item) as bool func containsAll(array<string> items) as bool func containsAny(array<string> items) as bool

存在性判定。contains：返回 false 一定不存在，true 可能存在。containsAll：全部命中。containsAny：任一命中。

func estimatedCount() as int func estimatedFpp() as float

estimatedCount：由填充率反推的去重基数估计。estimatedFpp：基于填充率的误判概率估计。

空过滤器两者均为 0。注意 count（add 次数）与 estimatedCount（去重估计）语义不同。

func serialize() as string

将过滤器（头 + 位数组）导出为可移植 hex 字符串，用于持久化或跨进程共享。

func merge(BloomFilter other) as bool func clone() as BloomFilter

merge：就地并集，本过滤器之后也包含 other 的全部元素；维度不一致返回 false。clone：独立深拷贝，配合 merge 实现非破坏性并集 a.clone().merge(b)。

func clear()

清空全部元素，位数组归零，可复用。

get valid as bool // handle 非空 get count as int // add 调用次数 get bits as int // 位数组总位数 get hashes as int // 独立哈希函数个数 k get capacity as int // 创建时声明的容量

只读属性，查询过滤器状态。

CountingBloomFilter 类

func add(string item) func contains(string item) as bool func remove(string item) func clear()

计数版核心操作。与标准版的关键差异：remove 可删除元素（标准版不可删除）。只能删除确定添加过且未删除的项目；误报会使不存在的项目通过筛选，不能仅凭 contains 决定删除。

计数版使用 4-bit 计数器：单个槽位重复添加超过 15 次会饱和，此时 remove 不完全可逆。

func addAll(array<string> items) func containsAll(array<string> items) as bool func containsAny(array<string> items) as bool func estimatedCount() as int func estimatedFpp() as float func serialize() as string func merge(CountingBloomFilter other) as bool func clone() as CountingBloomFilter

计数版与标准版对称的完整能力：批量、基数估计、序列化、合并（逐槽取计数器最大值）、克隆。

get valid as bool // handle 非空 get count as int // add 调用次数 get slots as int // 计数器槽数 get hashes as int // 独立哈希函数个数 k get capacity as int // 创建时声明的容量

只读属性。计数版以 slots（槽数）替代标准版的 bits（位数）。

教学范例

以下范例逐步展示全部 API，从基础创建到计数版删除。完整源文件：examples/extlibs/bloom.xl

1. 创建过滤器 & 基础查询

创建与查询
import bloom

// create(容量, 期望误判率)，误判率可省略（默认 0.01 = 1%）
auto f = bloom.create(10000, 0.001)

println("有效: ", f.valid)        // true
println("容量: ", f.capacity)     // 10000（创建时声明的元素上限）
println("位数: ", f.bits)         // 位数组总位数（由容量+误判率推导）
println("哈希数: ", f.hashes)     // 独立哈希函数个数 k
println("元素数: ", f.count)      // 0（add 调用次数）

2. 添加与存在性判定

增与查
f.add("user:1001")
f.add("user:1002")
f.add("user:1003")

// contains：可能存在 / 一定不存在。
// 返回 true 不代表一定存在（有误判），返回 false 则一定不存在。
println("含 user:1001 = ", f.contains("user:1001"))  // true
println("含 user:9999 = ", f.contains("user:9999"))  // false（一定不在）
println("元素数: ", f.count)                          // 3

3. 批量操作

批量增查
f.addAll(["user:2001", "user:2002", "user:2003"])
println("批量后元素数: ", f.count)                                  // 6
println("全部命中: ", f.containsAll(["user:1001", "user:2001"]))   // true
println("含缺失项: ", f.containsAll(["user:1001", "user:0"]))      // false
println("任一命中: ", f.containsAny(["user:0", "user:2002"]))      // true

4. 基数估计与运行时误判率

基数估计
// count 是 add 调用次数（含重复）；estimatedCount 由填充率反推的去重基数估计。
println("估计基数: ", f.estimatedCount())

// estimatedFpp：基于填充率的误判概率估计，随元素增多而上升。
println("当前误判率: ", f.estimatedFpp())

5. 序列化与反序列化

持久化
// 同格式与字节序下往返，不承诺永久跨版本存储
string blob = f.serialize()
println("序列化长度: ", string.len(blob))

auto restored = bloom.deserialize(blob)
println("还原有效: ", restored.valid)               // true
println("还原元素数: ", restored.count)             // 6
println("还原含 user:1001 = ", restored.contains("user:1001"))  // true

6. 合并（并集）与克隆

合并与克隆
auto a = bloom.create(10000, 0.001)
auto b = bloom.create(10000, 0.001)
a.add("left")
b.add("right")

// merge：就地并集，a 之后也包含 b 的全部元素。维度不一致时返回 false。
println("合并成功: ", a.merge(b))            // true
println("a 含 right = ", a.contains("right"))  // true

// clone：独立深拷贝。配合 merge 实现「非破坏性并集」——不改动原过滤器。
auto u1 = bloom.create(10000, 0.001)
auto u2 = bloom.create(10000, 0.001)
u1.add("p")
u2.add("q")
auto combined = u1.clone()
combined.merge(u2)
println("combined 含 p = ", combined.contains("p"))  // true
println("combined 含 q = ", combined.contains("q"))  // true
println("u1 仍不含 q = ", not u1.contains("q"))      // true（原过滤器未受影响）

7. 计数布隆过滤器（支持删除）

计数版
// 标准布隆过滤器不可删除；计数版用 4-bit 计数器记录每个槽位，从而支持 remove。
auto cf = bloom.createCounting(5000)
println("计数版槽数: ", cf.slots, " 哈希数: ", cf.hashes)

cf.add("session:abc")
cf.add("session:def")
println("cf 含 session:abc = ", cf.contains("session:abc"))  // true

cf.remove("session:abc")
println("删除后含 session:abc = ", cf.contains("session:abc"))  // false
println("cf 仍含 session:def = ", cf.contains("session:def"))  // true
println("cf 元素数: ", cf.count)                                 // 1

// 计数版同样支持批量 / 估计 / 序列化 / 合并 / 克隆
cf.addAll(["s1", "s2"])
string cblob = cf.serialize()
auto crf = bloom.deserializeCounting(cblob)
println("计数版还原含 s1 = ", crf.contains("s1"))  // true

运行范例

终端
cd release
xl.exe run examples\extlibs\bloom.xl

测试覆盖

测试文件：test/cases/extlib_bloom.xl，覆盖全部公开 API：

基础创建与只读属性（valid / count / bits / hashes / capacity）
add / contains / clear 标准流程
计数版 add / contains / remove / clear；仅对确定添加过的项目调用 remove
错误处理：create(0) / create(-5) 抛 ValueError
estimatedCount / estimatedFpp（空过滤器为 0，添加后为正）
批量操作 addAll / containsAll / containsAny
serialize / deserialize 往返一致性（count / contains / bits / hashes）
deserialize 非法输入抛 ValueError
merge 兼容合并与维度不兼容返回 false
clone 独立性（标准版与计数版，原过滤器不受影响）
非破坏性并集（clone + merge）

测试片段（完整边界以仓库套件为准）

extlib_bloom.xl
import bloom

func main(...) as int
    auto f = bloom.create(1000)
    assert f.valid, "bloom filter should be valid"
    assert f.count == 0, "bloom initial count"
    assert f.bits > 0, "bloom bit array size"
    assert f.hashes > 0, "bloom hash count"

    f.add("hello")
    f.add("world")
    f.add("xlang")
    assert f.count == 3, "bloom count after adds"
    assert f.contains("hello"), "bloom contains hello"
    assert f.contains("world"), "bloom contains world"
    assert f.contains("xlang"), "bloom contains xlang"
    assert not f.contains("missing"), "bloom not contains missing"
    assert not f.contains(""), "bloom not contains empty (never added)"

    f.clear()
    assert f.count == 0, "bloom count after clear"
    assert not f.contains("hello"), "bloom cleared hello"

    auto cf = bloom.createCounting(500)
    assert cf.valid, "counting bloom should be valid"
    assert cf.count == 0, "counting bloom initial count"
    assert cf.slots > 0, "counting bloom slots"
    assert cf.hashes > 0, "counting bloom hashes"

    cf.add("alpha")
    cf.add("beta")
    cf.add("gamma")
    assert cf.count == 3, "counting bloom count after adds"
    assert cf.contains("alpha"), "counting bloom contains alpha"
    assert cf.contains("beta"), "counting bloom contains beta"
    assert not cf.contains("delta"), "counting bloom not contains delta"

    cf.remove("beta")
    assert cf.count == 2, "counting bloom count after remove"
    assert not cf.contains("beta"), "counting bloom removed beta"
    assert cf.contains("alpha"), "counting bloom still has alpha"
    assert cf.contains("gamma"), "counting bloom still has gamma"

    cf.remove("nonexistent")
    assert cf.count == 2, "counting bloom remove nonexistent no-op"

    cf.clear()
    assert cf.count == 0, "counting bloom count after clear"
    assert not cf.contains("alpha"), "counting bloom cleared alpha"

    bool caught = false
    try
        bloom.create(0)
    catch ValueError e
        caught = true
    end
    assert caught, "bloom create(0) must throw ValueError"

    caught = false
    try
        bloom.create(-5)
    catch ValueError e
        caught = true
    end
    assert caught, "bloom create(-5) must throw ValueError"

    // ─── estimatedFpp / estimatedCount ───
    auto ef = bloom.create(1000)
    assert ef.estimatedCount() == 0, "empty estimatedCount"
    assert ef.estimatedFpp() == 0.0, "empty estimatedFpp"
    ef.add("a")
    ef.add("b")
    ef.add("c")
    assert ef.estimatedCount() >= 1, "estimatedCount positive after adds"
    assert ef.estimatedFpp() > 0.0, "estimatedFpp positive after adds"
    assert ef.estimatedFpp() < 0.5, "estimatedFpp low for sparse filter"

    // ─── batch operations ───
    auto bf = bloom.create(1000)
    bf.addAll(["x1", "x2", "x3"])
    assert bf.count == 3, "addAll count"
    assert bf.containsAll(["x1", "x2", "x3"]), "containsAll present"
    assert not bf.containsAll(["x1", "nope"]), "containsAll with missing"
    assert bf.containsAny(["nope", "x2"]), "containsAny hit"
    assert not bf.containsAny(["nope1", "nope2"]), "containsAny miss"

    // ─── serialize / deserialize round-trip ───
    auto sf = bloom.create(1000)
    sf.add("persist1")
    sf.add("persist2")
    string blob = sf.serialize()
    assert string.len(blob) > 0, "serialize non-empty"
    auto rf = bloom.deserialize(blob)
    assert rf.valid, "deserialized valid"
    assert rf.count == 2, "deserialized count"
    assert rf.contains("persist1"), "deserialized contains persist1"
    assert rf.contains("persist2"), "deserialized contains persist2"
    assert not rf.contains("absent"), "deserialized not contains absent"
    assert rf.bits == sf.bits, "deserialized bits match"
    assert rf.hashes == sf.hashes, "deserialized hashes match"

    // ─── deserialize invalid input throws ───
    caught = false
    try
        bloom.deserialize("zzzz")
    catch ValueError e
        caught = true
    end
    assert caught, "deserialize invalid must throw"

    // ─── merge (union) ───
    auto m1 = bloom.create(1000)
    auto m2 = bloom.create(1000)
    m1.add("left")
    m2.add("right")
    assert m1.merge(m2), "merge compatible"
    assert m1.contains("left"), "merge keeps left"
    assert m1.contains("right"), "merge gains right"
    auto big = bloom.create(100000)
    assert not m1.merge(big), "merge incompatible dimensions"

    // ─── counting bloom: estimated / batch / serialize / merge ───
    auto ccf = bloom.createCounting(500)
    ccf.addAll(["k1", "k2", "k3"])
    assert ccf.count == 3, "counting addAll count"
    assert ccf.containsAll(["k1", "k2", "k3"]), "counting containsAll"
    assert ccf.containsAny(["zz", "k2"]), "counting containsAny"
    assert ccf.estimatedCount() >= 1, "counting estimatedCount"
    assert ccf.estimatedFpp() > 0.0, "counting estimatedFpp"

    string cblob = ccf.serialize()
    auto crf = bloom.deserializeCounting(cblob)
    assert crf.valid, "counting deserialized valid"
    assert crf.contains("k1"), "counting deserialized contains k1"
    assert crf.contains("k2"), "counting deserialized contains k2"
    assert not crf.contains("absent"), "counting deserialized not contains absent"
    crf.remove("k1")
    assert not crf.contains("k1"), "counting deserialized remove works"

    auto cm1 = bloom.createCounting(500)
    auto cm2 = bloom.createCounting(500)
    cm1.add("aa")
    cm2.add("bb")
    assert cm1.merge(cm2), "counting merge compatible"
    assert cm1.contains("aa"), "counting merge keeps aa"
    assert cm1.contains("bb"), "counting merge gains bb"

    // ─── capacity getter ───
    auto capf = bloom.create(2000)
    assert capf.capacity == 2000, "capacity getter"
    auto capcf = bloom.createCounting(300)
    assert capcf.capacity == 300, "counting capacity getter"

    // ─── clone (standard) ───
    auto orig = bloom.create(1000)
    orig.add("c1")
    orig.add("c2")
    auto cp = orig.clone()
    assert cp.valid, "clone valid"
    assert cp.count == 2, "clone count"
    assert cp.contains("c1"), "clone contains c1"
    assert cp.contains("c2"), "clone contains c2"
    cp.add("c3")
    assert cp.contains("c3"), "clone has c3"
    assert not orig.contains("c3"), "original unaffected by clone add"
    assert orig.count == 2, "original count unchanged"

    // non-destructive union via clone
    auto u1 = bloom.create(1000)
    auto u2 = bloom.create(1000)
    u1.add("p")
    u2.add("q")
    auto combined = u1.clone()
    assert combined.merge(u2), "clone merge ok"
    assert combined.contains("p"), "combined has p"
    assert combined.contains("q"), "combined has q"
    assert not u1.contains("q"), "u1 unchanged after clone-merge"

    // ─── clone (counting) ───
    auto ccorig = bloom.createCounting(500)
    ccorig.add("z1")
    auto ccp = ccorig.clone()
    assert ccp.contains("z1"), "counting clone contains"
    ccp.remove("z1")
    assert not ccp.contains("z1"), "counting clone removed"
    assert ccorig.contains("z1"), "counting original unaffected"

    return 0
end

运行测试

终端
cd release
xl.exe run ..\test\cases\extlib_bloom.xl

← 返回扩展库列表