Where does hash collide?

A rule that maps data of arbitrary size to a value of fixed size, called the hash or digest, so that the same input always yields the same output and unrelated inputs rarely land on the same value. A cryptographic hash function adds the demand that the digest be hard to invert and hard to collide on purpose. Menezes, van Oorschot, and Vanstone's 1996 Handbook of Applied Cryptography set out these functions and the properties, preimage and collision resistance, that a secure one must hold. The referent is the mapping itself and the digest it returns, not the array that stores keyed records, a dish of chopped meat, or a line painted on a playing field.[1]

Unit

A deterministic map from arbitrary input to a fixed-size digest

Recovery means

Not applicable

Measured by

Assessed by output length in bits and by resistance to preimage and collision attacks

A data structure that stores records in an array whose index is computed from each record's key by a hash function, so that on average a lookup, insertion, or deletion takes constant time however many records are held. It is a container, not the function it calls: the function is one component, while the table also fixes the array, the way collisions are resolved, and the load policy. Knuth's The Art of Computer Programming, Volume 3: Sorting and Searching treats hashing as a search method and analyses these tables and their collision strategies in detail, and Carter and Wegman's work on universal hashing shows how the function is chosen so the table performs well. The referent is the keyed store and its average constant-time access, not the mapping alone, a plate of food, or a field marking.[2][3]

Unit

A keyed array store, sized by capacity and load factor

Recovery means

Not applicable

Measured by

Assessed by average lookup, insertion, and deletion time and by load factor