Re: [Commited] Extend BFD hash size table

[Doug Evans <dje at transmeta dot com>]

Nick Clifton writes:
 > Hi Paul, Hi Doug,
 > 
 > >  >> I have always thought that using prime numbers as the hash table
 > >  >> size was necessary in order to get an efficient use of all the
 > >  >> buckets.  Of course this may just be an urban myth, I do not know
 > >  >> of any actual theoretical work to back this up.
 > > 
 > >  Doug> Knuth Volume 3, 6.4 Hashing ?
 > 
 > Really ?  I sadly do not have these volumes, so I will take your word 
 > for it.

It's there, grep for prime.

 > Paul>
 > > any table size works,
 > > assuming of course that the hash function itself is good.

This is obviously the key: a good hash function.
A prime modulo lets one to some extent compensate for a poorer hash function.

 > I must admit that I have not tried using powers of two instead of prime 
 > numbers.  I will give it a go some time.
 > 
 > If you or anyone else has any results related to this subject please do 
 > post them to the list.

For some reading,

google: "hash table" size modulo prime [or variants thereof]

e.g.
http://www.isthe.com/chongo/tech/comp/fnv/
http://burtleburtle.net/bob/hash/hashfaq.html
http://en.wikipedia.org/wiki/Hash_table

Question: libiberty has hashtab.c.  I don't have an opinion on whether
bfd should use it (or on the efficiency of its algorithm), but I wonder
if whatever bfd does use shouldn't live in libiberty?