Difference between revisions of "Hash Table"

From Chessprogramming wiki
Jump to: navigation, search
(4 intermediate revisions by the same user not shown)
Line 81: Line 81:
 
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.cis.uab.edu/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]] » [[Shared Hash Table#Lockless|Shared Hash Table - Lock-less]]
 
* [[Robert Hyatt]], [[Tim Mann]] ('''2002'''). ''[http://www.cis.uab.edu/hyatt/hashing.html A lock-less transposition table implementation for parallel search chess engines]''. [[ICGA Journal#25_1|ICGA Journal, Vol. 25, No. 1]] » [[Shared Hash Table#Lockless|Shared Hash Table - Lock-less]]
 
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.cis.uab.edu/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]
 
* [[Robert Hyatt]], [[Anthony Cozzie]] ('''2005'''). ''[http://www.cis.uab.edu/hyatt/collisions.html The Effect of Hash Signature Collisions in a Chess Program]''. [[ICGA Journal#28_3|ICGA Journal, Vol. 28, No. 3]]
 +
* [[Mathematician#DFotakis|Dimitris Fotakis]], [[Mathematician#RPagh|Rasmus Pagh]], [[Peter Sanders]], [[Mathematician#PGSpirakis|Paul Spirakis]] ('''2005'''). ''[https://link.springer.com/article/10.1007/s00224-004-1195-x Space Efficient Hash Tables with Worst Case Constant Access Time]''. [https://en.wikipedia.org/wiki/Theory_of_Computing_Systems Theory of Computing Systems], Vol. 38, No. 2
 
* [[Sam Tannous]] ('''2007'''). ''Avoiding Rotated Bitboards with Direct Lookup''. [[ICGA Journal#30_2|ICGA Journal, Vol. 30, No. 2]], [http://arxiv.org/PS_cache/arxiv/pdf/0704/0704.3773v2.pdf pdf] » [[Hashing Dictionaries]]
 
* [[Sam Tannous]] ('''2007'''). ''Avoiding Rotated Bitboards with Direct Lookup''. [[ICGA Journal#30_2|ICGA Journal, Vol. 30, No. 2]], [http://arxiv.org/PS_cache/arxiv/pdf/0704/0704.3773v2.pdf pdf] » [[Hashing Dictionaries]]
 
* [[Kumar Chellapilla]], [http://videolectures.net/anton_mityagin/ Anton Mityagin], [[Denis Xavier Charles]] ('''2007'''). ''[http://www2007.org/poster1018.php GigaHash: scalable minimal perfect hashing for billions of urls]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/www/www2007.html#ChellapillaMC07 WWW 2007]
 
* [[Kumar Chellapilla]], [http://videolectures.net/anton_mityagin/ Anton Mityagin], [[Denis Xavier Charles]] ('''2007'''). ''[http://www2007.org/poster1018.php GigaHash: scalable minimal perfect hashing for billions of urls]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/www/www2007.html#ChellapillaMC07 WWW 2007]
Line 92: Line 93:
 
* [[David Eppstein]], [[Mathematician#MTGoodrich|Michael T. Goodrich]], [[Mathematician#MMitzenmacher|Michael Mitzenmacher]], [https://dblp.uni-trier.de/pers/hd/p/Pszona:Pawel Paweł Pszona] ('''2014'''). ''Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket''. [https://arxiv.org/abs/1404.0286 arXiv:1404.0286]
 
* [[David Eppstein]], [[Mathematician#MTGoodrich|Michael T. Goodrich]], [[Mathematician#MMitzenmacher|Michael Mitzenmacher]], [https://dblp.uni-trier.de/pers/hd/p/Pszona:Pawel Paweł Pszona] ('''2014'''). ''Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket''. [https://arxiv.org/abs/1404.0286 arXiv:1404.0286]
 
* [[Thomas Dybdahl Ahle]], [[Mathematician#MAumueller|Martin Aumüller]], [[Mathematician#RPagh|Rasmus Pagh]] ('''2016'''). ''Parameter-free Locality Sensitive Hashing for Spherical Range Reporting''. [https://arxiv.org/abs/1605.02673 arXiv:1605.02673] <ref>[https://en.wikipedia.org/wiki/Locality-sensitive_hashing Locality-sensitive hashing from Wikipedia]</ref>
 
* [[Thomas Dybdahl Ahle]], [[Mathematician#MAumueller|Martin Aumüller]], [[Mathematician#RPagh|Rasmus Pagh]] ('''2016'''). ''Parameter-free Locality Sensitive Hashing for Spherical Range Reporting''. [https://arxiv.org/abs/1605.02673 arXiv:1605.02673] <ref>[https://en.wikipedia.org/wiki/Locality-sensitive_hashing Locality-sensitive hashing from Wikipedia]</ref>
 +
* [https://dblp.uni-trier.de/pers/hd/m/Maier:Tobias Tobias Maier], [[Peter Sanders]], [https://dblp.uni-trier.de/pers/hd/d/Dementiev:Roman Roman Dementiev] ('''2016'''). ''Concurrent Hash Tables: Fast and General?(!)''. [https://arxiv.org/abs/1601.04017 arXiv:1601.04017]
 
* [[Thomas Dybdahl Ahle]] ('''2017'''). ''Optimal Set Similarity Data-structures Without False Negatives''. Master thesis, [https://en.wikipedia.org/wiki/University_of_Copenhagen University of Copenhagen], [http://www.itu.dk/people/thdy/papers/minhash.pdf pdf] <ref>[https://en.wikipedia.org/wiki/MinHash MinHash from Wikipedia]</ref>
 
* [[Thomas Dybdahl Ahle]] ('''2017'''). ''Optimal Set Similarity Data-structures Without False Negatives''. Master thesis, [https://en.wikipedia.org/wiki/University_of_Copenhagen University of Copenhagen], [http://www.itu.dk/people/thdy/papers/minhash.pdf pdf] <ref>[https://en.wikipedia.org/wiki/MinHash MinHash from Wikipedia]</ref>
 +
* [https://dblp.uni-trier.de/pers/hd/m/Maier:Tobias Tobias Maier], [[Peter Sanders]] ('''2017'''). ''Dynamic Space Efficient Hashing''. [https://arxiv.org/abs/1705.00997  arXiv:1705.00997]
 +
* [[Peter Sanders]] ('''2018'''). ''Hashing with Linear Probing and Referential Integrity''. [https://arxiv.org/abs/1808.04602 arXiv:1808.04602]
 +
==2020 ...==
 +
* [[Niklas Fiekas]] ('''2020'''). ''[https://backscattering.de/chess/hashtable-packing/ The Hashtable Packing Problem]''. (Draft)
  
 
=Forum Posts=
 
=Forum Posts=
Line 118: Line 124:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65870 Magic end-game material hash?] by [[Harm Geert Muller]], [[CCC]], November 30, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65870 Magic end-game material hash?] by [[Harm Geert Muller]], [[CCC]], November 30, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66183 hashing in chess4j] by [[James Swafford]], [[CCC]], December 30, 2017 » [[chess4j]], [[Transposition Table]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=66183 hashing in chess4j] by [[James Swafford]], [[CCC]], December 30, 2017 » [[chess4j]], [[Transposition Table]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72932 hash collisions] by [[Jon Dart]], [[CCC]], January 28, 2020 » [[Transposition Table#KeyCollisions|Key Collisions]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72964 Dense board representation as hash code] by koedem, [[CCC]], February 01, 2020
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73071 Hashtable packing (e.g. to optimize magic bitboards) is strongly NP-complete] by [[Niklas Fiekas]], [[CCC]],  February 13, 2020 » [[Magic Bitboards]] <ref>[https://en.wikipedia.org/wiki/Strong_NP-completeness Strong NP-completeness from Wikipedia]</ref>
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73110 Zobrist key independence] by [[Harm Geert Muller]], [[CCC]], February 17, 2020 » [[Zobrist Hashing]]
  
 
=External Links=  
 
=External Links=  
Line 143: Line 154:
 
* [https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function Fowler–Noll–Vo hash function from Wikipedia]
 
* [https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function Fowler–Noll–Vo hash function from Wikipedia]
 
* [http://www.partow.net/programming/hashfunctions/index.html General Purpose Hash Function Algorithms] by [http://www.partow.net/about/index.html Arash Partow]
 
* [http://www.partow.net/programming/hashfunctions/index.html General Purpose Hash Function Algorithms] by [http://www.partow.net/about/index.html Arash Partow]
* [http://www.chessbin.com/post/Transposition-Table-and-Zobrist-Hashing.aspx Transposition Table and Zobrist Hashing] by [[Adam Berent]]
 
 
* [http://www.cse.yorku.ca/~oz/hash.html Hash Functions]
 
* [http://www.cse.yorku.ca/~oz/hash.html Hash Functions]
 
* [http://www.fantasy-coders.de/projects/gh/html/x435.html 7. Wahl einer geeigneten Hash-Funktion] from [http://www.fantasy-coders.de/projects/gh/html/index.html Guugelhupf - Design und Implementation] (German)
 
* [http://www.fantasy-coders.de/projects/gh/html/x435.html 7. Wahl einer geeigneten Hash-Funktion] from [http://www.fantasy-coders.de/projects/gh/html/index.html Guugelhupf - Design und Implementation] (German)

Revision as of 21:35, 17 February 2020

Home * Programming * Data * Hash Table

A small phone book as a hash table [1]

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.

Perfect Hashing

A perfect hash function [2]

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 [3] . 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

Minimal perfect hash function [4]

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 ...

2020 ...

Forum Posts

1998 ...

2000 ...

2005 ...

2010 ...

2015 ...

2020 ...

External Links

Secure Hash Algorithm from Wikipedia
Merkle–Damgård construction from Wikipedia
Koorde based on Chord and De Bruijn Sequence
Pierre Courbois, Jasper van 't Hof, Toto Blanke, Sigi Busch

References

Up one Level