Fowler Noll Vo hash
From Wikipedia, the free encyclopedia
Fowler/Noll/Vo is a non-cryptographic hash function created by Glenn Fowler, Landon Curt Noll, and Phong Vo.
Contents |
[edit] History
The first version of FNV was FNV-0. The problem with FNV-0 was that it used an offset basis (see below) of 0, meaning that wherever an empty input or an input consisisting entirely of null bytes was encountered, the resulting hash would be 0. This, of course, meant rather a lot of collisions.
The current version is FNV-1 and FNV-1a, which supply a means of creating non-zero offset bases.
[edit] The hash
One of FNV's key advantages is that it is very simple to implement. Start with hash == offset_basis (see below). For each byte in the input, multiply hash by the FNV prime, then XOR it with the byte from the input. The alternate algorithm, FNV-1a, reverses the multiply and XOR steps.
There are several different offset bases for various bit lengths. These offset bases are computed by running FNV-0 on the string "chongo <Landon Curt Noll> /\../\", which is Noll's signature line. This is the only current practical use for the deprecated FNV-0.
FNV primes are a much more difficult problem. Noll says on his webpage that "The theory behind which primes make good FNV_prime's is beyond the scope of this web page." One notable feature of FNV primes is that when represented as hexadecimal, they are found to bear this appearance:
- The high byte is 1.
- The next-to-low byte is 1.
- The low byte is chosen so that the number is prime.
- All bytes in between are zero.
For any given size, there are a number of different low byte values which satisfy the above constraints. It is not known what criteria were used to select the particular values.
| Size in bits | FNV prime | FNV-1 offset base |
|---|---|---|
| 32 | 1<<24 + 0x193 = 16777619 |
0x811c9dc5 |
| 64 | 1<<40 + 0x1b3 = 1099511628211 |
0xcbf29ce484222325 |
| 128 | 1<<88 + 0x159 = 309485009821345068724781401 |
0xcf470aac6cb293d2f52f88bf32307f8f |
| 256 | 1<<168 + 0x163 | 0xdd268dbcaac550362d98c384c4e576cc c8b1536847b6bbb31023b4c8caee0535 |
Note that the values are in notation used by C and some other popular programming languages. So "1<<24" means 1 shifted left 24 bits, or 224. The prefix "0x" on numbers means that the subsequent numbers are in hexadecimal.
[edit] Other considerations
FNV currently comes in 32-, 64-, 128-, and 256-bit flavors. For pure FNV implementations, this is determined solely by the availability of FNV primes for the desired bit length; however, the FNV webpage discusses methods of adapting one of the above versions to a smaller length that may or not be a power of two.
