"David Richerby" wrote in message
...
Anders Thulin wrote:
4) One small table and one large table.

But why stop there? The table is not static -- you don't only
do searches. You also have to insert new stuff, and weed out old.

Insertion overwrites old data; it's not deleted `manually'. The hash
table is operating as a cache, not a dictionary: if the data you want

You pointing out that a chess hash table is being done as a cache rather
than a dictionary, and him saying that a table isn't static, actually
explains a few things about his message.

I bet he's thinking along the line of a a linked list or tree or b-tree or
some sort of data structure that gets updated dynamically. Maybe even a
structure who's size and organization can change during the search.

Stuff gets inserted, removed, re-organized, searched, etc.

Data structures and algorithms that are simply not used in a chess hash
table.


Anders, a chess hash table is done as a fixed sized table. It's a straight
array with no other structure. It's not a linked list or a tree or a b-tree
or any other 'fancy' data structure. Just a basic linear vector array.

To access a hash entry, you do:

HashEntry = HashTable [ HashIndex % HashSize];
if (HashEntry.Lock == MAGIC(HashIndex)) return HashEntry;
return NULL;

To save it, you do:
OldEntry = HashTable [ HashIndex % HashSize];
if (OldEntry.Draft = NewEntry.Draft)
HashTable[HashIndex % HashSize] = NewEntry;

And so on.

If you do a hash entry that actually contains two or more (a fixed number)
entries, then the code will be slightly more complicted, but still fairly
simple and a fixed cost regardless of the size of the table.

Other modifications to the hash table will change things slightly, but
again, they will be of a fixed cost that is independant of the size of the
table.


It didn't occur to me until now that you might be thinking of too high a
level of data structures.

Since this is a computer chess newsgroup, most people in here are already
familar with the basic algorithms, and I just assumed you were.