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; >}

- Re: Non power of two hash table sizes
**Dann Corbit***22:54:35 02/18/02*- Re: Non power of two hash table sizes
**David Rasmussen***11:22:10 02/19/02*- Re: Non power of two hash table sizes
**Dann Corbit***11:30:09 02/19/02*

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

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.