FNV (Computer Science)

from Wikipedia, the free encyclopedia

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

  1. ^ FNV from Landon Curt Noll note at the end of the section