From: David Bakhash <ca...@mit.edu>
Subject: Re: hashtable w/o keys stored...
Date: 1999/01/13
Message-ID: <wkiueb2krx.fsf@mit.edu>#1/1
X-Deja-AN: 432188452
References: <cxjlnj8zh33.fsf@acs1.bu.edu> <77g8fd$jfd@pravda.cc.gatech.edu> <wWNm2.88$oD6.7537@burlma1-snr1.gtei.net> <77gh61$k3n@pravda.cc.gatech.edu>
Organization: Boston University
Newsgroups: comp.lang.lisp

ly...@cc.gatech.edu (Lyman S. Taylor) writes:

> In article <wWNm2.88$oD6.7...@burlma1-snr1.gtei.net>,
> Barry Margolin  <bar...@bbnplanet.com> wrote:
> ...
> >He said he's going to resolve the collisions his own way.  Perhaps there's
> >something in the values that does that.  He didn't go into any more detail,
> 
>   That bothered me.  If this "something" can resolve colllisions why isn't
>   it the key?   Otherwise, if you have a piece of data (no key) in a 
>   "hash bucket" how do you know which "key" it belongs to if there is not 
>   one-to-one  mapping between keys and buckets? 

okay.  Let me explain.  I'm only doing this b/c you're interested,
though it's really not that important.

suppose, ideally, I want a hash table whose keys are strings and whose
values are objects.  However, I have so many keys, and each key (string)
is, say 50 characters long.  With 50,000 keys, this can start to really
swallow up memory.  But if, instead, the objects in the hash buckets
somehow contain the strings efficiently, then I can create those strings
when needed, but not store them permanently.

If you're wondering how that can be done, just imagine that two numbers
(pos . length) specifiy a sub-string inside one huge string.  So just
storing the pos and length is enough.

dave