|
Boost : |
From: David Rodríguez Ibeas (dibeas_at_[hidden])
Date: 2008-04-21 10:08:36
On Sat, Apr 19, 2008 at 12:26 PM, Daniel James <daniel_james_at_[hidden]>
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk