Jenkins hash function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Jenkins hash functions are a collection of (non-cryptographic) hash functions for multi-byte keys designed by Bob Jenkins. They can be used also as checksums to detect accidental data corruption or detect identical records in a database. The first one was formally published in 1997.

The hash functions[edit]

one-at-a-time[edit]

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. Dobbs article.[2]

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}
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 and SipHash, and uses Jenkins's one-at-a-time hash by default.[3][4][5]

lookup2[edit]

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.

lookup3[edit]

The lookup3 function consumes input in 12 byte (96 bit) chunks.[6] 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.

SpookyHash[edit]

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

See also[edit]

References[edit]

  1. ^ Jenkins, Bob (ca. 2006). "A hash function for hash Table lookup". Retrieved April 16, 2009. 
  2. ^ Jenkins, Bob (September 1997). "Hash functions". Dr. Dobbs Journal. 
  3. ^ "What hashing function/algorithm does Perl use ?"
  4. ^ "RFC: perlfeaturedelta": "one-at-a-time hash algorithm ... [was added in version] 5.8.0"
  5. ^ "perl: hv_func.h"
  6. ^ Jenkins, Bob. "lookup3.c source code". Retrieved April 16, 2009. 
  7. ^ Jenkins, Bob. "SpookyHash: a 128-bit noncryptographic hash". Retrieved Jan 29, 2012.