Computer Chess Club Archives


Search

Terms

Messages

Subject: Hash table and O(1)

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.