Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Non power of two hash table sizes

Author: David Rasmussen

Date: 22:48:51 02/18/02

Go up one level in this thread



Eh... How about just using the mod operator, %?

On February 18, 2002 at 16:41:31, Dann Corbit wrote:

>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 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.