File HashFunctions.h

↰ Parent directory (ADS/dictionary)

The hash functions of section 7.1.

Definition (ADS/dictionary/HashFunctions.h)

Detailed Description

A hash function :math:` HU rightarrow { 0 , ldots , m - 1 } ` maps a key to a place of a vector of size m; it has the simple uniformity if :math:`[

Q( i ) = sum_{k : H( k ) = i} P( k ) = frac{1}{m} qquad forall i in { 0 , ldots , m - 1 }

` where P( k ) is the probability that the key k is in the dictionary. A key is read as the string bin( k ) of its bits, the bytes of a string one after the other from the first, the most significant bit of each first, and int( b ) is the integer of the bit string b. The functions are

  • the extraction, :math:` H( k ) = int( b ) ` with b a block of p bits of bin( k ) [see hash_extraction()];

  • the XOR, :math:` H( k ) = int( bigoplus_i b_i ) ` of the blocks of p bits of bin( k ), the last one padded with zeros [see hash_xor()];

  • the division, :math:` H( k ) = int( bin( k ) ) bmod m `, computed with the rule of Horner and a mod at each character so that nothing overflows [see hash_division()];

  • the multiplication, :math:` H( k ) = lfloor m ( C i - lfloor C i rfloor ) rfloor ` with :math:` i = int( bin( k ) ) ` and :math:` C = ( sqrt{5} - 1 ) / 2 , the conjugate of the golden ratio [see hash_multiplication()], and its version with integers for :math: m = 2^p : with :math: s = lfloor C 2^w rfloor ` and :math:` i s = r_1 2^w + r_0 , H( k ) is made of the p most significant bits of :math: r_0 ` [see hash_fibonacci()];

  • the middle square, the p bits in the middle of :math:` i^2 ` [see hash_midsquare()].

The contracts [see File Contract.h]: the number p of bits in its range, a key of at most 8 characters for int_bin(), and for hash_division() a size m 0 and a base > 0 such that the rule of Horner does not overflow; each result is below the size it is meant for. The functions are defined in HashFunctions.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 7.1, https://algoritmicamente.it/materiali/libro/capitoli/cap07.pdf

    1. Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2nd ed., Addison-Wesley, 1998, section 6.4

  1. Morris, Scatter storage techniques, Communications of the ACM 11(1), 38-44, 1968, doi:10.1145/362851.362882

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

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

  • ADS/dictionary/impl/HashFunctions.tpp

  • cmath

  • cstddef

  • cstdint

  • limits

  • string_view

Namespaces

Functions