Author: Robert Hyatt
Date: 12:27:35 09/24/01
Go up one level in this thread
On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: > >>Several hash into 2 X 32 bit values. You store one value, you use the other >>to generate the hash index. This is not quite as safe as a true 64 bit hash >>signature where all 64 bits are used, but it is pretty good. If you have >>one million entries in the table, your hash key is 52 bits long, effectively, >>which is not horrible. Not as good as 64, but not horrible. > >hi. isn't one million of entries around 2^20, so just 44 bits are used for the >key, (not 52) ? I am assuming that the hash signature is made up of two 32-bit words. One of the 32 bit words is stored in the hash entry. The other is used to generate the index. That gives 32 + 20 == 52 bits used if you have a 1M entry table. > >what I see is that 48 bits with separate hashindex is already safer than 64 bits >without separate index when using just 131072 entries (=47 bits), so I may be >not understanding something. You aren't really using 48 bits. You are using more. You are using the number of bits you store in an entry + the number of bits you use to produce the table index. In your case 65 (48 + 17). Some use 2 x 32, and store one of those and use part of the other for the index. That is _clearly_ better than just using 32, period, with the index coming out of the 32 somewhere. > >Also another stupid question, in another post I see calculated the index for >hashtable with HV%N, with N the capacity, in that case is it a bit safer to not >use an N=2^something? or it is almost the same or there are drawbacks, or I'm >not understanding other thing? If you use %, then you can use any size hash table you want. I don't use % because it generally requires two registers, one for the quotient, one for the remainder. Not to mention integer divide has always been a pretty slow operation. With a perfect power of 2, you can use & (2^N - 1) for the address extraction... with a single-cycle instruction penalty. > >thank you.
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.