Collision (computer science)
Collision is used in two slightly different senses in theoretical computer science and telecommunications. In computer science it refers to a situation where a function maps two distinct inputs to the same output. In telecommunications, a collision occurs when two nodes of a network attempt to transmit at the same time.
In theoretical computer science
A collision or clash occurs when two different inputs to a function, typically one used to compress large data items into a smaller or fixed size, produce the same output, called (depending on the application) a hash value, checksum, fingerprint, or digest.
Collisions are unavoidable whenever members of a very large set (such as all possible person names, or all possible computer files) are mapped to a relatively short bit string. This is merely an instance of the pigeonhole principle.
This section does not cite any sources. (July 2017) (Learn how and when to remove this template message)
Half-duplex (HDX) data communications networks have the possibility that more than one node will transmit at the same or overlapping time. The messages sent by the transmitting nodes become corrupted. This event is referred to as a collision. The receiving nodes will receive (in most but not all cases) random data. In half-duplex networks, the transmitting node must ensure that the network is quiet prior to transmitting, and in addition there is usually some mechanism for transmitting nodes to detect overlapping transmissions.
- Birthday attack
- Collision attack (cryptographic hash functions)
- Collision resolution, in the context of hash tables
- Delimiter collision
- Name collision
- Perfect hash function, a hash function that is free of collisions by design
- Miller, Bradley N.; Ranum, David L. (2011). "5.5. Hashing". Problem Solving with Algorithms and Data Structures using Python. Franklin, Beedle & Associates. ISBN 978-1590282571.
- Paar, Christof; Pelzl, Jan (27 November 2009). Understanding Cryptography: A Textbook for Students and Practitioners. Springer Science & Business Media. p. 298. ISBN 9783642041013.