FNV (Informatik)

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

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

Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung.
 typedef unsigned long long uint64;
 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++;   // bitweises XOR: nHashVal = nHashVal ^ *pFirst++
     nHashVal *= nMagicPrime;
   }
   return nHashVal;
 }

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