25,161
edits
Changes
Created page with "'''Home * Programming * Data * Hash Table''' FILE:Hash table 3 1 1 0 1 0 0 SP.svg|border|right|thumb|A small phone book as a hash table <ref>[https://..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Hash Table'''
[[FILE:Hash table 3 1 1 0 1 0 0 SP.svg|border|right|thumb|A small phone book as a hash table <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
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 [https://en.wikipedia.org/wiki/Hash_function hash function] is used for turning the key into a relatively small integer, the hash, that serves as an index into an [[Array|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 [https://en.wikipedia.org/wiki/Cache cache] for once calculated values, to save relative expensive computations over and over again.
<span id="PerfectHashing"></span>
=Perfect Hashing=
[[FILE:Hash table 4 1 1 0 0 0 0 LL.svg|border|right|thumb|A perfect hash function <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
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|array]] contains either gaps or multiple entries.
Applications in computer chess are hashing of masked [[Occupancy|occupied bitboards]], to map for instance [[Sliding Piece Attacks|attack sets of sliding pieces]] ([[Rook|rooks]], [[Bishop|bishops]]) on a particular [[Squares|square]], or [[King Safety#PawnShield|pawn shield]] stuff. [[Material Tables|Another application]], despite a reversible hash function, is a precomputed table indexed by some [[Material|material]] key, likely an [[Incremental Updates|incremental updated]] [https://en.wikipedia.org/wiki/Dot_product 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|promotions]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010</ref> . Persistent, or on the fly generated [[Endgame Tablebases]] and [[Endgame Bitbases|Bitbases]] containing [[Knowledge#PerfectKnowledge|perfect knowledge]] by [[Retrograde Analysis|retrograde analyses]] of certain [[Material|material]] constellations with a few pieces in late endings might be considered as a kind of perfect hashing as well.
* [[BitScan#WalterFaxonsmagicBitscan|Walter Faxon's Magic BitScan]]
* [[BitScan#BitscanByModulo|BitScan by Modulo]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
* [[Hashing Dictionaries]]
* [[Congruent Modulo Bitboards]]
* [[Material Tables]]
* [[Pawn Shield Tables]]
* [[Endgame Tablebases]]
<span id="MinimalPerfectHashing"></span>
=Minimal Perfect Hashing=
[[FILE:Hash table 4 1 0 0 0 0 0 LL.svg|border|right|thumb|Minimal perfect hash function <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
If the hash [[Array|array]] has no gaps and unique, distinct values, so called Minimal Perfect Hashing is applied, like in following [[Bitboards|bitboard]] hashing for [[BitScan|bitscan]] purpose or determining pre-calculated [[Move List|move lists]] by [[Target Square|move target]] sets of [[Knight|knights]] and [[King|king]].
* [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]]
* [[BitScan#MattTaylorsFoldingtrick|Matt Taylor's Folding trick]]
* [[Bitboard Serialization#HashingMultipleBits|Hashing Multiple Bits]] for [[Bitboard Serialization]]
<span id="SearchTables"></span>
=Search Tables=
The classical hash table implementation in computer chess are the [[Transposition Table|transposition tables]], indexed by [[Zobrist Hashing|Zobrist]]- or [[BCH Hashing|BCH keys]] of the position, modulo number of entries inside the table, to store [[Search|search]] results, [[Evaluation|evaluation]], [[Pawn Structure|pawn structure]] related stuff and [[Repetitions|repetitions]].
* [[Transposition Table]]
* [[Pawn Hash Table]]
* [[Evaluation Hash Table]]
* [[Material Hash Table]]
* [[Persistent Hash Table]]
* [[Repetitions#RepetitionHashTable|Repetition Hash Table]]
* [[Shared Hash Table]]
=Class Libraries=
* [http://doc.trolltech.com/2.3/qmap.html QMap Class Reference], [[Cpp|C++]] from [http://doc.trolltech.com/2.3/index.html Qt On-line Reference Documentation]
* [http://msdn.microsoft.com/en-us/library/s897094z%28VS.80%29.aspx CMap Class], [[Cpp|C++]] from [http://msdn.microsoft.com/en-us/library/d06h2x6e%28VS.80%29.aspx MFC Library Reference]
* [http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html Interface Map] from the [[Java]] package [http://java.sun.com/j2se/1.4.2/docs/api/java/util/package-summary.html java.util]
* [http://docs.python.org/lib/module-UserDict.html UserDict - Class wrapper for dictionary objects] from [http://docs.python.org/lib/lib.html Python Library Reference]
* [http://docs.python.org/lib/defaultdict-objects.html defaultdict objects] from [http://docs.python.org/lib/lib.html Python Library Reference]
=Publications=
==1968==
* [[Ward Douglas Maurer]] ('''1968'''). ''[http://dl.acm.org/citation.cfm?id=357995 An Improved Hash Code for Scatter Storage]''. [[ACM#Communications|Communications of the ACM]], Vol. 11, No. 1
* [[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory'', New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon]
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood] ('''1968'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p008.htm A Solution to the table overflow problem for Hash Tables]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
==1970 ...==
* [[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 [[ICGA Journal#13_3|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]
* [https://en.wikipedia.org/wiki/Bloom_filter Burton H. Bloom] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362692 Space/time trade-offs in hash coding with allowable errors]''. Comm. of the ACM, Vol. 13, No. 7, [http://www.lsi.upc.edu/%7Ediaz/p422-bloom.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bloom_filter Bloom filter from Wikipedia]</ref>
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood], [http://people.bath.ac.uk/masjhd/ J. Davenport] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p012.htm The quadratic hash method when the table size is a power of 2]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood] ('''1974'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p007.htm Computer Animation used as a Tool in Teaching Computer Science]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Amble:Ole.html Ole Amble], [[Donald Knuth]] ('''1974'''). ''Ordered Hash Tables''. [https://en.wikipedia.org/wiki/The_Computer_Journal The Computer Journal], Vol. 17
* [[Ward Douglas Maurer]], [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Lewis:Ted_G= Ted G. Lewis] ('''1975'''). ''[http://dl.acm.org/citation.cfm?doid=356643.356645 Hash Table Methods]''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 7, No. 1
* [[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]
==1980 ...==
* [[Harry Nelson]] ('''1985'''). ''Hash Tables in Cray Blitz''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]] » [[Cray Blitz]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[Mathematician#IDamgard|Ivan Damgård]] ('''1989'''). ''A Design Principle for Hash Functions''. [http://www.informatik.uni-trier.de/~ley/db/conf/crypto/crypto89.html CRYPTO '89]
* [[Mathematician#RMerkle|Ralph C. Merkle]] ('''1989'''). ''One Way Hash Functions and DES''. [http://www.informatik.uni-trier.de/~ley/db/conf/crypto/crypto89.html CRYPTO '89] <ref>[https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction Merkle–Damgård construction from Wikipedia]</ref>
==1990 ...==
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://itee.uq.edu.au/~havas/ George Havas], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Majewski:Bohdan_S=.html Bohdan S. Majewski] ('''1992'''). ''An Optimal Algorithm for Generating Minimal Perfect Hash Functions''. Information Processing Letters, Vol. 43, pp. 257–264. [http://cmph.sourceforge.net/papers/chm92.pdf pdf]
* [[Warren D. Smith]] ('''1992'''). ''Hash functions for Binary and Ternary Words''. [https://en.wikipedia.org/wiki/NEC_Corporation_of_America NEC Research Institute], [http://scorevoting.net/WarrenSmithPages/homepage/gohash.ps ps]
* [[Mathematician#MDietzfelbinger|Martin Dietzfelbinger]], [https://en.wikipedia.org/wiki/Anna_Karlin Anna Karlin], [[Mathematician#KMehlhorn|Kurt Mehlhorn]], [[Mathematician#FMeyerAdH|Friedhelm Meyer auf der Heide]], [https://plus.google.com/105803273623353288634/posts Hans Rohnert], [[Mathematician#RETarjan|Robert E. Tarjan]] ('''1994'''). ''[http://epubs.siam.org/doi/abs/10.1137/S0097539791194094 Dynamic Perfect Hashing: Upper and Lower Bounds]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing SIAM Journal on Computing], Vol. 23, Nr. 4
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://itee.uq.edu.au/~havas/ George Havas], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Majewski:Bohdan_S=.html Bohdan S. Majewski] ('''1997'''). ''Perfect Hashing''. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-143
* [[Bob Jenkins]] ('''1997'''). ''Hash functions''. [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], September 1997 <ref>[http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] by [[Bob Jenkins]], updated [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's] article</ref>
* [[Donald Knuth|Donald E. Knuth]] ('''1998'''). ''[http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art of Computer Programming]''. Volume 3 - Sorting and Searching, 6.4 about universal hashing, (second edition), [http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 amazom]
* [[Dennis Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/ Memory versus Search in Games]''. Ph.D. Thesis, [[Maastricht University|Universiteit Maastricht]], The Netherlands. ISBN 90-9012006-8.
* [[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word'', [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf] » [[BitScan]]
==2000 ...==
* [[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]]
* [[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]
* [[Trevor Fenner]], [[Mark Levene]] ('''2008'''). ''Move Generation with Perfect Hashing Functions.'' [[ICGA Journal#31_1|ICGA Journal, Vol. 31, No. 1]], [http://www.dcs.bbk.ac.uk/~mark/download/bitboard_sliding_icga_final.pdf pdf] » [[Congruent Modulo Bitboards]]
==2010 ...==
* [[Jiao Wang]], [[Si-Zhong Li]], [[Xinhe Xu|Xin-He Xu]] ('''2010'''). ''A Minors Hash Table in Chinese-Chess Programs''. [[ICGA Journal#33_1|ICGA Journal, Vol. 33, No. 1]]
* [[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]
* [[Dan Anthony Feliciano Alcantara]] ('''2011'''). ''Effcient Hash Tables on the GPU''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_California,_Davis University of California, Davis], [http://idav.ucdavis.edu/~dfalcant//downloads/dissertation.pdf pdf] » [[GPU]]
* [[Maurizio Monge]] ('''2011'''). ''[http://scholar.google.com/citations?view_op=view_citation&hl=en&user=gpgb4LgAAAAJ&citation_for_view=gpgb4LgAAAAJ:UeHWp8X0CEIC On perfect hashing of numbers with sparse digit representation via multiplication by a constant]''. [http://www.sciencedirect.com/science/article/pii/S0166218X11000837 Discrete Applied Mathematics, Vol. 159, No. 11] » [[Magic Bitboards]]
* [[John Tromp]] ('''2014'''). ''[https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf Cuckoo Cycle: a memory-hard proof-of-work system]''. [http://www.informatik.uni-trier.de/~ley/db/journals/iacr/iacr2014.html#Tromp14 IACR Cryptology ePrint Archive] <ref>[https://bitcointalk.org/index.php?topic=405483.0 Cuckoo Cycle: a new memory-hard proof-of-work system] by [[John Tromp]], [https://bitcointalk.org/index.php Bitcoin Forum], January 08, 2014</ref> <ref>[https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]</ref>
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998 » [[Zobrist Hashing]]
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=14226 Hash tables and data-cache, some programmer stuff...] by [[Ed Schroder|Ed Schröder]], [[CCC]], January 17, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=175221 A fast hash -- assuming you are not planning to do incremental updates] by [[Dann Corbit]], [[CCC]], June 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=214125 Non power of two hash table sizes] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], February 18, 2002
==2005 ...==
* [http://www.hiarcs.net/forums/viewtopic.php?p=2921 What is the Difference between Mainhash, Evalhash, Pawnhash?] by Thomas Wallendik, [[Computer Chess Forums|Hiarcs Forum]], October 13, 2007
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=285407 Cache pollution when reading/writing hash table] by [[Marco Costalba]], [[CCC]], August 09, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012 » [[Transposition Table#KeyCollisions|Key Collisions]], [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48479 Hashing based on move lists] by [[Matthew R. Brades]], [[CCC]], June 30, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57924 Hash cache] by [[Harm Geert Muller]], [[CCC]], October 12, 2015 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=58944 Crafty's four hash tables] by [[Louis Zulli]], [[CCC]], January 17, 2016 » [[Crafty]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61328 Hashed repetition table] by [[J. Wesley Cleveland]], [[CCC]], September 04, 2016 » [[Repetitions#RepetitionHashTable|Repetition Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62239 Hashing a quadboard from scratch] by [[Edoardo Manino]], [[CCC]], November 23, 2016 » [[Quad-Bitboards]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Hash_table Hash Table from Wikipedia]
* [https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]
* [https://en.wikipedia.org/wiki/Perfect_hash_function Perfect hash function from Wikipedia]
* [https://en.wikipedia.org/wiki/Cryptographic_hash_function Cryptographic hash function from Wikipedia]
: [https://en.wikipedia.org/wiki/Secure_Hash_Algorithm Secure Hash Algorithm from Wikipedia]
: [https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction Merkle–Damgård construction from Wikipedia]
* [http://www.gnu.org/software/gperf/ gperf - GNU Project] - [[Free Software Foundation]]
* [https://en.wikipedia.org/wiki/Transposition_table Transposition table from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Distributed_hash_table Distributed hash table from Wikipedia]
: [https://en.wikipedia.org/wiki/Koorde Koorde] based on [https://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29 Chord] and [[De Bruijn sequence]]
* [https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]
* [https://en.wikipedia.org/wiki/Hashlife Hashlife from Wikipedia] by [[Bill Gosper]] <ref>[http://www-users.cs.york.ac.uk/~jowen/hashlife.html Gosper's Algorithm (Hashlife) explained]</ref>
* [http://www.concentric.net/~Ttwang/tech/inthash.htm Integer Hash Function] by [http://www.concentric.net/~ttwang/index.html Thomas Wang]
* [http://www.azillionmonkeys.com/qed/hash.html Hash functions] by [[Paul Hsieh]]
* [http://burtleburtle.net/bob/hash/index.html Hash Functions and Block Ciphers] by [[Bob Jenkins]]
* [http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] by [[Bob Jenkins]]
* [http://burtleburtle.net/bob/hash/perfect.html Perfect Hashing] by [[Bob Jenkins]]
* [https://en.wikipedia.org/wiki/Jenkins_hash_function Jenkins 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.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.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)
* [[Videos#AssociationPC|Association P.C.]] - Soft Time in a Life Machine, [https://en.wikipedia.org/wiki/JazzFest_Berlin Berliner Jazztage], November 7, 1971, [https://en.wikipedia.org/wiki/Norddeutscher_Rundfunk NDR]-[https://en.wikipedia.org/wiki/Radio_Bremen RB]-[https://en.wikipedia.org/wiki/Sender_Freies_Berlin SFB] 3 Broadcast, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#PierreCourbois|Pierre Courbois]], [[Videos#JasperVantHof|Jasper van 't Hof]], [[Videos#TotoBlanke|Toto Blanke]], [https://de.wikipedia.org/wiki/Sigi_Busch Sigi Busch]
: {{#evu:https://www.youtube.com/watch?v=_RvR7oG8Uz4|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
[[FILE:Hash table 3 1 1 0 1 0 0 SP.svg|border|right|thumb|A small phone book as a hash table <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
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 [https://en.wikipedia.org/wiki/Hash_function hash function] is used for turning the key into a relatively small integer, the hash, that serves as an index into an [[Array|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 [https://en.wikipedia.org/wiki/Cache cache] for once calculated values, to save relative expensive computations over and over again.
<span id="PerfectHashing"></span>
=Perfect Hashing=
[[FILE:Hash table 4 1 1 0 0 0 0 LL.svg|border|right|thumb|A perfect hash function <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
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|array]] contains either gaps or multiple entries.
Applications in computer chess are hashing of masked [[Occupancy|occupied bitboards]], to map for instance [[Sliding Piece Attacks|attack sets of sliding pieces]] ([[Rook|rooks]], [[Bishop|bishops]]) on a particular [[Squares|square]], or [[King Safety#PawnShield|pawn shield]] stuff. [[Material Tables|Another application]], despite a reversible hash function, is a precomputed table indexed by some [[Material|material]] key, likely an [[Incremental Updates|incremental updated]] [https://en.wikipedia.org/wiki/Dot_product 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|promotions]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010</ref> . Persistent, or on the fly generated [[Endgame Tablebases]] and [[Endgame Bitbases|Bitbases]] containing [[Knowledge#PerfectKnowledge|perfect knowledge]] by [[Retrograde Analysis|retrograde analyses]] of certain [[Material|material]] constellations with a few pieces in late endings might be considered as a kind of perfect hashing as well.
* [[BitScan#WalterFaxonsmagicBitscan|Walter Faxon's Magic BitScan]]
* [[BitScan#BitscanByModulo|BitScan by Modulo]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
* [[Hashing Dictionaries]]
* [[Congruent Modulo Bitboards]]
* [[Material Tables]]
* [[Pawn Shield Tables]]
* [[Endgame Tablebases]]
<span id="MinimalPerfectHashing"></span>
=Minimal Perfect Hashing=
[[FILE:Hash table 4 1 0 0 0 0 0 LL.svg|border|right|thumb|Minimal perfect hash function <ref>[https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]</ref> ]]
If the hash [[Array|array]] has no gaps and unique, distinct values, so called Minimal Perfect Hashing is applied, like in following [[Bitboards|bitboard]] hashing for [[BitScan|bitscan]] purpose or determining pre-calculated [[Move List|move lists]] by [[Target Square|move target]] sets of [[Knight|knights]] and [[King|king]].
* [[BitScan#DeBruijnMultiplation|De Bruijn Multiplication]]
* [[BitScan#MattTaylorsFoldingtrick|Matt Taylor's Folding trick]]
* [[Bitboard Serialization#HashingMultipleBits|Hashing Multiple Bits]] for [[Bitboard Serialization]]
<span id="SearchTables"></span>
=Search Tables=
The classical hash table implementation in computer chess are the [[Transposition Table|transposition tables]], indexed by [[Zobrist Hashing|Zobrist]]- or [[BCH Hashing|BCH keys]] of the position, modulo number of entries inside the table, to store [[Search|search]] results, [[Evaluation|evaluation]], [[Pawn Structure|pawn structure]] related stuff and [[Repetitions|repetitions]].
* [[Transposition Table]]
* [[Pawn Hash Table]]
* [[Evaluation Hash Table]]
* [[Material Hash Table]]
* [[Persistent Hash Table]]
* [[Repetitions#RepetitionHashTable|Repetition Hash Table]]
* [[Shared Hash Table]]
=Class Libraries=
* [http://doc.trolltech.com/2.3/qmap.html QMap Class Reference], [[Cpp|C++]] from [http://doc.trolltech.com/2.3/index.html Qt On-line Reference Documentation]
* [http://msdn.microsoft.com/en-us/library/s897094z%28VS.80%29.aspx CMap Class], [[Cpp|C++]] from [http://msdn.microsoft.com/en-us/library/d06h2x6e%28VS.80%29.aspx MFC Library Reference]
* [http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html Interface Map] from the [[Java]] package [http://java.sun.com/j2se/1.4.2/docs/api/java/util/package-summary.html java.util]
* [http://docs.python.org/lib/module-UserDict.html UserDict - Class wrapper for dictionary objects] from [http://docs.python.org/lib/lib.html Python Library Reference]
* [http://docs.python.org/lib/defaultdict-objects.html defaultdict objects] from [http://docs.python.org/lib/lib.html Python Library Reference]
=Publications=
==1968==
* [[Ward Douglas Maurer]] ('''1968'''). ''[http://dl.acm.org/citation.cfm?id=357995 An Improved Hash Code for Scatter Storage]''. [[ACM#Communications|Communications of the ACM]], Vol. 11, No. 1
* [[Elwyn Berlekamp]] ('''1968'''). ''Algebraic Coding Theory'', New York: McGraw-Hill. Revised ed., Aegean Park Press, ('''1984'''), ISBN 0894120638. [http://www.amazon.com/Algebraic-Coding-Theory-Revised-M-6/dp/0894120638 amazon]
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood] ('''1968'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p008.htm A Solution to the table overflow problem for Hash Tables]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
==1970 ...==
* [[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 [[ICGA Journal#13_3|ICCA Journal, Vol. 13, No. 2]], [http://www.cs.wisc.edu/techreports/1970/TR88.pdf pdf]
* [https://en.wikipedia.org/wiki/Bloom_filter Burton H. Bloom] ('''1970'''). ''[http://portal.acm.org/citation.cfm?id=362692 Space/time trade-offs in hash coding with allowable errors]''. Comm. of the ACM, Vol. 13, No. 7, [http://www.lsi.upc.edu/%7Ediaz/p422-bloom.pdf pdf] <ref>[https://en.wikipedia.org/wiki/Bloom_filter Bloom filter from Wikipedia]</ref>
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood], [http://people.bath.ac.uk/masjhd/ J. Davenport] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p012.htm The quadratic hash method when the table size is a power of 2]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
* [http://www.bahfrah.org.uk/bio/index.htm F R A Hopgood] ('''1974'''). ''[http://www.chilton-computing.org.uk/acl/literature/reports/p007.htm Computer Animation used as a Tool in Teaching Computer Science]''. [http://www.chilton-computing.org.uk/acl/literature/reports/overview.htm Literature: Reports] hosted by [[Atlas Computer Laboratory]]
* [http://www.informatik.uni-trier.de/~ley/pers/hd/a/Amble:Ole.html Ole Amble], [[Donald Knuth]] ('''1974'''). ''Ordered Hash Tables''. [https://en.wikipedia.org/wiki/The_Computer_Journal The Computer Journal], Vol. 17
* [[Ward Douglas Maurer]], [http://www.informatik.uni-trier.de/~ley/pers/hd/l/Lewis:Ted_G= Ted G. Lewis] ('''1975'''). ''[http://dl.acm.org/citation.cfm?doid=356643.356645 Hash Table Methods]''. [[ACM#Surveys|ACM Computing Surveys]], Vol. 7, No. 1
* [[Mathematician#JLCarter|J. Lawrence Carter]], [[Mathematician#MNWegman|Mark N. Wegman]] ('''1977'''). ''[http://dl.acm.org/citation.cfm?id=803400 Universal classes of hash functions]''. [http://dl.acm.org/citation.cfm?id=800105 STOC '77]
==1980 ...==
* [[Harry Nelson]] ('''1985'''). ''Hash Tables in Cray Blitz''. [[ICGA Journal#8_1|ICCA Journal, Vol. 8, No. 1]] » [[Cray Blitz]]
* [[Tony Warnock]], [[Burton Wendroff]] ('''1988'''). ''Search Tables in Computer Chess''. [[ICGA Journal#11_1|ICCA Journal, Vol. 11, No. 1]]
* [[Mathematician#IDamgard|Ivan Damgård]] ('''1989'''). ''A Design Principle for Hash Functions''. [http://www.informatik.uni-trier.de/~ley/db/conf/crypto/crypto89.html CRYPTO '89]
* [[Mathematician#RMerkle|Ralph C. Merkle]] ('''1989'''). ''One Way Hash Functions and DES''. [http://www.informatik.uni-trier.de/~ley/db/conf/crypto/crypto89.html CRYPTO '89] <ref>[https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction Merkle–Damgård construction from Wikipedia]</ref>
==1990 ...==
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://itee.uq.edu.au/~havas/ George Havas], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Majewski:Bohdan_S=.html Bohdan S. Majewski] ('''1992'''). ''An Optimal Algorithm for Generating Minimal Perfect Hash Functions''. Information Processing Letters, Vol. 43, pp. 257–264. [http://cmph.sourceforge.net/papers/chm92.pdf pdf]
* [[Warren D. Smith]] ('''1992'''). ''Hash functions for Binary and Ternary Words''. [https://en.wikipedia.org/wiki/NEC_Corporation_of_America NEC Research Institute], [http://scorevoting.net/WarrenSmithPages/homepage/gohash.ps ps]
* [[Mathematician#MDietzfelbinger|Martin Dietzfelbinger]], [https://en.wikipedia.org/wiki/Anna_Karlin Anna Karlin], [[Mathematician#KMehlhorn|Kurt Mehlhorn]], [[Mathematician#FMeyerAdH|Friedhelm Meyer auf der Heide]], [https://plus.google.com/105803273623353288634/posts Hans Rohnert], [[Mathematician#RETarjan|Robert E. Tarjan]] ('''1994'''). ''[http://epubs.siam.org/doi/abs/10.1137/S0097539791194094 Dynamic Perfect Hashing: Upper and Lower Bounds]''. [https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing SIAM Journal on Computing], Vol. 23, Nr. 4
* [http://sun.aei.polsl.pl/~zjc/ Zbigniew J. Czech], [http://itee.uq.edu.au/~havas/ George Havas], [http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/m/Majewski:Bohdan_S=.html Bohdan S. Majewski] ('''1997'''). ''Perfect Hashing''. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-143
* [[Bob Jenkins]] ('''1997'''). ''Hash functions''. [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's Journal], September 1997 <ref>[http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] by [[Bob Jenkins]], updated [https://en.wikipedia.org/wiki/Dr._Dobb%27s_Journal Dr. Dobb's] article</ref>
* [[Donald Knuth|Donald E. Knuth]] ('''1998'''). ''[http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art of Computer Programming]''. Volume 3 - Sorting and Searching, 6.4 about universal hashing, (second edition), [http://www.amazon.com/Art-Computer-Programming-Sorting-Searching/dp/0201896850 amazom]
* [[Dennis Breuker]] ('''1998'''). ''[http://www.dennisbreuker.nl/thesis/ Memory versus Search in Games]''. Ph.D. Thesis, [[Maastricht University|Universiteit Maastricht]], The Netherlands. ISBN 90-9012006-8.
* [[Charles Leiserson|Charles E. Leiserson]], [[Harald Prokop]], [[Keith H. Randall]] ('''1998'''). ''Using de Bruijn Sequences to Index a 1 in a Computer Word'', [http://supertech.csail.mit.edu/papers/debruijn.pdf pdf] » [[BitScan]]
==2000 ...==
* [[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]]
* [[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]
* [[Trevor Fenner]], [[Mark Levene]] ('''2008'''). ''Move Generation with Perfect Hashing Functions.'' [[ICGA Journal#31_1|ICGA Journal, Vol. 31, No. 1]], [http://www.dcs.bbk.ac.uk/~mark/download/bitboard_sliding_icga_final.pdf pdf] » [[Congruent Modulo Bitboards]]
==2010 ...==
* [[Jiao Wang]], [[Si-Zhong Li]], [[Xinhe Xu|Xin-He Xu]] ('''2010'''). ''A Minors Hash Table in Chinese-Chess Programs''. [[ICGA Journal#33_1|ICGA Journal, Vol. 33, No. 1]]
* [[Mathematician#MPatrascu|Mihai Pătrașcu]], [[Mathematician#MThorup|Mikkel Thorup]] ('''2011'''). ''The Power of Simple Tabulation Hashing''. [http://arxiv.org/abs/1011.5200 arXiv:1011.5200v2]
* [[Dan Anthony Feliciano Alcantara]] ('''2011'''). ''Effcient Hash Tables on the GPU''. Ph.D. thesis, [https://en.wikipedia.org/wiki/University_of_California,_Davis University of California, Davis], [http://idav.ucdavis.edu/~dfalcant//downloads/dissertation.pdf pdf] » [[GPU]]
* [[Maurizio Monge]] ('''2011'''). ''[http://scholar.google.com/citations?view_op=view_citation&hl=en&user=gpgb4LgAAAAJ&citation_for_view=gpgb4LgAAAAJ:UeHWp8X0CEIC On perfect hashing of numbers with sparse digit representation via multiplication by a constant]''. [http://www.sciencedirect.com/science/article/pii/S0166218X11000837 Discrete Applied Mathematics, Vol. 159, No. 11] » [[Magic Bitboards]]
* [[John Tromp]] ('''2014'''). ''[https://github.com/tromp/cuckoo/blob/master/cuckoo.pdf Cuckoo Cycle: a memory-hard proof-of-work system]''. [http://www.informatik.uni-trier.de/~ley/db/journals/iacr/iacr2014.html#Tromp14 IACR Cryptology ePrint Archive] <ref>[https://bitcointalk.org/index.php?topic=405483.0 Cuckoo Cycle: a new memory-hard proof-of-work system] by [[John Tromp]], [https://bitcointalk.org/index.php Bitcoin Forum], January 08, 2014</ref> <ref>[https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]</ref>
=Forum Posts=
==1998 ...==
* [https://www.stmintz.com/ccc/index.php?id=13810 Fast hash algorithm] by John Scalo, [[CCC]], January 08, 1998 » [[Zobrist Hashing]]
* [https://www.stmintz.com/ccc/index.php?id=14053 Fast hash key method - Revisited!] by John Scalo, [[CCC]], January 14, 1998
* [https://www.stmintz.com/ccc/index.php?id=14226 Hash tables and data-cache, some programmer stuff...] by [[Ed Schroder|Ed Schröder]], [[CCC]], January 17, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=175221 A fast hash -- assuming you are not planning to do incremental updates] by [[Dann Corbit]], [[CCC]], June 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=214125 Non power of two hash table sizes] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], February 18, 2002
==2005 ...==
* [http://www.hiarcs.net/forums/viewtopic.php?p=2921 What is the Difference between Mainhash, Evalhash, Pawnhash?] by Thomas Wallendik, [[Computer Chess Forums|Hiarcs Forum]], October 13, 2007
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=285407 Cache pollution when reading/writing hash table] by [[Marco Costalba]], [[CCC]], August 09, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33561 Cache-friendier material index] by [[Harm Geert Muller]], [[CCC]], March 31, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=44082 how to measure frequency of hash collisions] by [[Daniel Shawul]], [[CCC]], June 16, 2012 » [[Transposition Table#KeyCollisions|Key Collisions]], [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=48479 Hashing based on move lists] by [[Matthew R. Brades]], [[CCC]], June 30, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=57924 Hash cache] by [[Harm Geert Muller]], [[CCC]], October 12, 2015 » [[Transposition Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=58890 On-the fly hash key generation?] by [[Evert Glebbeek]], [[CCC]], January 12, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=58944 Crafty's four hash tables] by [[Louis Zulli]], [[CCC]], January 17, 2016 » [[Crafty]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61328 Hashed repetition table] by [[J. Wesley Cleveland]], [[CCC]], September 04, 2016 » [[Repetitions#RepetitionHashTable|Repetition Hash Table]]
* [http://www.talkchess.com/forum/viewtopic.php?t=62239 Hashing a quadboard from scratch] by [[Edoardo Manino]], [[CCC]], November 23, 2016 » [[Quad-Bitboards]]
* [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]]
=External Links=
* [https://en.wikipedia.org/wiki/Hash_table Hash Table from Wikipedia]
* [https://en.wikipedia.org/wiki/Hash_function Hash function from Wikipedia]
* [https://en.wikipedia.org/wiki/Perfect_hash_function Perfect hash function from Wikipedia]
* [https://en.wikipedia.org/wiki/Cryptographic_hash_function Cryptographic hash function from Wikipedia]
: [https://en.wikipedia.org/wiki/Secure_Hash_Algorithm Secure Hash Algorithm from Wikipedia]
: [https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction Merkle–Damgård construction from Wikipedia]
* [http://www.gnu.org/software/gperf/ gperf - GNU Project] - [[Free Software Foundation]]
* [https://en.wikipedia.org/wiki/Transposition_table Transposition table from Wikipedia]
* [https://en.wikipedia.org/wiki/Tabulation_hashing Tabulation hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Zobrist_hashing Zobrist hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Cuckoo_hashing Cuckoo hashing from Wikipedia]
* [https://en.wikipedia.org/wiki/Distributed_hash_table Distributed hash table from Wikipedia]
: [https://en.wikipedia.org/wiki/Koorde Koorde] based on [https://en.wikipedia.org/wiki/Chord_%28peer-to-peer%29 Chord] and [[De Bruijn sequence]]
* [https://en.wikipedia.org/wiki/Transposition-driven_scheduling Transposition-driven scheduling - Wikipedia]
* [https://en.wikipedia.org/wiki/Hashlife Hashlife from Wikipedia] by [[Bill Gosper]] <ref>[http://www-users.cs.york.ac.uk/~jowen/hashlife.html Gosper's Algorithm (Hashlife) explained]</ref>
* [http://www.concentric.net/~Ttwang/tech/inthash.htm Integer Hash Function] by [http://www.concentric.net/~ttwang/index.html Thomas Wang]
* [http://www.azillionmonkeys.com/qed/hash.html Hash functions] by [[Paul Hsieh]]
* [http://burtleburtle.net/bob/hash/index.html Hash Functions and Block Ciphers] by [[Bob Jenkins]]
* [http://burtleburtle.net/bob/hash/doobs.html A Hash Function for Hash Table Lookup] by [[Bob Jenkins]]
* [http://burtleburtle.net/bob/hash/perfect.html Perfect Hashing] by [[Bob Jenkins]]
* [https://en.wikipedia.org/wiki/Jenkins_hash_function Jenkins 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.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.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)
* [[Videos#AssociationPC|Association P.C.]] - Soft Time in a Life Machine, [https://en.wikipedia.org/wiki/JazzFest_Berlin Berliner Jazztage], November 7, 1971, [https://en.wikipedia.org/wiki/Norddeutscher_Rundfunk NDR]-[https://en.wikipedia.org/wiki/Radio_Bremen RB]-[https://en.wikipedia.org/wiki/Sender_Freies_Berlin SFB] 3 Broadcast, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#PierreCourbois|Pierre Courbois]], [[Videos#JasperVantHof|Jasper van 't Hof]], [[Videos#TotoBlanke|Toto Blanke]], [https://de.wikipedia.org/wiki/Sigi_Busch Sigi Busch]
: {{#evu:https://www.youtube.com/watch?v=_RvR7oG8Uz4|alignment=left|valignment=top}}
=References=
<references />
'''[[Data|Up one Level]]'''
