Re: [boost] [unordered] request for ways to get more space efficient allocations

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