File RandomHashing.h

↰ Parent directory (ADS/dictionary)

Hashing with random tables, beyond the book:

Definition (ADS/dictionary/RandomHashing.h)

Detailed Description

  • splitmix64(), the finalizer of the generator SplitMix64 of Steele, Lea and Flood, a bijection of the 64-bit words that mixes every input bit into every output bit, and SplitMix64, the generator itself, which meets UniformRandomBitGenerator and seeds the tables below;

  • fibonacciPlace(), the top b bits of :math:` h lfloor 2^{64} / phi rfloor , the multiplicative hashing of Knuth with the golden ratio, which spreads over a table of :math: 2^b ` places also the hashes whose low bits are regular;

  • ZobristTable, a random word R[ f ][ v ] for each feature f and value v, the hash of a state being the XOR of the words of its pairs: a move that changes the value of a feature updates the hash in O( 1 ) by two XOR, which makes it the hash of the board games and of the states of a search;

  • TabulationHash, the simple tabulation of Carter and Wegman: a key of 64 bits is cut into 8 bytes and the hash is the XOR of a random word of a table per byte; it is 3-independent, and Patrascu and Thorup showed that it gives linear probing, cuckoo hashing and the minwise estimates the bounds of fully random hashing.

The contracts [see File Contract.h]: 1 <= b <= 64 for fibonacciPlace(), at least a feature and a value for ZobristTable, and the features and the values within it. The functions are defined in RandomHashing.tpp.

    1. Steele, D. Lea, C. H. Flood, Fast splittable pseudorandom number generators, Proceedings of OOPSLA 2014, 453-472, 2014, doi:10.1145/2660193.2660195

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 6.4 (the multiplicative hashing)

    1. Zobrist, A new hashing method with application for game playing, Technical Report 88, University of Wisconsin, 1970

    1. Carter, M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18(2), 143-154, 1979, doi:10.1016/0022-0000(79)90044-8

  1. Patrascu, M. Thorup, The power of simple tabulation hashing, Journal of the ACM 59(3), article 14, 2012, doi:10.1145/2220357.2220361

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/dictionary/impl/RandomHashing.tpp

  • array

  • cstddef

  • cstdint

  • limits

  • vector

Included By

Namespaces

Classes

Functions