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.

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.

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.

Albert Zobrist (1970). A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison, WI, USA. Reprinted (1990) in ICCA Journal, Vol. 13, No. 2, pdf

Home * Programming * Data * Hash TableHash 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.

^{[1]}## Table of Contents

for the four names shown

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

1968).An Improved Hash Code for Scatter Storage. Communications of the ACM, Vol. 11, No. 11968).Algebraic Coding Theory, New York: McGraw-Hill. Revised ed., Aegean Park Press, (1984), ISBN 0894120638. amazon1968).A Solution to the table overflow problem for Hash Tables. Literature: Reports hosted by Atlas Computer Laboratory## 1970 ...

1970).A New Hashing Method with Application for Game Playing. Technical Report #88, Computer Science Department, The University of Wisconsin, Madison, WI, USA. Reprinted (1990) in ICCA Journal, Vol. 13, No. 2, pdf1970).Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, Vol. 13, No. 7, pdf^{[3]}1972).The quadratic hash method when the table size is a power of 2. Literature: Reports hosted by Atlas Computer Laboratory1974).Computer Animation used as a Tool in Teaching Computer Science. Literature: Reports hosted by Atlas Computer Laboratory1974).Ordered Hash Tables. The Computer Journal, Vol. 171975).Hash Table Methods. ACM Computing Surveys, Vol. 7, No. 11977).Universal classes of hash functions. STOC '77## 1980 ...

1985).Hash Tables in Cray Blitz. ICCA Journal, Vol. 8, No. 1 » Cray Blitz1988).Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 11989).A Design Principle for Hash Functions. CRYPTO '891989).One Way Hash Functions and DES. CRYPTO '89^{[4]}## 1990 ...

1992).An Optimal Algorithm for Generating Minimal Perfect Hash Functions. Information Processing Letters, Vol. 43, pp. 257–264. pdf1992).Hash functions for Binary and Ternary Words. NEC Research Institute, ps1994).Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM Journal on Computing, Vol. 23, Nr. 41997).Perfect Hashing. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-1431997).Hash functions. Dr. Dobb's Journal, September 1997^{[5]}1998).The Art of Computer Programming. Volume 3 - Sorting and Searching, 6.4 about universal hashing, (second edition), amazom1998).Memory versus Search in Games. Ph.D. Thesis, Universiteit Maastricht, The Netherlands. ISBN 90-9012006-8.1998).Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf » BitScan## 2000 ...

2002).A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1 » Shared Hash Table - Lock-less2005).The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 32007).Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pdf » Hashing Dictionaries2007).GigaHash: scalable minimal perfect hashing for billions of urls. WWW 20072008).Move Generation with Perfect Hashing Functions.ICGA Journal, Vol. 31, No. 1, pdf » Congruent Modulo Bitboards## 2010 ...

2011).The Power of Simple Tabulation Hashing. arXiv:1011.5200v22011).Effcient Hash Tables on the GPU. Ph.D. thesis, University of California, Davis, pdf » GPU2011).On perfect hashing of numbers with sparse digit representation via multiplication by a constant. Discrete Applied Mathematics, Vol. 159, No. 11 » Magic Bitboards2014).Cuckoo Cycle: a memory-hard proof-of-work system. IACR Cryptology ePrint Archive^{[6]}^{[7]}## Forum Posts

## External Links

Secure Hash Algorithm from Wikipedia

Merkle–Damgård construction from Wikipedia

Koorde based on Chord and De Bruijn sequence

^{[8]}Pierre Courbois, Jasper van 't Hof, Toto Blanke, Sigi Busch

## References

## What links here?

Up one Level