FNV (Informatik) – Wikipedia

In der Informatik ist Fowler-Noll-Vo (kurz: FNV) ein Algorithmus zur Generierung von Streuwerten über Datenfelder: eine sogenannte Hash-Funktion. Nachnamensgeber des Kürzels FNV sind Glenn Fowler, Landon Curt Noll und Phong Vo, die den Algorithmus zusammen 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.

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 oder 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).

In C bzw. C++ kann die empfohlene^[1] Version FNV-1a des Algorithmus folgendermaßen aussehen:

 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 der Originalversion FNV-1 sind lediglich die Operationen XOR und Multiplikation innerhalb der Schleife vertauscht.

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.

• FNV bei Landon Curt Noll

1. ↑ FNV bei Landon Curt Noll Notiz am Ende des Abschnittes