Hash 函数

1. hash

https://stackoverflow.com/questions/44695684/structured-bindings-when-something-looks-like-a-reference-and-behaves-similarly

https://stackoverflow.com/questions/9729390/how-to-use-unordered-set-with-custom-types

https://stackoverflow.com/questions/4948780/magic-number-in-boosthash-combine

http://www.burtleburtle.net/bob/hash/doobs.html

http://blog.reverberate.org/2012/01/state-of-hash-functions-2012.html

https://www.oschina.net/translate/state-of-hash-functions

https://en.wikipedia.org/wiki/Jenkins_hash_function

https://sites.google.com/site/murmurhash/

https://github.com/google/cityhash

http://burtleburtle.net/bob/hash/spooky.html

2. Boost helper function

This can be difficult; the XOR/bit-shifting method above is probably not a bad start. For a slightly better start, you may use the hash_value and hash_combine function template from the Boost library. The former acts in a similar way as std::hash for standard types (recently also including tuples and other useful standard types); the latter helps you combine individual hash values into one. Here is a rewrite of the hash function that uses the Boost helper functions:

#include <boost/functional/hash.hpp>
​
struct KeyHasher
{
std::size_t operator()(const Key& k) const
{
 using boost::hash_value;
 using boost::hash_combine;
​
 // Start with a hash value of 0    .
 std::size_t seed = 0;
​
 // Modify 'seed' by XORing and bit-shifting in
 // one member of 'Key' after the other:
 hash_combine(seed,hash_value(k.first));
 hash_combine(seed,hash_value(k.second));
 hash_combine(seed,hash_value(k.third));
​
 // Return the result.
 return seed;
}
};

And here’s a rewrite that doesn’t use boost, yet uses good method of combining the hashes:

namespace std
{
 template <>
 struct hash<Key>
 {
 size_t operator()( const Key& k ) const
 {
 // Compute individual hash values for first, second and third
 // http://stackoverflow.com/a/1646913/126995
 size_t res = 17;
 res = res * 31 + hash<string>()( k.first );
 res = res * 31 + hash<string>()( k.second );
 res = res * 31 + hash<int>()( k.third );
 return res;
 }
 };
}

The standard library contains specialisations of std::hash<T> for the fundamental types, for pointers and for std::string (or rather, for all specializations of std::basic_string).

Unfortunately the library does not contain the following vital new-from-old combination function, which is however part of Boost, and which you should copy into your code:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
 std::hash<T> hasher;
 seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

With this function, you can hash pairs, tuples, arrays, and any sort of range of elements that are themselves hashable. Browse the Boost sources for many examples and useful implementations. And obviously you can use this function to create a hash function for your own types. For example, here's hashing a pair:

template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
 inline std::size_t operator()(const std::pair<S, T> & v) const
 {
 std::size_t seed = 0;
 hash_combine(seed, v.first);
 hash_combine(seed, v.second);
 return seed;
 }
};

Please be aware, though, that hash-combining does not produce good hash values. The results have very poor statistic qualities (e.g. it is very easy to create hash collisions). Good hashing needs to be able to see all the raw input bits, and cannot be factored through partial hashes. (That's why there isn't a better solution in the current standard library; nobody has been able to come up with a satisfactory design.)

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart. Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, differences will soon be spread across all the bits.

3. Bob Jenkins' Functions

3.1. one_at_a_time

Jenkins's one_at_a_time hash is adapted here from a WWW page by Bob Jenkins,[1] which is an expanded version of his Dr. Dobb's article.[2] It was originally created to fulfill certain requirements described by Colin Plumb, a cryptographer, but was ultimately not put to use.[3]

 uint32_t jenkins_one_at_a_time_hash(const uint8_t* key, size_t length) {
 size_t i = 0;
 uint32_t hash = 0;
 while (i != length) {
 hash += key[i++];
 hash += hash << 10;
 hash ^= hash >> 6;
 }
 hash += hash << 3;
 hash ^= hash >> 11;
 hash += hash << 15;
 return hash;
}

Sample hash values for one_at_a_time hash function.

one_at_a_time("a", 1)
0xca2e9442
one_at_a_time("The quick brown fox jumps over the lazy dog", 43)
0x519e91f5

image

Avalanche behavior of Jenkins One-at-a-time hash over 3-byte keys

The avalanche behavior of this hash is shown on the right.

Each of the 24 rows corresponds to a single bit in the 3-byte input key, and each of the 32 columns corresponds to a bit in the output hash. Colors are chosen by how well the input key bit affects the given output hash bit: a green square indicates good mixing behavior, a yellow square weak mixing behavior, and red would indicate no mixing. Only a few bits in the last byte of the input key are weakly mixed to a minority of bits in the output hash.

The standard implementation of the Perl programming language includes Jenkins's one-at-a-time hash or a hardened variant of it, along with SipHash, and uses Jenkins's one-at-a-time hash by default.[4][5]

3.2. lookup2

The lookup2 function was an interim successor to one-at-a-time. It is the function referred to as "My Hash" in the 1997 Dr. Dobbs journal article, though it has been obsoleted by subsequent functions that Jenkins has released. Applications of this hash function are found in:

• the SPIN model checker, for probabilistic error detection. In a paper about this program, researchers Dillinger and Manolios note that lookup2 is "a popular choice among implementers of hash tables and Bloom filters". They study lookup2 and a simple extension of it that produces 96-bit rather than 32-bit hash values.[6]

• The Netfilter firewall component of Linux,[7] where it replaced an earlier hash function that was too sensitive to collisions. The resulting system, however, was shown to still be sensitive to hash flooding attacks, even when the Jenkins hash is randomized using a secret key.[8]

• The program that solved the game of kalah used the Jenkins hash function, instead of the Zobrist hashing technique more commonly used for this type of problem; the reasons for this choice were the speed of Jenkins' function on the small representations of kalah boards, as well as the fact that the basic rule of kalah can radically alter the board, negating the benefit of Zobrist's incremental computation of hash functions.[9]

3.3. lookup3

The lookup3 function consumes input in 12 byte (96 bit) chunks.[10] It may be appropriate when speed is more important than simplicity. Note, though, that any speed improvement from the use of this hash is only likely to be useful for large keys, and that the increased complexity may also have speed consequences such as preventing an optimizing compiler from inlining the hash function.

3.4. SpookyHash

In 2011 Jenkins released a new 128-bit hash function called SpookyHash.[11] SpookyHash is significantly faster than lookup3.

Example for V2 (little-endian x64):

The short method for less than 192 bytes (43 bytes):

 Hash128("The quick brown fox jumps over the lazy dog")
 2b12e846aa0693c71d367e742407341b

The standard method for more than 191 bytes (219 bytes):

 Hash128("The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog The quick brown fox jumps over the lazy dog")
 f1b71c6ac5af39e7b69363a60dd29c49

4. MurmurHash

5. CityHash 和 SpookyHash