Home * Programming * Data * Hash Table
315px-Hash_table_3_1_1_0_1_0_0_SP.svg.png

A Hash Table, or a Hash Map, is a data structure that associates identifiers or keys (names, chess positions) with values (i. e. phone number, score of a position). A hash function is used for turning the key into a relatively small integer, the hash, that serves as an index into an array.

In a well-dimensioned hash table, the average cost for each lookup is independent of the number of elements stored in the table. In general programming as well in computer chess, hash tables often serve as cache for once calculated values, to save relative expensive computations over and over again.
A small phone book as a hash table [1]

240px-Hash_table_4_1_1_0_0_0_0_LL.svg.png

240px-Hash_table_4_1_0_0_0_0_0_LL.svg.png
A perfect hash function
for the four names shown

A minimal perfect hash function
for the four names shown

Perfect Hashing

If all of the keys are known at compile or initialization time and their cardinality is reasonable small, a perfect hash table can be created, in which there will be no collisions, since each key has an unique index. Opposed to Minimal Perfect Hashing, the lookup array contains either gaps or multiple entries.

Applications in computer chess are hashing of masked occupied bitboards, to map for instance attack sets of sliding pieces (rooks, bishops) on a particular square, or pawn shield stuff. Another application, despite a reversible hash function, is a precomputed table indexed by some material key, likely an incremental updated dot-product of all piece-type counts in some fixed order, by a vector of cumulated maximum count products of pieces ordered below, usually ignoring unusual material configurations due to promotions [2] . Persistent, or on the fly generated Endgame Tablebases and Bitbases containing perfect knowledge by retrograde analyses of certain material constellations with a few pieces in late endings might be considered as a kind of perfect hashing as well.


Minimal Perfect Hashing

If the hash array has no gaps and unique, distinct values, so called Minimal Perfect Hashing is applied, like in following bitboard hashing for bitscan purpose or determining pre-calculated move lists by move target sets of knights and king.


Search Tables

The classical hash table implementation in computer chess are the transposition tables, indexed by Zobrist- or BCH keys of the position, modulo number of entries inside the table, to store search results, evaluation, pawn structure related stuff and repetitions.


Class Libraries


Publications

1968

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...


Forum Posts


External Links


References

  1. ^ Hash function from Wikipedia
  2. ^ Cache-friendier material index by Harm Geert Muller, CCC, March 31, 2010
  3. ^ Bloom filter from Wikipedia
  4. ^ A Hash Function for Hash Table Lookup by Bob Jenkins, updated Dr. Dobb's article
  5. ^ Cuckoo Cycle: a new memory-hard proof-of-work system by John Tromp, Bitcoin Forum, January 08, 2014
  6. ^ Cuckoo hashing from Wikipedia
  7. ^ Gosper's Algorithm (Hashlife) explained

What links here?


Up one Level