Re: Multi-Minute Startup?

["Eric D. Friedman" <eric_friedman@xxxxxxx>]

Using a prime number to size a hashtable is a way of getting a good distribution across buckets in the table if one is using division (modulo) by the table size to identify the bucket to use for some key.  You can get a refresher in Knuth v3, p. 515-516.

Another, faster approach that you will also see a lot of these days (the java hashtables use this one as of a few releases back), is to set hashtable sizes to one-less-than-some-power-of two. You then assign keys to buckets by doing a bitwise and of the key and that size.  This saves the time involved in doing division (still very expensive, even on modern processors) and also removes the need to find a new prime number every time the table grows.

On Aug 14, 2008, at 11:37 AM, Phil Pennock wrote:

On 2008-08-14 at 15:08 +0200, Richard Hartmann wrote:

On Mon, Aug 11, 2008 at 17:29, Dan Nelson <dnelson@xxxxxxxxxxxxxxx> wrote:

Raise suggested-size to 1601 (a prime number larger than your current

list size with some room to grow).

Using a prime hints at an interesting reason. What is it?

General hashing algorithm theory.  I forget the math (if I ever knew
it); also, there's a lot of heuristics in there ("that seems to work,
let's go with that").

You tend to not be hashing completely random data and in the absence of
distribution information about the input data, bucketing into a prime
number of slots tends to cause the least pain.

You'll find prime number requirements for many hash bucketing schemes.

-Phil, who should have made more effort to stay awake that lecture