FNV
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 breiten Einsatz überall, wo große Datenmengen verarbeitet werden, sowie Schnelligkeit und Zuverlässigkeit gefordert sind, z.B. in DN-Systemen, Datenbanken und eMail-Servern.
Hash-Funktionen kurz erläutert
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.
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 )
{
const uint64 nHashVal = 0x84222325cbf29ce4ULL,
nMagicPrime = 0x00000100000001b3ULL;
uchar* pFirst = ( uchar* )( pBuffer ),
* pLast = pFirst + nByteLen;
while( pFirst < pLast )
nHashVal ^= *pFirst++,
nHashVal *= nMagicPrime;
return nHashVal;
}