This is the mail archive of the binutils@sourceware.org mailing list for the binutils project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [Commited] Extend BFD hash size table


>>>>> "Doug" == Doug Evans <dje@transmeta.com> writes:

 Doug> Nick Clifton writes:
 >> > if we had a better hashing function, we wouldn't need > prime
 >> table sizes and could just use power-of-2 tables and replace all
 >> those > modulo operations with bitwise ANDs.]
 >> 
 >> 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 ?

I didn't see it there in a quick scan.  However...

If you use "add the hash" rehashing as the way to resolve hash
collisions, then you need a prime size.  For other schemes, like
linked list buckets, sequential probe, etc., any table size works,
assuming of course that the hash function itself is good.

	 paul




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]