Streufelder (engl. Hashtables) benötigen für ihre effiziente Funktion (Zugriffskomplexität O(1)) qualitativ hochwertige Streufunktionen. Streufelder sind die Leistungs-bestimmenden Datenstrukturen vieler wichtiger DV-Systeme wie z.B. Übersetzer oder auch in der statistischen Massendatenauswertung ("Big Data"). Genauer gesagt muß die Streufunktion für eine Menge von Eingabe-Schlüsseln ME (typischerweise Zeichenketten variabler Länge) eine Menge MS an Streuwerten (typischerweise Ganzzahlen 16, 32 oder 64 bit) liefern. Die Menge MS wird dabei im Allgemeinen Fall immer mindestens 36% kleiner als der die Menge der möglichen Zahlenwerte MZW sein. Im Falle sub-optimaler Streufunktionenwird MS noch wesentlich kleiner sein, bis hin zu 10% von MZW ! Diese Untersuchung wird aufzeigen, dass weithin bekannte Streufunktionen wie z.B. ADLER32 sub-optimal sind und durch bessere Streufunktionen auf Grundlage stark nichtlineaerer Funktionen ("S-Boxen") ersetzt werden sollten.
Durch einfache logische Überlegung kann gezeigt werden, dass kryptografisch starke Streufunktionen (KSSF) wie z.B. MD5 oder SHA gleichzeit optimale Streufunktionen für die Anwendung in Streufeldern sind:
KSSFs wurden entwickelt, um für beliebige Datenstrukturen eine "kryptografisch starke" Prüfsumme zu berechnen. Die Änderung eines einzigen oder mehr Bits in der Eingabe soll dabei im Mittel 50% der Ausgabebits (eine Prüfsumme der Länge 128 oder 256 bit) umkippen lassen. Zudem soll es sehr schwer sein, die Eingabe so zu modifizieren, daß dieselbe Prüsumme nach einer Modifikation erzielt wird. Diese Anforderungen erreicht schon die relativ alte Streufunktion MD5 mit sehr hoher Perfektion. Fast genau dieselben Anforderungen werden an eine Streufunktion eines Streufeldes gestellt, allerdings mit der Abschwächung daß bei einer Streufunktion i.d.R. keine Resistenz gegen gezielte "Dokumentenfälschung" gestellt wird. Die kanonisch besten Streufunktionen sind kryptografisch starke Streufunktionen (KSSFs). Es gibt keine qualitativ besseren, sondern allenfalls Funktionen mit geringerer Laufzeit, was natürlich ein wichtiger Aspekt ist. Verschiedene Autoren im Internet behaupten, Streufunktionen für Streufelder müssten "dem Problem angepasst" entwickelt werden. Dies ist nicht korrekt. KSSFs sind qualitativ optimale Streufunktionen - für alle Anwendungen von Streufeldern.Im Folgenden wird die "Streuwirkung" von Streufunktionen empirisch ermittelt. Dabei wird eine synthetische Menge von Schlüsseln erzeugt und danach mit Hilfe eines einfachen Zählerfeldes (Mit derselben Anzahl Felder wie die Anzahl der Schlüssel) die Menge der Kollisionen pro Feldeintrag ermittelt. Danach wird mittels eines Histogramms eine Aussage über die Menge der Kollisionen und damit die Qualität der Streufunktion gemacht.
Bei diesem Vergleich werden die Zahlen von 0 bis 999999 sowie Zeichenkette mit angehängter Zahl als Schlüsselmenge benutzt. Die Feldlaenge ist, falls nicht anders angegeben, 1000000. Von den vier Szenarien (siehe Quellcode) wird das schlechteste als Ergebnis gewählt.
| Funktion | CPU-Laufzeit [ms] | Histogramm der Feld-Nutzung | Kommentar |
|---|---|---|---|
| SHA256 | 2949 | 0 367826 1 368100 2 183760 3 61184 4 15470 5 3111 6 461 7 78 8 9 9 1 |
Die Optimale Streufunktion schafft es also, 73% eines Streufeldes zu nutzen. Die Anzahl der Felder mit mehr als 5 Kollisionen ist minimal. Laufzeit ist jedoch relativ hoch. |
| ADLER32 | 746 | 0 989199 1 1567 2 858 3 599 4 422 5 341 6 317 7 248 8 237 9 196 10 200 11 161 12 158 13 128 14 116 15 98 16 102 17 86 18 88 19 76 - weitere ca 200 Abgeschnitten ! - |
Diese Streufunktion schafft es also gerade einmal, etwa 2% der Streutabelle überhaupt auszunutzen ! Die Laufzeit ist auch nicht die Beste. |
| Suchoi | 632 |
0 368207 1 367533 2 183877 3 61229 4 15388 5 3143 6 515 7 78 8 11 9 2 |
Diese Funktion (Eigentwicklung des Autors) ist keine KSSF, zeigt aber fast identische Qualität. Zudem ist die Laufzeit kurz. |
| Suchoi mit Feldgroesse 2^20 (1048576) | 632 |
0 607743 1 245006 2 50597 3 25284 4 71583 5 26075 6 5330 7 2588 8 4153 9 1398 10 303 11 150 12 4905 13 1795 14 328 15 201 16 662 17 253 18 52 19 37 20 62 21 23 22 5 23 1 24 25 25 7 26 4 27 2 28 4 |
Hier zeit sich eine nicht-triviale Schwäche von Suchoi im Falle der Kompression auf eine Zweierpotenz. Bei anderen Zahlen tritt diese Schwäche jedoch nicht auf. |
| Verbesserte Suchoi-Funktion "Suchoi2" | 681 |
0 386132 1 385381 2 192729 3 64292 4 16105 5 3281 6 573 7 70 8 9 9 4 |
Im Vergleich zu Suchoi werden am Schluss noch vier Rotationen des Zustands miteinander XOR-verknüpft. Auch im Falle der Feldgroesse 2^20 erzielt der Algorithmus damit sehr gute Ergebnisse. |
| Paul Larson | 537 |
0 802557 1 13849 2 20398 3 15189 4 32477 5 37966 6 20745 7 22752 8 17523 9 11182 10 3488 11 1874 |
Keine besonders gute Funktion |
| Paul Larson mit primaler Groesse des Streufeldes (999983) | 537 |
0 385575 1 341350 2 185129 3 67228 4 17264 5 3017 6 391 7 28 8 1 |
Hier kann man eine dramatische Verbesserung durch die primale Groesse des Streufelds feststellen ! |
| CRC32 | 1820 |
0 367626 1 368178 2 183995 3 61305 4 15293 5 2995 6 506 7 87 8 10 9 5 |
Eine (fast) optimale Hashfunktion, allerdings mit relativ langer Laufzeit. |
| PJW | 518 |
0 1010176 1 512 2 768 3 512 4 768 5 512 6 768 7 512 8 256 9 0 10 256 11 0 12 256 13 0 14 256 15 0 16 256 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 512 25 1024 26 1024 27 1024 28 1024 29 1024 30 1024 31 1024 32 25088 |
Eine qualitativ sehr schlechte Streufunktion. |
| FGMult | 711 |
0 368581 1 367197 2 183355 3 61721 4 15481 5 3087 6 486 7 83 8 7 9 2 |
Eine (fast) optimale Streufunktion des Autors. Benutzt Multiplikation als Nichtlinearität |
| FGMult_ww | 441 |
0 372258 1 363500 2 181685 3 62126 4 16260 5 3462 6 575 7 122 8 10 9 2 |
Eine (fast) optimale Streufunktion des Autors. Benutzt 64-bit Multiplikation als Nichtlinearität |
| FG_ww_shift | 428 |
0 373535 1 362292 2 181114 3 62097 4 16585 5 3554 6 698 7 110 8 14 9 1 |
Eine (fast) optimale Streufunktion des Autors. Benutzt 64-bit Bitverschiebung und Additionsoperationen |
| MurmurHash | 410 |
0 367735 1 368116 2 184136 3 60933 4 15296 5 3183 6 509 7 78 8 12 9 2 |
Eine (fast) optimale Streufunktion. Diese Funktion ist Teil der libc sowie der STL auf Linux. Die Laufzeit ist ebenfalls sehr gut. |
| Bölkow | 465 |
0 385594 1 385994 2 192869 3 64277 4 15935 5 3279 6 534 7 81 8 10 9 3 |
Fast optimale Streufunktion des Autors auf Basis einer nichtlineaeren Funktion. Laufzeit ebenso konkurrenzfähig. |
Es wurde ein "Intel(R) Core(TM) i5-6200U CPU @ 2.30GHz" für die Leistungsmessungen benutzt. Der Quellcode kann von GIT heruntergeladen werden.