Bob Jenkins' Hash
This hash function is described here. It uses shifts, adds, and xors in its mixing function, and processes keys twelve octets at a time. The implementation in C++ is more elegant as C++ allow case statements to fall through, but C# does not.
Achieving avalanche seemed to be an important design goal for the hash author, and our results below confirm that this hash has excellent avalanche behavior. Another design goal was achieving processor parallelism in the mixing function. Control over low-level processor timing details is probably lost in a memory-managed and JIT-compiled language like C#, nevertheless this hash does its job well.
Figure 1 shows the listing for the Bob Jenkins hash. Since it processes the key twelve octets at a time, the post-processing step is slightly more complex than some other hash functions since it has to handle the partial final block. The post-processing step is also interesting in that it mixes the key length into the hash value. This is common practice for cryptographic hashes such as MD5 and SHA-1, but not common for hashes used for table lookup and other non-cryptographic uses.
Bob Jenkins has another shift-add-xor hash that processes keys one octet at a time and has a much simpler implementation. We'll look at that hash on a subsequent page.
Uniform Distribution Test
The details of this test are described fully on a previous page. We examine the distribution of numbers derived from lower and upper bits of the hash output in sizes of 1 through 16 bits.
Figure 2 shows the results of this test for the Bob Jenkins hash. This test indicates that this hash produces uniformly distributed values for hash tables that are a power of two, up to at least 216, when the key octets are uniformly distributed, distributed similar to alphabetic text, or sparsely distributed.
The results show a couple of values in the 5% significance range, but these are due to chance and do not appear to indicate any weakness in the hash distribution.
Avalanche Test
Figure 3
Avalanche behavior of the Bob Jenkins hash.
For two-octet keys:
For four-octet keys:
For 256-octet keys:
The details of this test are described fully on a previous page. We examine the diffusion of input bits into different bit positions in the output.
Figure 3 shows the results of this test for the Bob Jenkins hash. This test indicates that this hash has excellent avalanche behavior. It is unlikely that there are any specific classes of keys that will cause problems with this function, as key bits from every position appear to be dispersed well into all hash bit positions, even for very short hash keys.
One fact not shown here is the avalanche behavior for the full 96 bits of the mixing function. In the mixing function, the MSB of variable b is not distributed at all into the lower 12 bits of either the a or b variables until the next mixing step. There is also incomplete avalanche of other bits into the bits of a and b. That shouldn't be a concern, however, because these variables are only used as intermediate values in the hash calculation and only variable c is used as the final result. All bits of a and b do mix into all bit positions in c.
Conclusion
This hash function by Bob Jenkins should be suitable for general purpose use, either for hash table lookup, basic file fingerprinting, or other non-cryptographic uses. Both the upper and lower bits are uniformly distributed. The hash function achieves avalanche for every bit combination tested.
