This hash function is described here. It is a simple multiplicative hash with the addition of a post-processing step called xor-folding to remove some linearity in the lower bits. The FNV authors recommend using xor-folding if the desired hash size is not a power of 2, but they actually mean to use xor-folding when the hash size is not a power of 2 or is less than 32.
There are different initialization and multiplication constants for use with 32-bit, 64-bit, 128-bit hashes, etc., but we'll only examine the 32-bit version of FNV here. In our uniform distribution test we'll use xor-folding for the lower bits since that is the intended use of this hash, but we'll examine the upper bits as-is. Since our avalanche test is a full 32-bit test, we can't use xor-folding there. This will allow us to identify classes of keys for which using xor-folding is a necessity.
The primary appeals of this hash are its simplicity and its speed, but its speed is dependent on whether or not the CPU architecture supports fast integer multiplication. The Jenkins shift-add-xor hashes are faster on CPU architectures without fast multiplication.
Figure 1 shows the listing for the FNV 32-bit hash.
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 FNV hash. This test indicates that the FNV 32-bit hash with xor-folding produces uniformly distributed values for hash tables that are a power of two, up to at least 214, when the key octets are uniformly distributed, distributed similar to alphabetic text, or sparsely distributed.
The upper bits are not uniformly distributed if you use more than 14 or 15 bits. Because of this, I don't recommend using this hash with hash tables larger than 214 buckets. The results are acceptible up to 216 bits for text keys, so you may be able to use it for that purpose if you carefully test the performance in your particular application.
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 FNV hash. This test indicates that the FNV hash has poor avalanche behavior, as do all simple multiplicative hashes. This means that there will be some classes of keys for which the hash function does not produce uniform output, even for small bucket counts where the χ2 tests succeeded above.
Of particular concern are the two low-order bits. These are always just a simple linear function of the two low-order bits of the keys octets. For example, in the full 32-bit hash value, the low-order bit will always just be a simple XOR of the LSBs of the key octets and the LSB from the intialization constant. Also of concern is that fact that the upper bits of the key octets do not have any influence on the low-order bits of the hash output (without xor-folding). The MSB of each key octet does not diffuse at all into the entire lower 8 bits of the hash value. This indicates that you must follow the xor-folding recommendations for all classes of keys.
Also, the mixing step of this hash is never applied to the last octet of the key. This shows clearly in the avalanche results. The authors offer an alternative form of the hash where the combining step is done before the mixing step, and I recommend that you adopt this alternative if you use FNV. There is no reason to do otherwise, and I'm surprised that the authors do not recommend this by default.
I don't recommend using 32-bit FNV as a general-purpose hash. It can produce uniform output, but its suitability needs to be tested for each class of keys for which you intend to use it. It is likely to produce non-uniform output if you have more than 214 or 215 hash buckets. If the CPU architecture does not have fast integer multiplication, use a shift-add-xor hash instead.
If you want to use an FNV-style hash function, I recommend using the modified version listed in Figure 4. This version passes all the uniform distribution tests above and it achieves avalanche for every tested combination of input and output bits (green squares everywhere). No xor-folding step is required.
The only difference between this version and the original version is that the mixing steps occurs after the combining step in each round, and it adds a post-processing step to mix the bits even further. These two changes completely correct the avalanche behavior of the function. As a result, this version of FNV passes all of the χ2 tests above, all the way up to 216 buckets. I haven't tested larger sizes but I suspect it would be OK there as well.