Author: Alessandro Scotti
Date: 23:22:27 02/06/06
Go up one level in this thread
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. >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. >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.
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.