FNV (Informatik)

In der Informatik ist FNV ein Algorithmus zur Generierung von Streuwerten über Datenfelder: eine sog. Hash-Funktion. Nachnamensgeber des Kürzels FNV sind Glenn Fowler, Curt Landon Noll und Phong Vo, die den Algorithmus in Kooperation entwickelten. FNV erfüllt alle Kriterien einer guten Hashing-Funktion und findet überall breiten Einsatz dort, wo große Datenmengen verarbeitet werden sowie Schnelligkeit und Zuverlässigkeit gefordert sind, z. B. in DN-Systemen, Datenbanken und E-Mail-Servern. FNV eignet sich jedoch nicht für kryptographischen Einsatz.

Hash-Funktionen

Eine Hash-Funktion liest ein Datenfeld ein, z. B. eine Zeichenkette oder eine Datei, und verrechnet das Feld Byte für Byte so, dass ein möglichst eindeutiger Schlüsselwert zum Datenfeld erzeugt wird – eine Art zahlenmäßige Stauchung des Feldes. Der magische Trick ist die Verwendung von Primzahlen.

Mit Schlüsselwerten assoziierte Daten/Datenmengen lassen sich in Datenstrukturen indizieren und somit schneller auffinden; siehe Binärbaum, B-Baum, AVL-Baum, Hash-Tabelle. Zudem können Daten mithilfe der Streuwerte auf Unversehrtheit wie Konsistenz überprüft werden; denn über dasselbe Feld wird stets derselbe Schlüsselwert erzeugt – solange Feld und Algorithmus exakt gleich bleiben; siehe Zyklische Redundanzprüfung.

FNV-Implementation, 64-bit-Schlüssel, C/Cpp

 typedef unsigned long long  uint64; // etwaig __int64 == long long
 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++,
     nHashVal *= nMagicPrime;
 
   return nHashVal;
 }

Implementation

Für jede Schlüsselbreite existiert eine zugehörige alleintaugliche Primzahl. Wird ein schmalerer oder breiterer Schlüsselwert benötigt, muss der Primzahlwert angepasst werden, um weiterhin eine gute Streuwertbitverteilung zu erzielen.

Weblink

• [1]