Hash-Kollisionen
Hashfunktionen sind nicht perfekt; manchmal erzeugen sie für völlig unterschiedliche Dateneingaben denselben Hashwert. Dabei wird die gewünschte Eins-zu-eins-Zuordnung zwischen Eingaben und Hashwerten verletzt. Das kann bedeuten, dass unterschiedliche Zeichenketten oder Zahlenpaare denselben Hash haben. Solche Kollisionen können zu Sicherheitsproblemen und Leistungsengpässen führen, je nachdem in welchem Zusammenhang sie auftreten. Ein einfaches Beispiel ist eine Hashfunktion, die einem Zahlenpaar (a, b) einen Hashwert zuordnet:
Hier führen verschiedene
(a, b)-Paare zum selben Hashwert:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Wenn wir nun eine Liste solcher Paare hätten, die bewusst auf denselben Hashwert abzielen, gäbe es viele Kollisionen. Die Suche nach einem bestimmten Wert oder die Überprüfung, ob ein Paar
(a, b) in der Liste enthalten ist, würde dadurch sehr ineffizient oder womöglich sogar fehlerhaft (je nach Implementierung).Hash-Kollisionen können außerdem eine Sicherheitslücke darstellen. Benutzerpasswörter werden oft als Hashwerte gespeichert, damit sie selbst bei einem Datenbankdiebstahl nicht im Klartext sichtbar werden. Bei einer schlechten Hashfunktion, die viele Kollisionen erzeugt, könnten Angreifer ein Konto knacken, ohne das richtige Passwort zu erraten. Es würde genügen, wenn ein zufällig gewähltes Passwort denselben Hash erzeugt wie das ursprüngliche – das System würde denken, es handelt sich um die gleiche Person.
Eine gute Hashfunktion versucht, möglichst wenige Kollisionen zu erzeugen. Die eingebauten Hashfunktionen von Programmiersprachen leisten in der Regel gute Dienste bei zufälligen Eingaben. Allerdings kann es vorkommen, dass die Eingabedaten einen besonderen Aufbau haben oder dass das Problem spezielle Anforderungen stellt. In solchen Fällen ist es sinnvoll, eine angepasste Hashfunktion zu verwenden.
Herausforderung: Kollisionen prüfen
Es wird eine Hashfunktion
h vorgegeben, die einem Zahlenpaar (a, b) einen ganzzahligen Wert zuordnet. Die Aufgabe besteht darin zu überprüfen, ob h für die vorliegenden Eingaben ausreichend gut ist. Das Programm soll feststellen, ob es Kollisionen gibt, und es soll Yes ausgeben, falls keine Kollisionen gefunden werden, andernfalls No. Die Hashfunktion ist definiert als:Eingabe
Die erste Zeile der Eingabe enthält eine einzige ganze Zahl
n (1 ≤ n ≤ 10 000), die Anzahl der Paare.Die nächsten
n Zeilen beinhalten jeweils zwei durch Leerzeichen getrennte ganze Zahlen (0 ≤ ≤ ). Es ist garantiert, dass alle eingegebenen Paare eindeutig sind.Ausgabe
Das Programm soll
Yes ausgeben, wenn es bei der gegebenen Eingabe keine Kollision gibt und die Hashfunktion somit „gut genug“ ist. Andernfalls soll No ausgegeben werden.Beispiele
Eingabe | Ausgabe |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB