扩展库 / bloom

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，具体结果以保存的构建哈希为准。

典型场景

缓存穿透防护 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

核心特性

包信息

包名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：

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

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
← 返回扩展库列表