Wikipedia · einfach zusammengefasst · Stand
FNV (Informatik)
In der Informatik ist Fowler-Noll-Vo (kurz: FNV) ein Algorithmus zur Generierung von Streuwerten über Datenfelder: eine sogenannte Hash-Funktion.
Inhalt4 Abschnitte
Was FNV ist und wofür es verwendet wird
Fowler-Noll-Vo (FNV) ist eine Hash-Funktion, also ein Algorithmus, der aus einem Datenfeld einen Streuwert beziehungsweise Schlüsselwert erzeugt. Der Name geht auf die Entwickler Glenn Fowler, Landon Curt Noll und Phong Vo zurück.
FNV ist auf Schnelligkeit, Zuverlässigkeit und die Verarbeitung großer Datenmengen ausgerichtet. Der Algorithmus wird beispielsweise in DN-Systemen, Datenbanken und E-Mail-Servern eingesetzt. Für kryptographische Anwendungen eignet er sich jedoch nicht.
Funktionsweise und Nutzen von Hash-Funktionen
Eine Hash-Funktion liest ein Datenfeld, etwa eine Zeichenkette oder eine Datei, Byte für Byte ein. Daraus berechnet sie einen möglichst eindeutigen Schlüsselwert. Das Datenfeld wird damit gewissermaßen auf einen Zahlenwert verdichtet. Bei der Berechnung spielen Primzahlen eine wichtige Rolle.
Mit Schlüsselwerten verknüpfte Daten lassen sich in Datenstrukturen wie Binärbäumen, B-Bäumen, AVL-Bäumen oder Hash-Tabellen indizieren und dadurch schneller finden. Streuwerte können außerdem zur Prüfung der Unversehrtheit und Konsistenz von Daten dienen: Für dasselbe Datenfeld entsteht immer derselbe Schlüsselwert, solange sowohl das Feld als auch der verwendete Algorithmus exakt gleich bleiben.
Berechnung mit FNV-1a
Bei der empfohlenen Variante FNV-1a mit einem 64-Bit-Schlüssel beginnt die Berechnung mit dem Anfangswert 0xcbf29ce484222325. Als Primzahl wird 0x00000100000001b3 verwendet.
Für jedes Byte des Datenfeldes wird zuerst der bisherige Hashwert durch ein bitweises XOR mit dem aktuellen Byte verknüpft. Anschließend wird das Ergebnis mit der Primzahl multipliziert. Die zentrale Berechnung lautet: Hash = (Hash ^ *pBuffer) * MagicPrime.
Die ursprüngliche Variante FNV-1 verwendet dieselben beiden Operationen, vertauscht aber ihre Reihenfolge: Dort erfolgt die Multiplikation vor dem XOR.
Anpassung an die Schlüsselbreite
Für jede Schlüsselbreite gibt es eine eigene geeignete Primzahl. Soll ein schmalerer oder breiterer Schlüsselwert erzeugt werden, muss daher auch der Primzahlwert angepasst werden. Nur so bleibt eine gute Verteilung der Streuwertbits erhalten.