Author: Dieter Buerssner
Date: 12:53:34 08/26/03
Go up one level in this thread
On August 26, 2003 at 15:20:22, Peter Fendrich wrote: >How can we use these 40Mb with a good distribution of entries? >(I have more hash tables to combine with but let's skip that for now) > >Some figures in this example: > 1 entry: 96 bits = 12 bytes > Available memory: 88Mb > # entries available: 7689557 >Key for 88Mb (Key88): 23 bits (22 bits will cover 48Mb) > Max for Key88: 96Mb (8388608 entries) > >When computing the Key88 from my (64 bits) Hashcode some values will of course Skip this step. >be above the upper limit 7689557 (11101010101010101010101). >My first thought was to use modulo: Key88 %= 7689557 And use 32 bits of the 64 bit hash code. unsigned long keyxx = hashcode & 0xffffffffUL; index = keyxx%number_of_entries; It will be almost uniformly distributed, unless your number of entries comes close 2^^32. One could use the modolu directly on the 64-bit number, but that will be a very costly operation on many platforms. For example there is no instruction on x86 for that operation (there is a 64 bit devide by 32 bit instruction, that also yields the modulo, but the result of the devision must be smaller than 2^^32, otherwise you get a divide by zero - so it is not usable here). Regards, Dieter
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.