Re: [Chicken-users] This may be a bug in chickens hash tables - or my bad

[Ivan Shmakov]

>>>>> Jörg F Wittenberger <address@hidden> writes:

 > I always assumed that (make-hash-table eq?) would create a hash table
 > usable with arbitrary chicken objects as keys.

 > That is especially structures like objects created via define-record
 > should be valid as keys.  That is: referencing the table using the
 > very same object (comparing eq? to the key object of the insert
 > operation) will succeed.

 > However this fails for me.  At least after the key object was mutated
 > between insert and reference time.

        Given that the basic idea of hashing is to produce a key out of
        the object’s /value/, the change of the value – and mutation
        does just that – changes the hash.  In this regard, SRFI-69
        reads:

    Hashing means the act of taking some value and producing a number
    from the value.  A hash function is a function that does this.

        A typical implementation for a hash table would be a pair of a
        hash function (or closure) and a vector of, say, alists.
        For each input value, the hash function gives the index into the
        vector to look at, and the predicate is used to search for the
        exact pair, in the manner similar to assoc, etc.

        A (make-hash-table eq?) call may be interpreted as a request for
        a hash table, still value-based (as with any other predicate),
        yet with a twist that the alist found via (vector-ref
        table-vector (hash object)) is then searched via assq.  Given
        that the ‘hash’ function still depends on the value (and not the
        identity), assq may easily get applied to a different alist each
        time ‘object’ is mutated.

        SRFI 69 allows for a hash-by-identity function that could be
        used along with eq?, but it seems to be meant more as an
        optimization than anything.  And I fail to see in the request
        any clear provision for “true” by-identity hash tables.

        Naturally, once we stick to immutable objects, this problem
        never arises.

[…]

-- 
FSF associate member #7257  http://am-1.org/~ivan/      … 3013 B6A0 230E 334A