imported>Skranon: Änderungen von 84.119.16.74 (Diskussion) auf die letzte Version von Wiki-Friend12345 zurückgesetzt

2024-10-31T19:25:29Z

Änderungen von 84.119.16.74 (Diskussion) auf die letzte Version von Wiki-Friend12345 zurückgesetzt

Neue Seite

In der Informatik ist '''Fowler-Noll-Vo''' (kurz: '''FNV''') ein [[Algorithmus]] zur Generierung von [[Streuwert]]en über Datenfelder: eine sogenannte [[Hash-Funktion]]. Nachnamensgeber des Kürzels ''FNV'' sind [[Glenn Fowler]], [[Landon Curt 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 [[Domain Name System|DN-Systemen]], [[Datenbank]]en und [[E-Mail-Server]]n. FNV eignet sich jedoch nicht für kryptographischen Einsatz.

== 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 oder Datenmengen lassen sich in [[Datenstruktur]]en indizieren und somit schneller auffinden (siehe [[Binärbaum]], [[B-Baum]], [[AVL-Baum]], [[Hashtabelle|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 ==
In [[C (Programmiersprache)|C]] bzw. [[C++]] kann die empfohlene<ref>
[http://www.isthe.com/chongo/tech/comp/fnv/#FNV-1a FNV bei Landon Curt Noll] Notiz am Ende des Abschnittes</ref> Version FNV-1a des Algorithmus folgendermaßen aussehen:

uint64_t
fnFNV (const uint8_t* pBuffer, const uint8_t* const pBufferEnd)
{
const uint64_t MagicPrime = 0x00000100000001b3;
uint64_t Hash = 0xcbf29ce484222325;

for ( ; pBuffer < pBufferEnd; pBuffer++)
Hash = (Hash ^ *pBuffer) * MagicPrime; // bitweises XOR und dann Multiplikation

return Hash;
}

In der Originalversion FNV-1 sind lediglich die Operationen [[XOR]] und Multiplikation innerhalb der Schleife vertauscht.

== 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 ==
* [http://www.isthe.com/chongo/tech/comp/fnv/ FNV] bei [[Landon Curt Noll]]

== Einzelnachweise ==
<references />

[[Kategorie:Hash|Fnv]]
[[Kategorie:Algorithmus|Fnv]]

FNV (Informatik) - Versionsgeschichte

imported>Skranon: Änderungen von 84.119.16.74 (Diskussion) auf die letzte Version von Wiki-Friend12345 zurückgesetzt