Email list hosting service & mailing list manager


Re: hash-by-identity guarantees of change consistency? Panu Kalliokoski 21 Apr 2006 12:17 UTC

On Thu, Apr 20, 2006 at 09:39:45AM +0200, Sebastian Egner wrote:
> > 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.

That is already stated, the problem being just that it severes the
usefulness of eq? hash tables.

> 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.

... and you can't do it in standard RnRS Scheme, AFAIK.

Panu

--
personal contact:	xxxxxx@helsinki.fi, +35841 5323835
technical contact:	xxxxxx@iki.fi, http://www.iki.fi/atehwa/
PGP fingerprint:	0EA5 9D33 6590 FFD4 921C  5A5F BE85 08F1 3169 70EC