Message from discussion hashtable w/o keys stored...
From: ly...@cc.gatech.edu (Lyman S. Taylor)
Subject: Re: hashtable w/o keys stored...
Organization: College of Computing, Georgia Tech
In article <cxjlnj8zh33....@acs1.bu.edu>, David Bakhash <ca...@bu.edu> wrote:
>I am using hash-tables, and realized that Lisp, by the way hash-tables are
>defined, must store the keys of the hash-table.
> I'd rather just have collisions, in which case I have a novel way to
>resolve them. I'm trying to figure out a way out.
The reason you must store keys is to resolve the collisions. So the
collisions may happen now. I think it would be more precise to
say you need something else to be the key preferably with a more
Two other responses have point out the function SXHASH.
However, this doesn't guarrantee unique values for each object.
You would still need the key to resolve collisions. For example:
USER(11): (sxhash #( a b ))
USER(12): (sxhash #( c d ))
Here the impelementation is apparently returning the size of the vector
as the code. For other data types the values distribution is much more
less uniform. :-) [ It is implementation specific on how well the
hash codes are distributed over all possible values. The restriction
the codes be indepedent of an "image" likely means for some
situations it will be far from "perfect". ]
What I think you are looking for is a "perfect hashing" function.
In some circumstances you can create these. See Knuth (or another good
algorithms book) on perfect hashes. If each hash code is unique
then you don't need to store the keys to resolve collisions. Because
there aren't any and the index into the underlying array is the
[ Another partial solution would be to only store the keys for
the cases where SXHASH did produce a solution. Although in
the worst case everything could collide and you'd have an
even larger "problem". ]
>wanted a more relaxed version of hash-tables which don't guarantee "no
>collisions", and (maybe) one for which you cannot iterate over the keys.
>Anyone have a clue here?
The predefine tables don't guarantee "no collisions".
And I'm not sure what you mean by iterate over the keys.
You can iterate over a hash table ( this iteration process is
independent of the keys). MAPHASH and WITH-HASH-TABLE-ITERATOR
iterate over the table but there is no "order" in which the
keys are encouttered.
Lyman S. Taylor "Twinkie Cream; food of the Gods"
(ly...@cc.gatech.edu) Jarod, "The Pretender"