Re: hash-by-identity guarantees of change consistency?
Panu Kalliokoski wrote: ... and you can't do it in standard RnRS Scheme, AFAIK. And that's ok. -- --Per Bothner [EMAIL PROTECTED] http://per.bothner.com/
Re: hash-by-identity guarantees of change consistency?
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: [EMAIL PROTECTED], +35841 5323835 technical contact: [EMAIL PROTECTED], http://www.iki.fi/atehwa/ PGP fingerprint:0EA5 9D33 6590 FFD4 921C 5A5F BE85 08F1 3169 70EC
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. Sebastian
