FNV (Informatik)


FNV (Informatik)

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

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.

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

 typedef unsigned long long  uint64; // etwaig __int64 == long long
 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++,
     nHashVal *= nMagicPrime;
 
   return nHashVal;
 }

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.

Weblink


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • FNV — Die Abkürzung FNV wird in folgenden Zusammenhängen verwendet: Federatie Nederlandse Vakbeweging (niederländischer Gewerkschaftsbund) In der Informatik: ein Algorithmus zur Generierung von Streuwerten über Datenfelder steht in der Neurologie für… …   Deutsch Wikipedia

  • Hasch-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hasch-Verfahren — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Algorithmus — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Funktion — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hash-Wert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashcode — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashen — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashing — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia

  • Hashwert — Eine Hashfunktion oder Streuwertfunktion ist eine Funktion bzw. Abbildung, die zu einer Eingabe aus einer üblicherweise großen Quellmenge eine Ausgabe, den Hashcode, erzeugt, meist aus einer kleineren Zielmenge. Die Hashwerte beziehungsweise… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.