Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!cs.utexas.edu!asuvax!stjhmc!f14.n15.z1.fidonet.org!Dave.Harris
From: Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris)
Newsgroups: comp.lang.c
Subject: hash function for mac needed
Message-ID: <14207.285B768A@stjhmc.fidonet.org>
Date: 16 Jun 91 14:18:36 GMT
Sender: ufgate@stjhmc.fidonet.org (newsout1.26)
Organization: FidoNet node 1:15/14 - Nibbles 'n Bits, Orem UT
Lines: 39


 >From: bkottmann@falcon.aamrl.wpafb.af.mil (Brett Kottmann)
 >Date: 10 Jun 91 21:08:47 GMT
 >Organization: Logicon Technical Services, Inc.
 >Message-ID: <1991Jun10.160847.134@falcon.aamrl.wpafb.af.mil>
 >Newsgroups: comp.lang.c


 >        Are there C implementations of hash functions lying around out 
 >there? 
 >I need a hash function that will take a string (up to 255 chars + null) 
 >and
 >make a unique key for it.  It should hash to the same key for the same 
 >string
 >:).

When somebody compresses 255 bytes down to 2 or 4 let me know :).  "Unique" 
isn't exactly the word you want I don't think.  The simple thing to do is to 
add all the characters up then mod by the size of your hash, then use that 
number to index into an array.  If the spot is used, either link list off the 
array location or skip cirularly in the array until you hit the next unused 
location.  You don't necessarly need to add all 255 characters together.  
Every 5th, 10th or whatever may work just as well, depending on the data.  
Simply keep a counter of the number of seeks required to find your hash 
locations so you can determine which hash scheme works with the fewest seeks 
for your particular data.

To anybody else.  If I have n data elements, with a hash of size x, what is 
considered a good number of searches based on n and x (i.e. ln(x/n)).  Thanks
 

Dave Harris. 


 

--  
Uucp: ...{gatech,ames,rutgers}!ncar!asuvax!stjhmc!15!14!Dave.Harris
Internet: Dave.Harris@f14.n15.z1.fidonet.org