chromium / external / github.com / google / farmhash / 2bc1fd0d958f6b6b2131ac70484aa81bfaf9b29a / . / Understanding_Hash_Functions

UNDERSTANDING HASH FUNCTIONS | |

by Geoff Pike | |

Version 0.2 --- early draft --- comments and questions welcome! | |

References appear in square brackets. | |

1 INTRODUCTION | |

Hashing has proven tremendously useful in constructing various fast | |

data structures and algorithms. It is typically possible to simplify | |

the analysis of hash-based algorithms if one assumes that the relevant | |

hash functions are high quality. At the other extreme, if the | |

relevant hash functions were always to return the same value, many | |

hash-based algorithms become algorithms that are slower, simpler, but still well-known. | |

For example, a chaining hash table devolves into a linked list. | |

There are many possible definitions of hash function quality. For | |

example, one might want a list of keys and their hashes to provide no | |

pattern that would allow an opponent to predict anything about the | |

hashes of other keys. Although I cannot prove it, I think I can meet | |

this and many other definitions of quality with | |

f(s) = SHA-3(concatenation of z and s), | |

where z is some secret string known only to me. This well-known trick | |

provides, I think, more high-quality hash functions than anyone will | |

need, though greater computational power in the future may push us to | |

replace SHA-3 from time to time. | |

In short, discussions about choosing a hash function are almost always | |

discussions about speed, energy consumption, or similar. Concerns | |

about hash quality are easy to fix, for a price. | |

2 ANATOMY OF A HASH FUNCTION | |

Hash functions that input strings of arbitrary length are written in | |

terms of an internal state, S. In many cases the internal state is a | |

fixed number of bits and will fit in machine registers. One generic | |

sketch of a string hash is: | |

let S = some initial value | |

let c = the length of S in bits | |

while (input is not exhausted) { | |

let t = the next c bits of input (padded with zeroes if less than c remain) | |

S = M(S xor t) | |

} | |

let n = the number of bytes hashed | |

return F(S, n) | |

where M is a hash function that inputs and outputs c bits, and F is a | |

hash function that inputs c bits (plus, say, 64 for its second argument) | |

and outputs however many bits one needs to return. In some sense we have | |

reduced the string-hashing problem to two integer hashing problems. | |

2.1 INTEGER HASHING TECHNIQUES | |

A hash function that inputs and outputs the same number of bits, say, | |

32, can use reversible bit-twiddling operations, each of which is | |

"onto" in the mathematical sense. For example, multiplication by an | |

odd constant is reversible, as all odd numbers are relatively prime to | |

2^32. Other commonly used reversible operations include: | |

o Adding or xoring a constant | |

o Bitwise rotation or other bitwise permutations | |

o bit j = (bit j) xor (bit k) for unequal constants j and k | |

o "Shift mix": S = S xor (S >> k), where k is, say, 17 | |

o Replacing a fixed-length bit string with its cyclic redundancy | |

checksum, perhaps via _mm_crc32_u32(f, <some constant>) [Pike] | |

Each of the above is a "bad" hash function that inputs and outputs | |

the same number of bits. One can simply compose two or more of those | |

bad hash functions to construct a higher-quality hash function. | |

One common quality goal for integer hashing (and string hashing) is | |

that flipping the 19th bit, or any other small change, applied to | |

multiple input keys, causes a seemingly unpredictable difference each | |

time. Similarly, any change to an input should lead to a seemingly | |

unpredictable selection of the output bits to flip. | |

Therefore, if we want a high-quality hash function that inputs c bits | |

and outputs fewer than c bits, we can simply truncate the output of a | |

high-quality hash function that inputs and outputs c bits. | |

To give a concrete example, here is Bob Jenkins' mix(), published in | |

1996 [Jenkins]. Its input is 96 bits in three 32-bit variables, and its output | |

is 96 bits. However, one may use a subset of the output bits, as every | |

