FNV (Computer Science)
In computer science, Fowler-Noll-Vo ( FNV for short ) is an algorithm for generating scatter values using data fields: a so-called hash function . The FNV abbreviation is given by Glenn Fowler , Landon Curt Noll and Phong Vo , who developed the algorithm together. FNV fulfills all criteria of a good hashing function and is widely used wherever large amounts of data are processed and speed and reliability are required, e.g. B. in DN systems , databases and e-mail servers . However, FNV is not suitable for cryptographic use.
Hash functions
A hash function reads a data field, e.g. B. a character string or a file, and calculates the field byte by byte so that a key value that is as unique as possible is generated for the data field - a kind of numerical compression of the field. The “magic trick” is to use prime numbers.
Data or data volumes associated with key values can be indexed in data structures and thus found more quickly (see binary tree , B-tree , AVL tree , hash table ). In addition, data can be checked for integrity and consistency using the scatter values; because the same key value is always generated via the same field - as long as the field and algorithm remain exactly the same (see cyclic redundancy check ).
FNV implementation, 64-bit key
In C or C ++ , the recommended version FNV-1a of the algorithm can look like this:
uint64_t fnFNV (const uint8_t* pBuffer, const uint8_t* const pBufferEnd) { const uint64_t MagicPrime = 0x00000100000001b3; uint64_t Hash = 0xcbf29ce484222325; for ( ; pBuffer < pBufferEnd; pBuffer++) Hash = (Hash ^ *pBuffer) * MagicPrime; // bitweises XOR und dann Multiplikation return Hash; }
In the original version FNV-1, only the operations XOR and multiplication are interchanged within the loop.
Implementation
For each key width there is an associated prime number that can be used alone. If a narrower or broader key value is required, the prime number value must be adapted in order to continue to achieve a good scatter value bit distribution.
Web link
Individual evidence
- ^ FNV from Landon Curt Noll note at the end of the section