kollisionsfreie

Kollisionsfrei describes a mapping that is one-to-one, meaning it maps distinct inputs to distinct outputs. More formally, a function f: X -> Y is kollisionsfrei if f(x1) = f(x2) implies x1 = x2. In consequence, every element of the image has a unique preimage.

In mathematical terms, kollisionsfreiheit is the property of injectivity. For finite sets, a necessary condition for a kollisionsfreies mapping is that the size of the domain does not exceed the size of the codomain (|X| ≤ |Y|). Examples include f(n) = 2n from natural numbers to natural numbers, which is injective, whereas f(n) = n^2 is not injective on Z because f(2) = f(-2).

In practical computing, the concept is often discussed in relation to hash functions and data structures. A hash function being kollisionsfrei would mean it yields a unique hash for every input within a given domain. In practice, global kollisionsfreiheit is rarely achievable for functions with large or infinite input spaces and finite output ranges. Therefore, terms such as kollisionarm (difficult to collide) and kollisionresistent (hard to find two inputs with the same output) are commonly used. A common workaround is a perfect hash function, which is kollisionsfrei for a specific, fixed set of keys.

Limitations include the impossibility of global collision-freedom in many contexts and the dependence on the chosen domain and codomain. The term emphasizes the one-to-one correspondence of inputs and outputs in the described setting.