Fowler–Noll–Vo hash function
In computer science, FNV is an algorithm for the generation of cluster values over data fields: a so-called hash function. Last name giver of the FNV are abbreviation Glenn Fowler, Landon Curt Noll, and Phong Vo, who developed the algorithm together. FNV meets all the criteria of a good hashing function and finds wide use everywhere where large amounts of data are processed, as well as speed and reliability are required, such as in DN- systems, databases and e- mail servers. FNV but not suitable for cryptographic use.
Hash functions
A hash function reads a data field, such as a string or a file and offset byte for byte the field so that a unique key value is generated as possible to the data field - a kind of numerical compression of the field. The "magic trick" is the use of prime numbers.
With key values associated data or data sets can be indexed in data structures and thus find faster; see binary tree, B- tree, AVL tree, hash table. In addition, data can be verified using the scattering values integrity such as consistency; because on the same field, the same key value is always produced - as long as box and algorithm remain exactly the same; see Cyclic Redundancy Check.
FNV implementation, 64 - bit key
Typedef unsigned long long uint64; typedef unsigned char uchar; uint64 fnFNV (const void * pBuffer, size_t nByteLen ) { uint64 nHashVal = 0xcbf29ce484222325ULL, nMagicPrime = 0x00000100000001b3ULL; const uchar * pFirst = ( uchar *) pBuffer, * pLast = pFirst nByteLen; while ( pFirst < pLast ) { nHashVal ^ = * pFirst ; / / Bitwise XOR: nHashVal = nHashVal ^ * pFirst nHashVal * = nMagicPrime; } return nHashVal; } Shown here is the recommended version of FNV -1a of the algorithm in the C programming language in the original version of FNV -1 operations XOR and multiplication inside the loop are only reversed.
Implementation
For each key width exists an associated prime grade alone. If a narrower or wider key value required, the prime value must be adjusted in order to continue to achieve good Streuwertbitverteilung.
Weblink
- Landon Curt Noll FNV