output bit is affected by every non-empty subset of the input bits. | |

Input: a, b, and c | |

Algorithm: | |

a -= b; a -= c; a ^= (c>>13); | |

b -= c; b -= a; b ^= (a<<8); | |

c -= a; c -= b; c ^= (b>>13); | |

a -= b; a -= c; a ^= (c>>12); | |

b -= c; b -= a; b ^= (a<<16); | |

c -= a; c -= b; c ^= (b>>5); | |

a -= b; a -= c; a ^= (c>>3); | |

b -= c; b -= a; b ^= (a<<10); | |

c -= a; c -= b; c ^= (b>>15); | |

Output: a, b, and c | |

2.2 VARIATIONS ON STRING HASHING | |

There are three variations on our initial sketch worth noting. | |

First, for speed, one can special-case short inputs, as the CityHash | |

and FarmHash algorithms do. The number of special cases can be | |

reduced by using loads that may overlap: for example, a hash of a 9- | |

to 16-byte string can be implemented by a hash that inputs two 8-byte | |

values (the first 8 and last 8 bytes of the input string) and the string | |

length [CityHash, FarmHash]. | |

Second, one may choose different means of incorporating input bits | |

into the internal state. One example: the mixing of S and input bits | |

may be interleaved with the mixing of parts of S and other parts of S. | |

Another example: the input bits processed in a loop iteration might be | |

xor'ed into multiple places in S, rather than just one, or might be | |

hashed with each other before touching S [Murmur]. The advantages and | |

disadvantages of these are unclear. | |

Third, one may repeatedly "squeeze information" from S, by remixing it with | |

itself and then revealing a subset of S. This is convenient when one would | |

like a family of hash functions with different output lengths. A special | |

case of the idea, called the "sponge construction," has been well studied and | |

adopted by the authors of Keccak and others [SHA-3]. | |

3 HASH FUNCTIONS FOR HASH TABLES | |

It isn't hard to find real-life examples where hash tables or the hash | |

functions for them take more than 5% of a program's CPU time. | |

Improvements to hash tables and their hash functions are therefore a | |

classic example of software performance tuning. Unfortunately, the | |

best choice may be platform-dependent, so to avoid writing your own | |

collection of #ifdefs, please consider selecting something like the | |

FarmHash family of hash functions, that supply decent | |

platform-dependent logic for you. | |

To tune a program, often one will replace an existing hash function with a | |

faster, lower-quality hash function, despite the increased chance of unlucky | |

or pathological performance problems. Clever algorithms can mitigate this | |

risk. For example, hash tables can start with one hash function and then | |

switch to another if things seem to be going poorly. Therefore, one should | |

rarely plan to spend much CPU time on a secure hash function (such as SHA-3) | |

or a near-universal hash function (such as VHASH) when seeking the best | |

possible performance from a hash table. Against that, those types of hash | |

functions can limit the risk of pathological performance problems when one is | |

designing around typical hash-based algorithms that stick with a single hash | |

function no matter how it behaves on the data at hand. | |

4 | |

REFERENCES | |

[Murmur] Appleby, Austin. https://code.google.com/p/smhasher, | |

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

[SMHasher] Appleby, Austin. https://code.google.com/p/smhasher | |

[SHA-3] Bertoni, Guido, et al. http://keccak.noekeon.org/ | |

[Jenkins] Jenkins, Bob. http://burtleburtle.net/bob/hash/doobs.html | |

[VHASH] Krovetz, Ted. Message authentication on 64-bit architectures. In | |

Selected Areas of Cryptography – SAC 2006. Springer-Verlag, 2006. | |

[CityHash] Pike, Geoff and Alakuijala, Jyrki. https://code.google.com/p/cityhash | |

[FarmHash] Pike, Geoff. https://code.google.com/p/farmhash | |

[Pike] Pike, Geoff. http://www.stanford.edu/class/ee380/Abstracts/121017-slides.pdf |