20. Sep 2008, 12:02

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 in Kooperation 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.

Inhaltsverzeichnis 1 Hash-Funktionen 2 FNV-Implementation, 64-bit-Schlüssel, C/Cpp 3 Implementation 4 Weblink

[Bearbeiten] Hash-Funktionen

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/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.

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

 typedef unsigned long long  uint64; // etwaig __int64 == long long
 typedef unsigned char       uchar;
 
 uint64 fnFNV( void* pBuffer, size_t nByteLen )
 {
   uint64 nHashVal    = 0xcbf29ce484222325ULL,
          nMagicPrime = 0x00000100000001b3ULL;
 
   uchar* pFirst = ( uchar* )( pBuffer ),
        * pLast  = pFirst + nByteLen;
 
   while( pFirst < pLast )
     nHashVal ^= *pFirst++,
     nHashVal *= nMagicPrime;
 
   return nHashVal;
 }

[Bearbeiten] Implementation

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.

[Bearbeiten] Weblink

http://www.isthe.com/chongo/tech/comp/fnv/

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon