On Sat, Apr 19, 2008 at 12:26 PM, Daniel James <daniel_james@fmail.co.uk> wrote:
The theory is that you get less collisions when the size is as far from a power of 2 as possible. But I haven't looked into the research that this is based on, so I'm not sure how trustworthy it is.
That is what I was first told in college. Anyway, Java's HashTable (at least Sun's implementation) uses the opposite approach: hash tables are powers of two. A power of two number of buckets implies that the container is more sensitive to a bad hash function, but the 'modulo' operation can be performed as a left-shift, which is much faster. To minimize the impact of a bad hash function Java implements a second (fast, bitwise operations) hashcode conversion after the user provided function. (Note: Java VM modulo an integer division operations are really slow, some real live testing should be performed in C++) David