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

[Sebastian Egner <sebastian.egner@xxxxxxxxxxx>]

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.

Sebastian