Roc 字典 Dict.remove 的交换移除语义:为什么删除后查找仍有效、迭代顺序却会变
Roc 字典 Dict.remove 的交换移除语义:为什么删除后查找仍有效、迭代顺序却会变
Roc 是一门快速、友好、函数式的编程语言,其标准库中的 Dict 模块提供了不可变的字典(哈希表)实现。本文以仓库中的 REPL 快照测试 dict_remove_order.md 为切入点,完整讲解 Dict.remove 的删除语义、它与其他字典操作(get、to_list、len、contains)的组合行为,以及其底层"交换移除(swap-removal)"实现原理。读完本文,你将掌握 Dict.remove 的准确行为模型,能在实际代码中安全地依赖"删除后剩余键值对查找依旧有效"这一保证,同时理解为何迭代顺序会发生变化。
一、快照测试:一页浓缩的删除行为契约
test/snapshots/repl/dict_remove_order.md 是一个 REPL 快照测试文件:它把一段在 Roc REPL 中执行的交互记录固化下来,作为回归测试的预期输出。文件由四个部分组成:
| 区块 | 作用 |
|---|---|
# META |
元数据,description 描述本次测试的语义,type=repl 表明这是 REPL 交互测试 |
# SOURCE |
REPL 中输入的命令(以 » 开头),即被执行的 Roc 表达式 |
# OUTPUT |
每条命令对应的标准输出 |
# PROBLEMS |
期望的类型检查/编译诊断,NIL 表示没有任何错误 |
该文件 description 明确指出本次测试的语义:
Dict.remove swap-removes entries and keeps remaining lookups valid
即:Dict.remove 采用"交换移除"策略删除条目,同时保证剩余条目的查找仍然有效。这就是本文要解释的核心契约。
二、逐条拆解快照中的命令与输出
快照的 SOURCE 部分包含三条 REPL 命令,我们逐条分析其行为。
2.1 构建一个含三个键值对的字典
» dict = Dict.empty().insert("a", 1).insert("b", 2).insert("c", 3)
assigned `dict`
Dict.empty() 创建空字典,连续三次 .insert(...) 依次写入 "a"→1、"b"→2、"c"→3。REPL 将结果绑定到变量 dict,并回显 assigned dict``。
2.2 删除后 to_list() 的迭代顺序
» dict.remove("a").to_list()
[("c", 3.0), ("b", 2.0)]
这是全文最关键的一行:删除 "a" 之后,剩余两对键值对不是按插入顺序 [("b", 2), ("c", 3)] 返回,而是 [("c", 3.0), ("b", 2.0)]——"c" 排到了 "b" 前面。这正是"交换移除"的直接证据:底层把最后一个条目("c")移动到被删除条目("a")腾出的位置上,而不是把 "b" 及其之后的所有元素整体前移(那叫"顺移移除",代价为 O(n))。
2.3 删除后按键查找仍然正确
» dict.remove("a").get("c")
Ok(3.0)
删除 "a" 后,用 get("c") 查询剩余键 "c",返回 Ok(3.0)。注意两点:
- 返回值是
Ok(...)而非裸值:Roc 中Dict.get : Dict(k, v), k -> Result(v, [KeyNotFound]),按键不存在时返回Err(KeyNotFound),存在时返回Ok(v)。快照输出Ok(3.0)说明查找路径完全正常。 - "剩余条目查找有效"这一保证在交换移除后依然成立:虽然内部存储里
"c"被移动到了"a"的槽位,但由于槽位索引同步更新(详见第四节),get依然能正确定位"c"。
2.4 删除不存在的键:原字典原样返回
» dict.remove("missing").to_list()
[("a", 1.0), ("b", 2.0), ("c", 3.0)]
删除一个不存在的键 "missing" 时,to_list() 返回了与原始插入顺序完全一致的三对键值对。这说明:
- 删除缺失键是空操作(no-op),返回的就是原字典本身;
- 此时没有任何条目被移动,因此迭代顺序保持不变。
从源码看,这一行为在 Builtin.roc 的 remove 实现中非常直观:
remove = |dict, key| match dict {
HashMap(data) => match dict_find(data, key) {
Found(found) => HashMap(dict_remove_bucket_data(data, found.bucket_index))
Missing(_) => dict // 找不到键:原样返回,不做任何改动
}
}
dict_find 命中才触发真正的删除逻辑;未命中则直接返回 dict,因此迭代顺序、长度、内容全部保持不变。
2.5 小结:三行命令对应三条行为保证
| 命令 | 输出 | 揭示的行为 |
|---|---|---|
dict.remove("a").to_list() |
[("c", 3.0), ("b", 2.0)] |
删除后剩余条目采用交换移除,顺序可能改变 |
dict.remove("a").get("c") |
Ok(3.0) |
交换移除后剩余条目的按键查找仍然有效 |
dict.remove("missing").to_list() |
[("a", 1.0), ("b", 2.0), ("c", 3.0)] |
删除缺失键为空操作,字典原样返回 |
三、兄弟快照:dict_remove.md 与 dict_remove_all.md
仓库中还有两份同主题的 REPL 快照,可以交叉验证 remove 系列 API 的语义。
3.1 dict_remove.md:删除的核心性质
dict_remove.md 验证了 Dict.remove 最基本的两条性质:
» Dict.empty().insert("a", 1).insert("b", 2).remove("a").len()
1
» Dict.empty().insert("a", 1).insert("b", 2).remove("a").contains("a")
False
» Dict.empty().insert("a", 1).remove("missing").len()
1
- 删除
"a"后len()从 2 变为 1,键值对数量正确递减; contains("a")返回False,被删除的键彻底消失;- 删除缺失键
"missing"后len()仍为 1,再次印证空操作语义。
3.2 dict_remove_all.md:批量删除
dict_remove_all.md 覆盖了批量版本 Dict.remove_all:
» Dict.remove_all(
Dict.empty().insert("a", 1).insert("b", 2).insert("c", 3),
Dict.empty().insert("b", 99).insert("d", 4),
).len()
2
» ...contains("b")
False
» ...get("c")
Ok(3.0)
remove_all 把第一个字典中凡是出现在第二个字典里的键全部删除:"b" 被移除(注意第二个字典中 "b" 的值是 99,remove_all 只看键不看值),"c" 保留且查找有效,剩余长度为 2。
四、源码级原理:交换移除(swap-removal)在 Roc 中的实现
4.1 Roc 的 Dict 是基于开放寻址哈希表的不可变封装
Dict 的公开 API 定义在 src/build/roc/Builtin.roc(标准库内建模块)。remove 的类型签名为:
remove : Dict(k, v), k -> Dict(k, v)
where [k.is_eq : k, k -> Bool, k.to_hash : k, Hasher -> Hasher]
它要求键类型 k 满足 is_eq(相等判断)与 to_hash(哈希计算)两个约束——这是哈希表实现的前提。remove 返回新字典而非就地修改,保持了 Roc 数据不可变、值语义的总体设计。
从结构看,Dict 内部由 HashMap(data) 承载,data 包含条目数组(entries)与桶数组(buckets)。remove 的删除流程是:
dict_find(data, key)定位键所在的桶索引;- 命中则调用
dict_remove_bucket_data(data, bucket_index)从桶中摘除条目; - 未命中则原样返回
dict。
4.2 为什么"交换"而非"顺移"?
从 dict_remove_order.md 的输出可见,删除 "a" 后剩余条目顺序为 [("c", 3.0), ("b", 2.0)]。这正好对应"最后一条被移到被删位置"的操作:
删除前 entries: [("a",1), ("b",2), ("c",3)]
删除 "a" 后 : [("c",3), ("b",2)] ← "c" 被搬到下标 0,"b" 留在原地
如果采用"顺移",结果会是 [("b",2), ("c",3)],与快照不符。因此可以断定 Roc 的字典删除采用交换移除:把数组末尾元素搬到被删元素的位置,再弹出末尾,从而将删除成本控制在 O(1)(摊销),无需移动后续所有条目。
这一策略与编译器内部使用的 DenseMap 数据结构高度一致。在 src/collections/DenseMap.zig 中,remove 通过 removeActive 实现:
pub fn remove(self: *Self, key: K) bool {
const index = keyIndex(key);
const position = self.densePosition(index) orelse return false;
self.removeActive(index, position);
return true;
}
removeActive(src/collections/DenseMap.zig)的注释性行为正是交换移除的标准实现:
fn removeActive(self: *Self, index: usize, position: usize) void {
const last_position = self.active_indices.items.len - 1;
if (position < last_position) {
const last_index = self.active_indices.items[last_position];
self.active_indices.items[position] = last_index; // 把最后一个索引搬到被删位置
self.values.items[position] = self.values.items[last_position]; // 最后一个值同步搬移
self.sparseSlotPtr(last_index).?.* = @intCast(position); // 更新被搬元素的反向索引
}
_ = self.active_indices.pop().?; // 弹出末尾,删除完成
_ = self.values.pop().?;
self.sparseSlotPtr(index).?.* = empty_position; // 被删键的槽位标记为空
}
这里揭示的正是"剩余查找仍然有效"的实现基础:被移动的元素(最后一个)会在搬移的同时更新它的稀疏索引(sparseSlotPtr(last_index)),因此后续按键查找依然能精确指向新位置。标准库层面的 dict_remove_bucket_data 与 DenseMap.removeActive 遵循同一交换移除思想,只是前者作用于条目/桶数组,后者作用于稀疏-稠密双数组结构。
4.3 顺序保证的边界:插入顺序在删除前有效
to_list(src/build/roc/Builtin.roc)直接返回内部条目数组,iter 与 iter_rev(src/build/roc/Builtin.roc)则按当前内部顺序迭代。因此:
- 未发生删除时:迭代顺序等于插入顺序;
- 一旦发生删除:
Dict.remove可能重排剩余条目(to_list/iter/iter_rev的文档注释均明确提示[Dict.remove] may reorder the remaining pairs)。
所以在依赖"字典顺序"的代码里,只有两种情况可以安全假设顺序:字典自创建后从未被 remove 过,或者删除的恰好是最后一个条目(此时 position == last_position,交换分支不执行,顺序不变)。不要在任何删除操作之后假设迭代顺序与插入顺序一致。
五、实战建议:写出不依赖顺序的删除代码
基于上述契约,在实际 Roc 代码中使用 Dict.remove 时有几条可直接落地的建议:
- 把删除后的字典当"无序集合"使用:删除后按键查找(
get)、成员判断(contains)、长度统计(len)都是安全且语义稳定的,放心使用; - 不要依赖删除后的迭代顺序:如果后续要遍历,优先以
get/contains等查找类操作为主,或对to_list()的结果先排序再消费; - 删除缺失键是零成本的:
remove对不存在的键直接返回原字典,无需先contains判断再删除,直接调remove即可; - 键类型需要可哈希、可判等:
remove要求键满足is_eq与to_hash约束(见 Builtin.roc),自定义键类型需确保实现了这两者; - 批量删除优先用
remove_all:需要按另一个字典批量剔除键时,直接使用Dict.remove_all,语义是"去掉第一个字典中键出现在第二个字典中的所有条目"。
六、总结
通过 dict_remove_order.md 这一份 REPL 快照,我们可以完整还原 Roc 字典删除的三大行为契约:
- 交换移除:删除条目时把最后一个条目搬到被删位置,迭代顺序因此可能改变(如
[("c", 3.0), ("b", 2.0)]); - 查找依然有效:被搬移条目的槽位索引同步更新,
get("c")依旧返回Ok(3.0); - 缺失键空操作:删除不存在的键返回原字典,顺序与内容均不变。
这一语义与编译器内部 DenseMap 的 removeActive 实现(src/collections/DenseMap.zig)一脉相承,都以 O(1) 的代价换取了删除性能,代价是迭代顺序不稳定。理解这份契约,你就能在编写 Roc 程序时做出正确的取舍:把 Dict 当作按键访问的容器来用,而不要在删除后依赖任何顺序假设。