Re: Hashtable efficiency

From: Michael Borgwardt (brazil_at_brazils-animeland.de)
Date: 08/21/04 

Date: Sat, 21 Aug 2004 00:46:20 +0200

Mike Schilling wrote:
> Speaking of which, why does HashMap use powers of 2, when we all learned in
> our first data structures class to use odd primes?

Probably because finding primes is a lot more difficult that finding
powers of 2.

The *reason* why you use prime hash table sizes is that it's the simplest
way to defend against non-obviously bad hash functions. Sun's
implementation achieves the same goal with the scrambling method I quoted.

BTW, the only even prime is 2, and nobody's gonna use that as a hash
table size...

Relevant Pages

  • Re: Hashtable efficiency
    ... >>Probably because finding primes is a lot more difficult that finding ... > hard-coded, static table of primes which, say, are just a little greater than ... > the powers of two, and use that to choose sizes for the table. ... Mark Thornton ...
    (comp.lang.java.programmer)
  • Re: Hashtable efficiency
    ... >> learned in our first data structures class to use odd primes? ... > Probably because finding primes is a lot more difficult that finding ... the powers of two, and use that to choose sizes for the table. ...
    (comp.lang.java.programmer)
  • Re: Self Study problem help - Group theory
    ... > numerator and the denominator will decompose into powers of the primes ... Where do the *powers* of primes come from? ... > the bottom, and none of them are 2, so no matter what we can never ...
    (sci.math)
  • Re: Magic number in Boolean
    ... public int hashCode() { ... Programmers are a superstitious lot. ... Powers of two, of course, are the most magical of all: ... about hash tables and prime numbers. ...
    (comp.lang.java.programmer)
  • Re: How to implement a Hash Table in C
    ... Primes aren't just an advantage for quadratic probing - they're ... Just how big a hash table did your users want? ... Google users: ...
    (comp.lang.c)