FNV (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Informatik ist Fowler-Noll-Vo (kurz: 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 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.

Hash-Funktionen[Bearbeiten]

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.

FNV-Implementation, 64-bit-Schlüssel[Bearbeiten]

 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;
 }

Hier dargestellt ist die empfohlene[1] Version FNV-1a des Algorithmus in der Programmiersprache C. In der Originalversion FNV-1 sind lediglich die Operationen XOR und Multiplikation innerhalb der Schleife vertauscht.

Implementation[Bearbeiten]

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[Bearbeiten]

Einzelnachweise[Bearbeiten]

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