CODEWITHSUNDEEP
common-lisp
Byte
Byte

Reputation: 509

Using mutable data as hash table keys in Common Lisp?

It appears that Common Lisp allows mutable data to be used as hash table keys.

(defparameter *dict* (make-hash-table))

(defparameter *a* (make-hash-table))

(setf (gethash *a* *dict*) 5)

(loop for key being the hash-keys of *dict*
      do (progn
             (print key)
             (print (gethash key *dict*))))

Here a hash table is used as a key in another hash table.

I'm a bit confused by this behavior. It is my understanding that keys that are mutable can mess with the hash if the key object is mutated.

How does the hash table maintain its integrity, and more importantly - is there anything one should know when dealing with mutable hash table keys in CL? Is this something to be avoided?

Upvotes: 2

Views: 217

Answers (1)

sds
sds

Reputation: 60074

See 18.1.2 Modifying Hash Table Keys:

An object is visibly modified with regard to an equivalence test if there exists some set of objects (or potential objects) which are equivalent to the object before the modification but are no longer equivalent afterwards.

If an object O1 is used as a key in a hash table H and is then visibly modified with regard to the equivalence test of H, then the consequences are unspecified if O1, or any object O2 equivalent to O1 under the equivalence test (either before or after the modification), is used as a key in further operations on H. The consequences of using O1 as a key are unspecified even if O1 is visibly modified and then later modified again in such a way as to undo the visible modification.

In your example, the hash table test is eql, which means that modifying the key (adding elements to *a*) does not change the hash code (i.e., this is not a "visible modification"):

(defparameter *ht-1* (make-hash-table :test 'eql))
(defparameter *key* (cons nil nil))
(setf (gethash *key* *ht-1*) 10)
*ht-1*
==> #S(HASH-TABLE :TEST FASTHASH-EQL ((NIL) . 10))
(setf (car *key*) 42)
*ht-1*
==> #S(HASH-TABLE :TEST FASTHASH-EQL ((42) . 10))
(gethash *key* *ht-1*)
==> 10; T
(gethash '(42) *ht-1*)
==> NIL; NIL

Thus you can see that *ht-1* is keyed on the specific object rather than on anything that looks like it.

On the other hand, consider an equal hash table:

(defparameter *ht-2* (make-hash-table :test 'equal))
(setf (gethash *key* *ht-2*) 20)
*ht-2*
==> #S(HASH-TABLE :TEST FASTHASH-EQUAL ((42) . 20))
(gethash *key* *ht-2*)
==> 20; T
(setf (car *key*) 7)            ; **visible modification**!
(gethash '(7) *ht-2*)
==> unspecified!
(gethash *key* *ht-2*)
==> unspecified!
(setf (car *key*) 42)           ; restore key
(gethash '(42) *ht-2*)
==> unspecified!
(gethash *key* *ht-2*)
==> unspecified!

The bottom line is: do not modify hash table keys visibly!

Upvotes: 4

Related Questions