Author: Antonio Dieguez
Date: 13:19:13 09/24/01
Go up one level in this thread
On September 24, 2001 at 16:03:31, Heiner Marxen wrote: >On September 24, 2001 at 15:41:07, Antonio Dieguez wrote: > >>On September 24, 2001 at 15:27:35, Robert Hyatt wrote: >> >>>On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: >>> >>>> >>>>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. >> >>sure, but would be interesting to know if using an N!=2^m fixes a bit the >>decreasing security of the hash. I don't have clear how much, that is why I >>asked. > >That depends on the quality of your hash value HV. If it is a very good one, >using any m bits of HV would yield a nearly optimal (equal) distribution. >If your hashing algorithm is not very good, then selecting m bits from it >may yield a not so good distribution, what causes only part of the hash >table to be really used. In that case, a prime N can help a lot. > >Zobrist hashes with carefully selected random values is good enough >to just select some m bits without noticable problems. doh, I am not speaking about the distribution. Supose we use 3 bits for hashkey. If our hashtable is of 2 entries, already filled. ->We will use %2. these can fit in the first entry: 000 010 100 110 these on the second: 001 011 101 111 all of them have the last bit already equal, so posibility to collision is around 1 of 4. If our hashtable is of 4 entries. ->We will use %4. these can fit in the first entry: 000 100 these on the second: 001 101 these on the third: 010 110 and these on the last: 011 111 in this case all of them have the last 2 bits already equal so posibility to collide is around 1 of 2 (more.)
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.