[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: hash-by-identity guarantees of change consistency?

Panu wrote:
> A problem in the SRFI has been brought to my attention, namely that
> hash-by-identity is not required to remain the same for mutable
> structures if you change their contents (and indeed won't in the
> reference implementation).  Arguably this guarantee should be made, as
> lack of it seriously lowers the value of eq? hash tables.

> Any ideas / suggestions on how to best approach this?

The usual approach is to turn a blind eye to the problem,
because most approaches that really solve it (like keeping
track of modifications) have inacceptable performance.

My approach would be to clearly state a general precondition
on hash tables: Hash tables assume that the values stored in
the table are not modified.

Alternatively, you could add a force-rehash! operation that
rebuilds the entire hash table. But of course this only solves
the problem in some cases (when you have made a long sequence
of structure modifications _without_ querying the table).

Another solution, e.g. in the Map type of the LEDA library
for C++, is to use the /pointer/ to the heap-allocated object
as a hash value. This is indeed the most efficient hash
function you can imagine. Unfortunately, this imposes the
severe constraint that the underlying garbage collector must
support this, e.g. by not moving objects in the heap.