非破坏性修改哈希table
Non destructive modify hash table
是否可以将新的键值对非破坏性地添加到 Common Lisp (SBCL) 哈希 table？向散列 table 添加新元素的标准方法是调用：
(setf (gethash key *hash-table*) value)
但是对 setf 的调用修改了 *hash-table* 破坏了原件。我有一个应用程序，我想利用散列 table 查找的效率，但我也想对它们进行非破坏性修改。我看到的解决方法是在对其进行操作之前复制原始哈希 table ，但这在我的情况下是不切实际的，因为我正在处理的哈希 tables 包含数千个元素并且例如，在循环中复制大哈希 tables 会抵消首先使用它们的计算效率优势。
我不认为你可以用普通的 lisp pass-by-reference 一个 hash-table 到另一个 hash-table。
但是我有一个想法是如何避免复制整个散列table，
一个调用得到的结果是使用默认值参数位置
gethash.
(gethash key ht default-value) returns 当 ht 中不存在 key 时，default-value 给出的内容。
;; prepare three example hash-tables, where *h3* and *h2* gets the additional keys
;; and if a key is not present in *h3*, one should look up in *h2*, and if not there too, in *h1*.
(defparameter *h1* (make-hash-table))
(setf (gethash 'a *h1*) 1)
(setf (gethash 'b *h1*) 2)
(setf (gethash 'c *h1*) 3)
(defparameter *h2* (make-hash-table))
(setf (gethash 'd *h2*) 4)
(setf (gethash 'e *h2*) 5)
(defparameter *h3* (make-hash-table))
(setf (gethash 'f *h3*) 6)
;; the call
(gethash 'a *h3* (gethash 'a *h2* (gethash 'a *h1*)))
;; would give the desired result `1`.
;; let us assume, there is a chain of hash-tables *hk* *h(k-1)* ... *h2* *h1*
;; in which one should look up into that order.
;; Then it is to us to build the code
;; (gethash 'a *hk* (gethash 'a *h(k-1)* ...(gethash 'a *h2* (gethash 'a *h1*))...))
;; automatically for every lookup.
;; this macro does it:
(defmacro mget (key hash-tables-list)
(flet ((inject-last (e1 e2) `(,@e1 ,e2)))
(reduce #'inject-last
(mapcar (lambda (ht) `(gethash ,key ,ht))
(nreverse hash-tables-list)))))
;; let's see its macroexpansion:
(macroexpand-1 '(mget 'a (*h3* *h2* *h1*)))
;; (GETHASH 'A *H3* (GETHASH 'A *H2* (GETHASH 'A *H1*))) ;
;; T
;; and run the code:
(mget 'a (*h2* *h1*))
;; 1 ;
;; NIL
可以附上要查看的下一个散列 table 的信息
在 hash-table 对象中。甚至自动生成列表 (*h3* *h2* *h1*) 这样一个人只写
(gethash* key ht) 然后调用 mget ...
嗯，当然，通过这一切 hash-access 变慢了。
在复制整个 hash-table 或在每次调用时支付性能成本之间 trade-off ...
自动查找由 *h3*
扩展的 hash-table
(setf (get '*h3* 'extendeds) '(*h2* *h1*))
(setf (get '*h2* 'extendeds) '(*h1*))
(defun collect-extendeds (hts)
(let ((res (loop for ht in hts
nconcing (get ht 'extendeds))))
(remove-duplicates res)))
;; this function can recursively retrieve all hashtables
(defun get-extendeds* (hts &optional (acc '()))
(let ((hts (if (listp hts) hts (list hts))))
(let ((nexts (collect-extendeds hts)))
(cond ((every #'null nexts) (nreverse (remove-duplicates (append hts acc))))
(t (get-extendeds* nexts (remove-duplicates (append hts acc))))))))
;; write a macro to retrieve key's value from all downstream hashtables
(defmacro geth (key ht)
`(mget ,key ,(get-extendeds* ht)))
(geth 'a *h3*)
;; 1 ;
;; NIL ;; NIL because it was not in *h3* directly but in one of the hashtables
;; which it extends.
;; problem is if 'NIL is a value of an existing key,
;; one would still get 'NIL NIL.
根据您的需要，您可以只使用关联列表，使用 assoc 和其他函数在现有绑定之上建立新绑定。 assoc returns 第一个匹配元素意味着您可以隐藏绑定：
(let ((list '((:a . 1) (:b . 2))))
(acons :b 3 list))
=> ((:b . 3) (:a . 1) (:b . 2))
如果您在结果列表中调用 (assoc :b list)，条目将为 (:b . 3)，但原始列表未修改。
F集
如果关联列表不够用，FSet 库为 Common Lisp 提供了纯函数式的 data-structures，比如映射，它们是 immutable hash-tables。它们被实现为平衡树，这比天真的方法要好。还有其他更高效的 data-structures，但您可能需要自己实现它们（Hash array mapped trie (edit: see https://github.com/danshapero/cl-hamt，感谢@Flux）。话虽如此，FSet 总体上已经足够好了。
FSet 可通过 Quicklisp 获得
USER> (ql:quickload :fset)
创建地图；请注意，如果您安装了适当的 reader 宏，打印的表示将被再次阅读。但是你可以在没有修改语法 table.
的情况下完美地使用这个库
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) |})
是否可以将新的键值对非破坏性地添加到 Common Lisp (SBCL) 哈希 table？向散列 table 添加新元素的标准方法是调用：
(setf (gethash key *hash-table*) value)
但是对 setf 的调用修改了 *hash-table* 破坏了原件。我有一个应用程序，我想利用散列 table 查找的效率，但我也想对它们进行非破坏性修改。我看到的解决方法是在对其进行操作之前复制原始哈希 table ，但这在我的情况下是不切实际的，因为我正在处理的哈希 tables 包含数千个元素并且例如，在循环中复制大哈希 tables 会抵消首先使用它们的计算效率优势。
我不认为你可以用普通的 lisp pass-by-reference 一个 hash-table 到另一个 hash-table。
但是我有一个想法是如何避免复制整个散列table，
一个调用得到的结果是使用默认值参数位置
gethash.
(gethash key ht default-value) returns 当 ht 中不存在 key 时，default-value 给出的内容。
;; prepare three example hash-tables, where *h3* and *h2* gets the additional keys
;; and if a key is not present in *h3*, one should look up in *h2*, and if not there too, in *h1*.
(defparameter *h1* (make-hash-table))
(setf (gethash 'a *h1*) 1)
(setf (gethash 'b *h1*) 2)
(setf (gethash 'c *h1*) 3)
(defparameter *h2* (make-hash-table))
(setf (gethash 'd *h2*) 4)
(setf (gethash 'e *h2*) 5)
(defparameter *h3* (make-hash-table))
(setf (gethash 'f *h3*) 6)
;; the call
(gethash 'a *h3* (gethash 'a *h2* (gethash 'a *h1*)))
;; would give the desired result `1`.
;; let us assume, there is a chain of hash-tables *hk* *h(k-1)* ... *h2* *h1*
;; in which one should look up into that order.
;; Then it is to us to build the code
;; (gethash 'a *hk* (gethash 'a *h(k-1)* ...(gethash 'a *h2* (gethash 'a *h1*))...))
;; automatically for every lookup.
;; this macro does it:
(defmacro mget (key hash-tables-list)
(flet ((inject-last (e1 e2) `(,@e1 ,e2)))
(reduce #'inject-last
(mapcar (lambda (ht) `(gethash ,key ,ht))
(nreverse hash-tables-list)))))
;; let's see its macroexpansion:
(macroexpand-1 '(mget 'a (*h3* *h2* *h1*)))
;; (GETHASH 'A *H3* (GETHASH 'A *H2* (GETHASH 'A *H1*))) ;
;; T
;; and run the code:
(mget 'a (*h2* *h1*))
;; 1 ;
;; NIL
可以附上要查看的下一个散列 table 的信息
在 hash-table 对象中。甚至自动生成列表 (*h3* *h2* *h1*) 这样一个人只写
(gethash* key ht) 然后调用 mget ...
嗯，当然，通过这一切 hash-access 变慢了。
在复制整个 hash-table 或在每次调用时支付性能成本之间 trade-off ...
自动查找由 *h3*
扩展的 hash-table
(setf (get '*h3* 'extendeds) '(*h2* *h1*))
(setf (get '*h2* 'extendeds) '(*h1*))
(defun collect-extendeds (hts)
(let ((res (loop for ht in hts
nconcing (get ht 'extendeds))))
(remove-duplicates res)))
;; this function can recursively retrieve all hashtables
(defun get-extendeds* (hts &optional (acc '()))
(let ((hts (if (listp hts) hts (list hts))))
(let ((nexts (collect-extendeds hts)))
(cond ((every #'null nexts) (nreverse (remove-duplicates (append hts acc))))
(t (get-extendeds* nexts (remove-duplicates (append hts acc))))))))
;; write a macro to retrieve key's value from all downstream hashtables
(defmacro geth (key ht)
`(mget ,key ,(get-extendeds* ht)))
(geth 'a *h3*)
;; 1 ;
;; NIL ;; NIL because it was not in *h3* directly but in one of the hashtables
;; which it extends.
;; problem is if 'NIL is a value of an existing key,
;; one would still get 'NIL NIL.
根据您的需要，您可以只使用关联列表，使用 assoc 和其他函数在现有绑定之上建立新绑定。 assoc returns 第一个匹配元素意味着您可以隐藏绑定：
(let ((list '((:a . 1) (:b . 2))))
(acons :b 3 list))
=> ((:b . 3) (:a . 1) (:b . 2))
如果您在结果列表中调用 (assoc :b list)，条目将为 (:b . 3)，但原始列表未修改。
F集
如果关联列表不够用，FSet 库为 Common Lisp 提供了纯函数式的 data-structures，比如映射，它们是 immutable hash-tables。它们被实现为平衡树，这比天真的方法要好。还有其他更高效的 data-structures，但您可能需要自己实现它们（Hash array mapped trie (edit: see https://github.com/danshapero/cl-hamt，感谢@Flux）。话虽如此，FSet 总体上已经足够好了。
FSet 可通过 Quicklisp 获得
USER> (ql:quickload :fset)
创建地图；请注意，如果您安装了适当的 reader 宏，打印的表示将被再次阅读。但是你可以在没有修改语法 table.
的情况下完美地使用这个库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) |})