File FastHash.h

↰ Parent directory (ADS/dictionary)

The engineered hash functions of Namespace ADS, beyond the book [see File HashFunctions.h for those of section 7.1 and File UniversalHashing.h for the universal classes]: hashes of 64 bits for the tables, the filters and the perfect hash functions, made of the folded product, the product of two words on 128 bits whose two halves are XORed [see foldedProduct()].

Definition (ADS/dictionary/FastHash.h)

Detailed Description

Each bit of the folded product depends on every bit of its factors that the low half of the product does not lose, and a 64-bit processor computes it by one multiplication, so that a word costs one product and a string one product per 16 bytes.

  • hashWord() is the hash of a word, its folded product with the seed XORed with a constant;

  • hashBytes() is the hash of a string of n bytes, by the length: up to 8 bytes, the string is read as one word, by two loads of 4 bytes at its ends (overlapping below 8) or by its first, middle and last byte below 4, and its hash is the folded product of that word XOR the seed and of a constant XOR n; from 9 to 16 bytes, the product of the two words that end at its ends; from 17 to 32, the XOR of the products of its first and its last 16 bytes, two products at once; from 33 to 64, four products at once, of its first and its last 32 bytes, folded by a fifth one; these are inline, with no loop. Past 64 bytes, out of line, up to 256 the blocks of 16 bytes are folded into a state, each by the product of its two words, one XORed with the state, by 6 independent states over each 96 bytes, and the last 16 bytes go through a last product with the state and n; past 256, the string is cut into stripes of 64 bytes, i.e., 8 lanes of a word, each adding the product of the two halves of its word XOR a constant, and its word to the other lane of its pair, scrambled every 16 stripes (the stripes of XXH3), which vectors of AVX2 or AVX-512 do 4 or 8 lanes at a time with the same result as the scalar operations, and the 8 lanes are folded by 4 products and a last one;

  • FastHash< T > is the hash of the integers, the enumerations, the pointers, the floating point numbers (+0 and -0 hashing the same) and the strings (std::string, std::string_view and the C strings), by hashWord() and hashBytes(); it declares is_avalanching (the convention of Boost), so that FlatHashTable [see File FlatHashTable.h] and the tables of Boost take its hash as it is; DefaultHash< K > is FastHash< K > when it is defined and std::hash< K > otherwise, the default hash of the engineered tables and filters.

Every bit of a hash depends on every bit of the key, the high half of a product carrying the bits that its low half loses, which is what a hash table needs; a single product does not give the full avalanche that the statistical batteries ask (one bit of a key flips each bit of the hash with probability near 1 / 2, not exactly 1 / 2), as for the hashes of the short strings of Abseil. The functions are not cryptographic: a string chosen to make a factor of a product 0 loses the bits of the other one, and anyone who knows the seed can make collisions; a table that faces adversarial keys must use a seed drawn at random. A word is read in the byte order of the machine, so the hashes differ between little and big endian machines.

The contracts [see File Contract.h]: a string of n bytes from a pointer that is not nil when n > 0. The functions are defined in FastHash.tpp.

  1. Thorup, High speed hashing for integers and strings, 2015, arXiv:1504.06804 (the multiply-shift hashing and its analysis)

    1. Lopez Munoz, Inside boost::unordered_flat_map, 2022 (the folded product as the mixing of a hash)

Wang Yi, wyhash, 2019, https://github.com/wangyi-fudan/wyhash (the folded product of the words of a string, the overlapping loads of its short tails)

  1. Collet, XXH3, 2019, https://github.com/Cyan4973/xxHash (the stripes of the long strings in vectors)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

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

  • ADS/dictionary/impl/FastHash.tpp

  • array

  • bit

  • concepts

  • cstddef

  • cstdint

  • cstring

  • functional

  • string (File AhoCorasick.h)

  • string_view

  • type_traits

Included By

Namespaces

Classes

Functions

Typedefs

Variables