Author: Bruce Moreland
Date: 22:31:20 01/14/00
Go up one level in this thread
On January 14, 2000 at 21:55:04, Landon Rabern wrote: >An average how many hash collisions per number of nodes should be happening? I >am getting around 18,000 collisions when I search 800,000 nodes. This seems >like a lot. I am using random numbers from 0 to greatest power of 2 over the >number of hash entries I have for my values. This way if the hashIndex is over >the number of the highest entry I can just subtract the highest entry and get >back in to the numbers I want to be in. I didn't see an easy way to use randoms >from 0 to 2^32 -1, because how do you get the number back into an index you can >use? I'm being a little repetitive but hopefully you'll get your answer out of all of these posts together. First, you can simplify things by forcing a hash table that's an even power of two in size. Use a 64-bit value for your hash key. So to start with you have 2^64 values for your hash key. OK. Say you only have 2^20 entries in your table. Index your table by using the bottom 20 bits of the key, simply mask off the top 44 bits. When you store a hash table element, there is space in the hash table element for the whole 64-bit key. You stuff the whole thing in there when you store the element. When you index your table you check to see that the value stored is the same as the key you are using now. If it's not, the element isn't a match. So you only have 20 bits of table, but you store the whole 64 bits in the table, so you can get the same number of undetected collisions as if you used 64 bits of table. bruce
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.