www.delorie.com/gnu/docs/gnugo/gnugo_171.html   search  
 
Buy GNU books!


GNU Go Documentation

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

14.2.2 Organization of the hash table

The hash table consists of 3 parts:

When the hash table is created, these 3 areas are allocated using malloc(). When the hash table is populated, all contents are taken from the Hash nodes and the Read results. No further allocation is done and when all nodes or results are used, the hash table is full. Nothing is deleted from the hash table except when it is totally emptied, at which point it can be used again as if newly initialized.

When a function wants to use the hash table, it looks up the current position using hashtable_search(). If the position doesn't already exist there, it can be entered using

hashtable_enter_position().

Once the function has a pointer to the hash node containing a function, it can search for a result of a previous search using hashnode_search(). If a result is found, it can be used, and if not, a new result can be entered after a search using hashnode_new_result().

Hash nodes which hash to the same position in the hash table (collisions) form a simple linked list. Read results for the same position, created by different functions and different attacked or defended strings also form a linked list.

This is deemed sufficiently efficient for now, but the representation of collisions could be changed in the future. It is also not determined what the optimum sizes for the hash table, the number of positions and the number of results are.


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003