hash buckets

[HIBBS, BARR (SBCSI)]

Brian--

I'm just getting back to work after three weeks off, so I'm a bit behind in
my mail...  this may have already been discussed to death in later messages:
if so, please forgive the repetition....

Read Knuth on "Searching and Sorting" for a good discussion on the selection
of a radix value for constructing hash tables.  Basically, the best choices
are prime numbers, chosen so that with randomly distributed key values the
number of links that must be followed is less than some target value, for
example, log2N, the mean value of comparisons for a binary search.

Here at Pacific*Bell, we've used a hash table size of 1997 since the
beginning.  It scales well for our client population size, although I
suppose I really should reexamine the fundamental assumptions that led me to
choosing that particular value.  When I chose this value, I was seeking
something reasonably close to a power of two, in addition to being prime.
As an exercise, I also devised a brute force algorithm different from the
Sieve of Erasthomes for determining prime values... (I went to engine
school, not CS...)

Hope that helps!

--Barr



> ----------
> From: 	Brian J. Murrell[SMTP:brian_murrell at ssd.bctel.net]
> Sent: 	Tuesday, January 04, 2000 2:23 PM
> To: 	dhcp-hackers at isc.org
> Subject: 	hash buckets
> 
> Happy New Year all you hackers out there!
> 
> Ted (and gang), I noticed that there seems to be a constant defined in the
> server which is used when setting up the hash tables and doing the hashing
> that produces a table with 97 (IIRC) hash buckets.
> 
> I am just wondering why 97?
> 
> I guess in looking at the capacity of our server, I am thinking that the
> hash tables in my server(s) are probably pretty (over-)loaded.  Any advise
> on picking a new number?  A text I read recently prescribed a load of no
> more than 2 to 3 per bucket.  It seems obvious what the penalties of too
> few hash buckets are, but what penalties exist for too many, beyond the
> obvious of having unused resource?
> 
> Is the hashing algorithm somehow tuned for 97 buckets?  If I wanted to
> increase the number of buckets should I replace the algorithm too?
> 
> Considering I have (using a simple grep, sort and uniq searching
> algorithm)
> 12000 leases in my leases file, does 97 hash buckets not sound a little
> few?  Even the most uniform hashing algorithm is going to create buckets
> with 127 leases in them.
> 
> Anybody else modifying the number of hash buckets you are using?  What
> load
> factor did you choose and why?
> 
> Thanx,
> b.
> 
> 
> 
> --
> Brian J. Murrell
> Brian_Murrell at ssd.bctel.net
> BCTel Advanced Communications                                      604 454
> 5279
> Vancouver, B.C.
> 
>