Author: Dann Corbit
Date: 15:03:12 02/06/06
A hash table is an O(1) data structure. That means that hash table lookups are proportional to the number 1. Which means that no matter how large the hash table is, the lookup requires constant time. So if I have a trillion has slots in my hash table, a lookup take about the same time as if I have a total of one hundred hash slots. And if the lookup fails, then it fails. It does not look at additional entries. There are some hash table designs that "chain" a number of entries. Generally, for chess programs, the chains are one or two additional entities (if chaining is even implemented). Even so, the largest chain sequence I have ever seen allowed in a chess program is 8 entries [I would recommend against using 8 entries]. Now, in such cases, you are far more likely to scan longer chains in small hash tables than large ones anyway. Here is an explanation of hash table: http://en.wikipedia.org/wiki/Hash_table Bear in mind that chess programs do not generally chain more than one or two entries -- they simply over-write old data with new. So the explanation on that page is not fully correct for the usage in a chess program. But the explanations on that page do show the general principles for how they work as far as computation of the hash, storage into the table, and retrieval of the stored data.
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.