Re: Is it better to set the freelist to a prime number ?

Indeed a hash function uses prime numbers wherever it can. I was saying that the reason for a prime number is precisely that if the source is not sufficiently random, the target (number of items in hash buckets) would still be as random as we can achieve. For an idealy random source, a prime number is not required but does no harm. For a less idealy random source, a prime number has to be used. And using a prime number is only negligibly more expensive than using a non-prime number. So why not?

An Oracle UNIX process ID is quite random within certain range (has to be greater than essential UNIX daemons). But generally speaking, if the source is a list of numbers mostly ending with 0, then a prime number of buckets would distribute them fairly evenly while 10 buckets won't, if modulus is used as the function.

Yong Huang

"Jonathan Lewis" <jonathan_at_jlcomp.demon.co.uk> wrote in message news:<1027410622.10650.0.nnrp-08.9e984b29_at_news.demon.co.uk>...
> I think it is purely down to the choice
> of algorithm. The hash function Oracle
> uses for hash partitions is clearly
> designed as a 2^N algorithm for mechanical
> reasons. But I have a memory that the best
> randomisers always used prime numbers
> for the hash target.
>
>
> --
> Jonathan Lewis
> http://www.jlcomp.demon.co.uk
>
> Next Seminars
> UK Sept
> Australia August
> Malaysia September
> USA x 2 November
>
> http://www.jlcomp.demon.co.uk/seminar.html
>
> Yong Huang wrote in message
> <07b6be7c6105b142172a9b70371d2d92.99975_at_mygate.mailgate.org>...
> >"Jonathan Lewis" <jonathan_at_jlcomp.demon.co.uk> wrote in message
> >news:1026200922.18484.1.nnrp-13.9e984b29_at_news.demon.co.uk
> >
> >>
> >> When a process requests a free list,
> >> it uses some sort of 'hashing' function
> >> to select which free list, based on the
> >> process id. Using a prime number
> >> with such mechanisms usually reduces
> >> the number of collisions that occur if
> >> the input is randomly distributed.
> >
> >Jonathan, I think you meant non-randomly, or not sufficiently randomly.
> >Otherwise why does the prime number matter? But I could be wrong.
> >
> >Yong Huang
Received on Tue Jul 23 2002 - 12:48:33 CDT