[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: hash-by-identity guarantees of change consistency?
> 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
> lack of it seriously lowers the value of eq? hash tables.
> Any ideas / suggestions on how to best approach
The usual approach is to turn a blind eye to the problem,
because most approaches that really solve it (like
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
the table are not modified.
Alternatively, you could add a force-rehash! operation
rebuilds the entire hash table. But of course this
the problem in some cases (when you have made a long
of structure modifications _without_ querying the
Another solution, e.g. in the Map type of the LEDA
for C++, is to use the /pointer/ to the heap-allocated
as a hash value. This is indeed the most efficient
function you can imagine. Unfortunately, this imposes
severe constraint that the underlying garbage collector
support this, e.g. by not moving objects in the heap.