Author: Dann Corbit
Date: 11:36:06 02/07/06
Go up one level in this thread
On February 07, 2006 at 02:22:27, Alessandro Scotti wrote: >On February 06, 2006 at 18:03:12, Dann Corbit wrote: > >>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. > >This is only true if the hash table is relatively empty, but as the table gets >full the access time becomes O(n) with most implementations. Right. But not in computer chess. For O(n) access, you have a broken implementation. The hash table should be resized. It is also possible to hash to a skiplist chain instead of a linear list. In such a case the access time is O(log(k)), where k is the average length of the overflow chains. >>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. > >Then it's not a "classical" hash table, which holds as many different entries as >its size without discarding any and must be able to work around collisions. Right. Chess programs do not use classical hash tables. >>Bear in mind that chess programs do not generally chain more than one or two >>entries -- they simply over-write old data with new. > >They can do that because the discarded information can be computed again, so >it's a space vs. time tradeoff. In most applications when you stuff data into a >hash table you assume you will be always able to retrieve it later. It depends on what you are using it for. One of the most popular uses for hash tables is as a cache. In such a usage, you hope that it's there and load it if it is not. That is how it is used in chess.
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.