From: ly...@cc.gatech.edu (Lyman S. Taylor)
Subject: Re: hashtable w/o keys stored...
Date: 1999/01/12
Message-ID: <77g8fd$jfd@pravda.cc.gatech.edu>#1/1
X-Deja-AN: 431774543
References: <cxjlnj8zh33.fsf@acs1.bu.edu>
Organization: College of Computing, Georgia Tech
NNTP-Posting-User: lyman
Newsgroups: comp.lang.lisp

In article <cxjlnj8zh33....@acs1.bu.edu>, David Bakhash  <ca...@bu.edu> wrote:
>hey,
>
>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 
  concise encoding. 

  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 ))
2
USER(12): (sxhash #( c d ))
2

   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 
   "key". 
   
  
   [ 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"