无损修改哈希表

Question

是否可以非破坏性地将新的键值对添加到 Common Lisp (SBCL) 哈希表中？向哈希表添加新元素的标准方法是调用：

(setf (gethash key *hash-table*) value)

但调用setf修改*hash-table*破坏了原件。我有一个应用程序，我想利用哈希表查找的效率，但我也想非破坏性地修改它们。我看到的解决方法是在对其进行操作之前复制原始哈希表，但这在我的情况下不切实际，因为我正在处理的哈希表包含数千个元素并复制大型哈希表，例如循环首先会否定使用它们的计算效率优势。

Answer 1

根据您的需要，您可以只使用关联列表、使用assoc和其他函数在现有绑定之上建立新绑定。assoc返回第一个匹配元素的事实意味着您可以隐藏绑定：

(let ((list '((:a . 1) (:b . 2))))
  (acons :b 3 list))

=> ((:b . 3) (:a . 1) (:b . 2))

如果您调用(assoc :b list)结果列表，条目将为(:b . 3)，但原始列表未修改。

集

如果关联列表还不够，FSet 库为 Common Lisp 提供纯函数式数据结构，如映射，它们是不可变的哈希表。它们被实现为平衡树，这比简单的方法要好。还有其他更有效的数据结构，但您可能需要自己实现它们（哈希数组映射的树）。话虽如此，总体而言，FSet 已经足够好了。

FSet 可通过 Quicklisp 获得

USER> (ql:quickload :fset)

创建地图；请注意，如果您安装了适当的阅读器宏，则会再次读取打印的表示。但是您可以在没有修改语法表的情况下完美使用该库。

USER> (fset:map (:a 0) (:b 1))
#{| (:A 0) (:B 1) |}

使用新的绑定更新之前的地图:c：

USER> (fset:with * :c 3)
#{| (:A 0) (:B 1) (:C 3) |}

使用新的绑定更新前一张地图:b，它会遮住前一张地图：

USER> (fset:with * :b 4)
#{| (:A 0) (:B 4) (:C 3) |}

所有中间映射都未修改：

USER> (list * ** *** )
(#{| (:A 0) (:B 4) (:C 3) |}
 #{| (:A 0) (:B 1) (:C 3) |} 
 #{| (:A 0) (:B 1) |})