Kollisionsfrei

Kollisionsfrei bedeutet in der Informatik, dass eine Abbildung Eingaben eindeutig auf Ausgaben abbildet. Formal spricht man von einer injektiven Funktion: Eine Funktion f: D → C ist kollisionsfrei, wenn x und y in D mit x ≠ y stets unterschiedliche Ausgaben f(x) ≠ f(y) haben. In der Praxis wird häufig der Definitionsbereich eingeschränkt, sodass eine solche eindeutige Zuordnung überhaupt möglich ist.

Anwendungen finden sich vor allem im perfekten Hashing. Für eine gegebene Schlüsselmenge S lässt sich eine Hashfunktion wählen, die alle Schlüssel von S eindeutig auf eine Zielmenge abbildet. Ebenso kann in Datenbanken oder Codierungssystemen eine eindeutige Kennung erzeugt werden, die innerhalb des betrachteten Datensatzes kollisionsfrei bleibt. Kollisionsfreie Kodierungen dienen auch der Kompaktheit oder der schnellen Zuordnung von Schlüssel-Wert-Paaren.

Grenzen und Unterschiede zu anderen Eigenschaften: Echte globale Kollisionsfreiheit kann es nicht geben, da Domain und Codomain oft endlich sind und verschiedene Inputs denselben Output liefern müssen (Pigeonhole-Prinzip). In der Kryptografie spricht man statt von Kollisionsfreiheit häufiger von kollisionsresistenten Hashfunktionen; eine absolut kollisionsfreie Funktion lässt sich theoretisch nicht garantieren. Praktisch strebt man an, Kollisionsmöglichkeiten schwer oder unpraktisch zu finden oder zu vermeiden.

Beispiele sind ein perfekter Hash für eine kleine Wortliste, bei dem jedes Wort eine eigene Zahl erhält, oder ein ID-System, das neue Elemente eindeutig zuordnet, ohne vorhandene IDs zu duplizieren.

Siehe auch: perfekter Hash, injektive Funktion, Hash-Funktion, Kollisionsresistenz.