Author: Dann Corbit
Date: 13:41:31 02/18/02
Go up one level in this thread
On February 18, 2002 at 15:43:09, Alvaro Jose Povoa Cardoso wrote:
>My program uses hash tables witch are a power of two.
>In order to compute the index to an hash table of this kind I simply do:
> hashindex=(hashkey & hashsize)
>in witch hashsize is a mask with for example the first 12 bits set for a size of
>4096 entries.
>I would like to know how to compute the index to a hash table that can have
>sizes like 1MB, 7MB, 45MB, 49MB, 50MB, ..etc
>Could someone please explain how to do this?
Let's suppose that you want some size of 49MB. Find the smallest prime number
that is less than or equal to your target size (it's easier than it sounds).
Now, to hash to your table, the lookup is:
hashindex = hashkey % hashsize;
In Beowulf, we have this:
...
if (NHash == 0) {
/* Work out how much hash table memory we have to play with */
HashMem = (1 << Params.HashSize) * 512;
/* Calculate a sensible number of hash table entries, using the
* largest prime number less than the calculated maximum number. */
NHash = LargestPrime(HashMem / ((long int) sizeof(HashElt)));
/* Allocate the memory */
TableW = calloc(sizeof(HashElt), (size_t) NHash);
assert(TableW != NULL);
TableB = calloc(sizeof(HashElt), (size_t) NHash);
assert(TableB != NULL);
}
Here is prime number selection:
/* Calculate the largest (odd) prime number not greater than n.
* I know this is a dumb way of doing it, but it's easily fast enough
* considering that it should only need to be done once per game. */
long int LargestPrime(long int n)
{
int max_fact = (int) sqrt((double) n),
i;
/* This clause should never be needed, but it's worth keeping for safety */
if (n < 5)
return 3;
n += (n % 2) + 1;
do {
n -= 2;
for (i = 3; i <= max_fact; i += 2)
if (n % i == 0)
break;
} while (i <= max_fact);
return n;
}
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.