Author: James Swafford
Date: 06:40:51 01/15/00
Go up one level in this thread
On January 15, 2000 at 01:31:20, Bruce Moreland wrote: >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. If you use 20 bits to probe, why not just store the other 44 bits in the table as a checksum? You already know the other 20 bits match.... I use a "minimum size", so my key is guaranteed to be N bits long. My tables only use 64-N bits as the checksum. James > >bruce
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.