On Fri, Jun 22, 2001 at 12:01:05PM +0000, Jost Krieger wrote:
> On Thu, Jun 21, 2001 at 02:25:52PM -0400, Russell Nelson wrote:
> > > speed. However, why should this number be prime, why not have 12 or 16
> > > directories?
> >
> > Because it's a hash. If your hash isn't prime, you fill your hash
> > buckets unevenly.
>
> I think we are spreading urban legends here.
>
> AFAIK, the primality is for double hashing in conflict resolution.
> Nothing of that kind is going on here.
The only way to minimize collisions is to test the function empirically.
In general the hash function ''f(x)=x mod m'' seems to work well if m
is a prime number and not close to a power of 2. Knuth discussed this
in ''The Art of Computer Programming'' Vol.3: Sorting and Searching
(Addison-Wesley) -- happy reading.
Jörgen
