Author: Robert Hyatt
Date: 19:08:44 12/10/99
Go up one level in this thread
On December 10, 1999 at 13:44:52, Dann Corbit wrote: >On December 10, 1999 at 09:03:43, Robert Hyatt wrote: >[snip] >>I don't see the connection between hash signature and table size. I use a 64 >>bit signature, which means I can use _any_ table size up to 2^64... I can even >>go beyond 2^64 entries by using what is commonly called 'buckets'. (A bucket is >>a set of entries rather than a single entry. Then I would probe to a specific >>bucket. I would need some way to differentiate between the different positions >>that produce the same hash signature for that bucket of course, if I use 2^64 >>buckets or more..) >If you store the whole 64 bits "somewhere" (even though you only use a fragment >for the lookup) then the bigger the hash, the fewer the entries you can hold. >If you don't store the full 64 bits somewhere, then you don't really have a 64 >bit hash. You have only the bits that actually get stored when you check for >collision. Not exactly. Suppose you have exactly 4 billion (2^32) entries. You can use the right-most 32 bits to form the hash probe address, and store the leftmost 32 bits for verification. You are using _all_ 64 bits. But since the right most bits are used for the address, there is no use in storing them at that address, right? :) Bob
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.