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

- Re: Non power of two hash table sizes
**David Rasmussen***22:48:51 02/18/02*- 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

- Re: Non power of two hash table sizes
- Re: Non power of two hash table sizes
**Benny Antonsson***13:56:37 02/18/02*- Re: Non power of two hash table sizes
**Dann Corbit***14:07:11 02/18/02*- Re: Non power of two hash table sizes
**Heiner Marxen***14:37:27 02/18/02*- Re: Non power of two hash table sizes
**Dann Corbit***15:58:54 02/18/02*- Re: Non power of two hash table sizes
**Heiner Marxen***17:19:17 02/18/02*- Re: Non power of two hash table sizes
**Dan Andersson***23:47:41 02/18/02*- Re: Non power of two hash table sizes
**Heiner Marxen***06:23:18 02/19/02*- Re: Non power of two hash table sizes
**Dan Andersson***11:21:15 02/19/02*

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes
- Re: Non power of two hash table sizes
**Dann Corbit***17:34:09 02/18/02*- Re: Non power of two hash table sizes
**Keith Evans***15:11:20 02/19/02*

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

- Re: Non power of two hash table sizes

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.