eq and hashing (was Re: [plt-scheme] How to make unit functors?)

From: Robby Findler (robby at cs.uchicago.edu)
Date: Wed May 28 23:43:20 EDT 2003

At Wed, 28 May 2003 16:38:22 -0600, Matthew Flatt wrote:
> At Wed, 28 May 2003 17:19:18 -0500, Robby Findler wrote:
> > Say that I'm implementing a finite mapping data structure that claims
> > to map all values, but only creates the actual entries lazily (ie, when
> > they are looked up or changed or something like that). If you ask me
> > for 'l many times, but I only keep the hash code for 'l in my data
> > structure, you may get different entries in the table at different
> > times, as the symbol table is gc'd.
> I don't quite follow. If you keep only the hash code, how do you know
> that it has something to do with 'l (as opposed to, say, 'foo)?

You don't -- all you know is that next time you get a 'l passed into
the data structure, you want the same answer to come out. Now you don't
get that.


  (define m (make-mapping))
  (bind 'l "l binding")
  (lookup 'l) ==>(hopefully) "l binding"

If the internal structure of the table uses the hash codes to maintain
the mapping and doesn't hold onto the values themselves the lookup
might signal some kind of unknown entry.

Isn't this true if I were implementing hash tables in Scheme, using the
eq-hash-map function myself? Am I missing something?

I tried to test out this theory with mz's weak hash tables:

  Welcome to MzScheme version 204.3, Copyright (c) 1995-2003 PLT
  > (define ht (make-hash-table 'weak))
  > (hash-table-put! ht 'funnyhaha 1)
  > (hash-table-get ht 'funnyhaha)
  > (collect-garbage)
  > (hash-table-get ht 'funnyhaha)
  hash-table-get: no value found for key: funnyhaha

But of course I *have* mapped 'funnyhaha! I can see how you can argue
operationally that this is just how it works, but I can't see how this
is desirable behavior.

'funnyhaha that I type in now should be eq? to the 'funnyhaha I type in
later. I have exposed the fact that it isn't.


Posted on the users mailing list.