= Hash function
{title2=$h:U\to B$}
{wiki}
A <hash function> is a <function> assigning each key in an <input> <set> $U$ a value in an <output> <set> $B$. Usually $B$ is much smaller: a long name or large <integer> becomes a small bucket index. Equal keys must receive equal values from the same <hash function>; different keys may also receive equal values. Such a <hash collision> means "look in the same place", and does not establish key equality. If $|U|>|B|$, the <pigeonhole principle> makes some collisions unavoidable.
For example, <modular arithmetic> gives the <hash function> $h(k)=k\bmod7$, with seven bucket indices $0,\ldots,6$. Store the seven keys $0,2,3,10,11,17,24$: their values are respectively $0,2,3,3,4,3,3$. In particular, $h(3)=h(10)=3$ although $3\ne10$. A <hash table> is a <data structure> that uses these indices to locate records. With <separate chaining>, each bucket holds a <linked list> of records, so bucket $3$ retains all four keys $3,10,17,24$. Inserting $10$ must not overwrite $3$ merely because their <hash function> values agree.
\Image[/hash-bucket-collisions.png]
{title=Seven keys stored in seven buckets using the hash function h(k) = k mod 7}
{description=Orange arrows identify four colliding keys. Bucket 3 keeps all four records in a linked list; equality is checked on the stored keys.}
Searching for $10$ computes bucket $3$, then compares the actual keys until it reaches $10$. Searching for absent key $31$ reaches that same bucket and must reject every stored key. This <data structure> trades a search through all records for a search through one short chain, provided the <hash function> distributes keys adequately. A fixed <hash function> can perform poorly on patterned keys: $3,10,17,24$ already demonstrate the problem. A <universal hash family> introduces controlled randomness to limit the <expected value> of this extra work. Neither indexing nor a small collision <probability> inherently supplies <encryption> or <message authentication>; a <cryptographic hash function> has additional requirements such as <collision resistance>.
Back to article page
