From ###@###.### Fri Oct 13 10:17:08 1995
From: ###@###.### (Ken Arnold - Sun Labs)
To: arthur.vanhoff@Eng
Subject: primes in hash table

I'm submitting the following as a bug, but since the bug report doesn't
give me any ack that it recieved the report, I'm sending it to you, too.

I'm reporting the lack-of-ack to the Appropriate Authorities...

The java.util.Hashtable class doesn't know from primes. It
takes any initial capacity I give it, and it doubles (!) the
size when it runs out of space, thereby guaranteeing an even
number, not a prime. It is well known that hash
tables are most efficient (by a large amount, on average)
when the size of the hash table is prime. This is usually
accomplished by having a table of known primes, or a simple
test for primeness, since it usually doesn't take very long
to find the next prime by rounding up until you find one.

At the very least, growth should be by 2*size - 1, which has
a *tendency* to be prime, if size is already prime, but that's
pretty crude.