Difference between revisions of "Hash Table"
GerdIsenberg (talk | contribs) |
GerdIsenberg (talk | contribs) |
||
(9 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] | ||
* [[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]] | * [[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 ...== | ==2010 ...== | ||
+ | * [[Maurizio Monge]] ('''2010'''). ''On perfect hashing of numbers with sparse digit representation via multiplication by a constant''. [https://arxiv.org/abs/1003.3196 arXiv:1003.3196] » [[Magic Bitboards]] | ||
* [[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]] | * [[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] | * [[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]] | * [[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]] | ||
− | |||
* [[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> | * [[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> | ||
+ | * [[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> | ||
+ | * [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> | ||
+ | * [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 100: | Line 109: | ||
* [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 | * [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 ...== | ==2005 ...== | ||
+ | * [https://www.stmintz.com/ccc/index.php?id=484874 Hash table and O(1)] by [[Dann Corbit]], [[CCC]], February 06, 2006 | ||
* [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.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 | * [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 | ||
Line 114: | 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 139: | 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.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) | ||
− | * [[ | + | * [[:Category:Association P.C.|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 |
− | : [[ | + | : [[:Category:Pierre Courbois|Pierre Courbois]], [[:Category:Jasper van 't Hof|Jasper van 't Hof]], [[:Category:Toto Blanke|Toto Blanke]], [https://de.wikipedia.org/wiki/Sigi_Busch Sigi Busch] |
: {{#evu:https://www.youtube.com/watch?v=_RvR7oG8Uz4|alignment=left|valignment=top}} | : {{#evu:https://www.youtube.com/watch?v=_RvR7oG8Uz4|alignment=left|valignment=top}} | ||
Line 150: | Line 164: | ||
'''[[Data|Up one Level]]''' | '''[[Data|Up one Level]]''' | ||
+ | [[Category:Association P.C.]] | ||
+ | [[Category:Pierre Courbois]] | ||
+ | [[Category:Jasper van 't Hof|Jasper van 't Hof]] | ||
+ | [[Category:Toto Blanke]] |
Revision as of 22:35, 17 February 2020
Home * Programming * Data * Hash Table
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.
Contents
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 [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.
- Walter Faxon's Magic BitScan
- BitScan by Modulo
- Kindergarten Bitboards
- Magic Bitboards
- Hashing Dictionaries
- Congruent Modulo Bitboards
- Material Tables
- Pawn Shield Tables
- Endgame Tablebases
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.
- De Bruijn Multiplication
- Matt Taylor's Folding trick
- Hashing Multiple Bits for Bitboard Serialization
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.
- Transposition Table
- Pawn Hash Table
- Evaluation Hash Table
- Material Hash Table
- Persistent Hash Table
- Repetition Hash Table
- Shared Hash Table
Class Libraries
- QMap Class Reference, C++ from Qt On-line Reference Documentation
- CMap Class, C++ from MFC Library Reference
- Interface Map from the Java package java.util
- UserDict - Class wrapper for dictionary objects from Python Library Reference
- defaultdict objects from Python Library Reference
Publications
1968
- Ward Douglas Maurer (1968). An Improved Hash Code for Scatter Storage. 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. amazon
- F R A Hopgood (1968). A Solution to the table overflow problem for Hash Tables. 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 ICCA Journal, Vol. 13, No. 2, pdf
- Burton H. Bloom (1970). Space/time trade-offs in hash coding with allowable errors. Comm. of the ACM, Vol. 13, No. 7, pdf [5]
- F R A Hopgood, J. Davenport (1972). The quadratic hash method when the table size is a power of 2. Literature: Reports hosted by Atlas Computer Laboratory
- F R A Hopgood (1974). Computer Animation used as a Tool in Teaching Computer Science. Literature: Reports hosted by Atlas Computer Laboratory
- Ole Amble, Donald Knuth (1974). Ordered Hash Tables. The Computer Journal, Vol. 17
- Ward Douglas Maurer, Ted G. Lewis (1975). Hash Table Methods. ACM Computing Surveys, Vol. 7, No. 1
- J. Lawrence Carter, Mark N. Wegman (1977). Universal classes of hash functions. STOC '77
1980 ...
- Harry Nelson (1985). Hash Tables in Cray Blitz. ICCA Journal, Vol. 8, No. 1 » Cray Blitz
- Tony Warnock, Burton Wendroff (1988). Search Tables in Computer Chess. ICCA Journal, Vol. 11, No. 1
- Ivan Damgård (1989). A Design Principle for Hash Functions. CRYPTO '89
- Ralph C. Merkle (1989). One Way Hash Functions and DES. CRYPTO '89 [6]
1990 ...
- Zbigniew J. Czech, George Havas, Bohdan S. Majewski (1992). An Optimal Algorithm for Generating Minimal Perfect Hash Functions. Information Processing Letters, Vol. 43, pp. 257–264. pdf
- Warren D. Smith (1992). Hash functions for Binary and Ternary Words. NEC Research Institute, ps
- Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert E. Tarjan (1994). Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM Journal on Computing, Vol. 23, Nr. 4
- Zbigniew J. Czech, George Havas, Bohdan S. Majewski (1997). Perfect Hashing. Theoretical Computer Science, Vol. 182, Nos. 1-2, pp. 1-143
- Bob Jenkins (1997). Hash functions. Dr. Dobb's Journal, September 1997 [7]
- Donald E. Knuth (1998). The Art of Computer Programming. Volume 3 - Sorting and Searching, 6.4 about universal hashing, (second edition), amazom
- Dennis Breuker (1998). Memory versus Search in Games. Ph.D. Thesis, Universiteit Maastricht, The Netherlands. ISBN 90-9012006-8.
- Charles E. Leiserson, Harald Prokop, Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf » BitScan
2000 ...
- Robert Hyatt, Tim Mann (2002). A lock-less transposition table implementation for parallel search chess engines. ICGA Journal, Vol. 25, No. 1 » Shared Hash Table - Lock-less
- Robert Hyatt, Anthony Cozzie (2005). The Effect of Hash Signature Collisions in a Chess Program. ICGA Journal, Vol. 28, No. 3
- Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul Spirakis (2005). Space Efficient Hash Tables with Worst Case Constant Access Time. Theory of Computing Systems, Vol. 38, No. 2
- Sam Tannous (2007). Avoiding Rotated Bitboards with Direct Lookup. ICGA Journal, Vol. 30, No. 2, pdf » Hashing Dictionaries
- Kumar Chellapilla, Anton Mityagin, Denis Xavier Charles (2007). GigaHash: scalable minimal perfect hashing for billions of urls. WWW 2007
- Trevor Fenner, Mark Levene (2008). Move Generation with Perfect Hashing Functions. ICGA Journal, Vol. 31, No. 1, pdf » Congruent Modulo Bitboards
2010 ...
- Maurizio Monge (2010). On perfect hashing of numbers with sparse digit representation via multiplication by a constant. arXiv:1003.3196 » Magic Bitboards
- Jiao Wang, Si-Zhong Li, Xin-He Xu (2010). A Minors Hash Table in Chinese-Chess Programs. ICGA Journal, Vol. 33, No. 1
- Mihai Pătrașcu, Mikkel Thorup (2011). The Power of Simple Tabulation Hashing. arXiv:1011.5200v2
- Dan Anthony Feliciano Alcantara (2011). Effcient Hash Tables on the GPU. Ph.D. thesis, University of California, Davis, pdf » GPU
- John Tromp (2014). Cuckoo Cycle: a memory-hard proof-of-work system. IACR Cryptology ePrint Archive [8] [9]
- David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, Paweł Pszona (2014). Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket. arXiv:1404.0286
- Thomas Dybdahl Ahle, Martin Aumüller, Rasmus Pagh (2016). Parameter-free Locality Sensitive Hashing for Spherical Range Reporting. arXiv:1605.02673 [10]
- Tobias Maier, Peter Sanders, Roman Dementiev (2016). Concurrent Hash Tables: Fast and General?(!). arXiv:1601.04017
- Thomas Dybdahl Ahle (2017). Optimal Set Similarity Data-structures Without False Negatives. Master thesis, University of Copenhagen, pdf [11]
- Tobias Maier, Peter Sanders (2017). Dynamic Space Efficient Hashing. arXiv:1705.00997
- Peter Sanders (2018). Hashing with Linear Probing and Referential Integrity. arXiv:1808.04602
2020 ...
- Niklas Fiekas (2020). The Hashtable Packing Problem. (Draft)
Forum Posts
1998 ...
- Fast hash algorithm by John Scalo, CCC, January 08, 1998 » Zobrist Hashing
- Fast hash key method - Revisited! by John Scalo, CCC, January 14, 1998
- Hash tables and data-cache, some programmer stuff... by Ed Schröder, CCC, January 17, 1998
2000 ...
- A fast hash -- assuming you are not planning to do incremental updates by Dann Corbit, CCC, June 15, 2001
- Non power of two hash table sizes by Alvaro Jose Povoa Cardoso, CCC, February 18, 2002
2005 ...
- Hash table and O(1) by Dann Corbit, CCC, February 06, 2006
- What is the Difference between Mainhash, Evalhash, Pawnhash? by Thomas Wallendik, Hiarcs Forum, October 13, 2007
- Cache pollution when reading/writing hash table by Marco Costalba, CCC, August 09, 2009
2010 ...
- Cache-friendier material index by Harm Geert Muller, CCC, March 31, 2010
- how to measure frequency of hash collisions by Daniel Shawul, CCC, June 16, 2012 » Key Collisions, Transposition Table
- Hashing based on move lists by Matthew R. Brades, CCC, June 30, 2013
2015 ...
- Hash cache by Harm Geert Muller, CCC, October 12, 2015 » Transposition Table
- On-the fly hash key generation? by Evert Glebbeek, CCC, January 12, 2016
- Crafty's four hash tables by Louis Zulli, CCC, January 17, 2016 » Crafty
- Hashed repetition table by J. Wesley Cleveland, CCC, September 04, 2016 » Repetition Hash Table
- Hashing a quadboard from scratch by Edoardo Manino, CCC, November 23, 2016 » Quad-Bitboards
- Magic end-game material hash? by Harm Geert Muller, CCC, November 30, 2017
- hashing in chess4j by James Swafford, CCC, December 30, 2017 » chess4j, Transposition Table
2020 ...
- hash collisions by Jon Dart, CCC, January 28, 2020 » Key Collisions
- Dense board representation as hash code by koedem, CCC, February 01, 2020
- Hashtable packing (e.g. to optimize magic bitboards) is strongly NP-complete by Niklas Fiekas, CCC, February 13, 2020 » Magic Bitboards [12]
- Zobrist key independence by Harm Geert Muller, CCC, February 17, 2020 » Zobrist Hashing
External Links
- Hash Table from Wikipedia
- Hash function from Wikipedia
- Perfect hash function from Wikipedia
- Cryptographic hash function from Wikipedia
- gperf - GNU Project - Free Software Foundation
- Transposition table from Wikipedia
- Tabulation hashing from Wikipedia
- Zobrist hashing from Wikipedia
- Cuckoo hashing from Wikipedia
- Distributed hash table from Wikipedia
- Koorde based on Chord and De Bruijn Sequence
- Transposition-driven scheduling - Wikipedia
- Hashlife from Wikipedia by Bill Gosper [13]
- Integer Hash Function by Thomas Wang
- Hash functions by Paul Hsieh
- Hash Functions and Block Ciphers by Bob Jenkins
- A Hash Function for Hash Table Lookup by Bob Jenkins
- Perfect Hashing by Bob Jenkins
- Jenkins hash function from Wikipedia
- Fowler–Noll–Vo hash function from Wikipedia
- General Purpose Hash Function Algorithms by Arash Partow
- Hash Functions
- 7. Wahl einer geeigneten Hash-Funktion from Guugelhupf - Design und Implementation (German)
- Association P.C. - Soft Time in a Life Machine, Berliner Jazztage, November 7, 1971, NDR-RB-SFB 3 Broadcast, YouTube Video
References
- ↑ Hash function from Wikipedia
- ↑ Hash function from Wikipedia
- ↑ Cache-friendier material index by Harm Geert Muller, CCC, March 31, 2010
- ↑ Hash function from Wikipedia
- ↑ Bloom filter from Wikipedia
- ↑ Merkle–Damgård construction from Wikipedia
- ↑ A Hash Function for Hash Table Lookup by Bob Jenkins, updated Dr. Dobb's article
- ↑ Cuckoo Cycle: a new memory-hard proof-of-work system by John Tromp, Bitcoin Forum, January 08, 2014
- ↑ Cuckoo hashing from Wikipedia
- ↑ Locality-sensitive hashing from Wikipedia
- ↑ MinHash from Wikipedia
- ↑ Strong NP-completeness from Wikipedia
- ↑ Gosper's Algorithm (Hashlife) explained