Author: Dann Corbit
Date: 13:03:02 12/09/99
Go up one level in this thread
On December 09, 1999 at 15:58:51, Daniel Clausen wrote: >Hi > >On December 09, 1999 at 15:46:54, Dann Corbit wrote: > >>If I make a hash key of n bits, how can I make a smaller hash table than 2^n. >> >>I don't get it. (e.g. My question about shrinking the hash table was met with >>"It does not matter how small the table is -- it is the size of the key that >>matters."). This caused me to wonder why my brain is so tiny. I mean, how can >>I have a hash table with a great big key and not allocate enough space to hold >>it? Do you have a smaller hash leader (half-key, quarter-key, whatever) and then >>throw the rest into a list of some kind? > >If you have a hash key of e.g 64 bits and a good algorithm to create it, all >bits are of >'equal quality'. So you can for example use the 1st 20 bits for the index in a >hash >table of 2^20 entries. The index in the hashtable is "key & (hashEntries-1)". > >One hash entry should hold the complete hashkey. If you get a hash-hit, you >should >compare the complete hash-key in the hash table with the hash-key of the current >position. If they're not equal, you got a collision. How are collisions handled? Do you compute the value for the current key and replace or???
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.