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 | Quelltext 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 | Quelltext 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 | Quelltext 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 | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

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