A hash function turns any input into a fixed-size number for fast lookup

A hash function turns any input into a fixed-size number for fast lookup
Image: Intellect (generated)

In short: Imagine finding any item in a huge collection almost instantly, no matter how big it grows. A hash function makes this possible by mapping data of arbitrary size to a fixed-size value, which then points to a storage slot. The result is retrieval that stays close to constant in time, using only a little more space than the data itself.

A hash function accepts data of any size and maps it to a fixed-size value, often called a hash value, hash code, digest, or simply a hash. Those values are typically used to index a fixed-size table, known as a hash table. Using a hash function to index such a table is called hashing, or scatter-storage addressing. Hash tables store and retrieve records quickly, and they need only slightly more space than the records themselves. The mechanism works in three broad steps. First, variable-length keys are folded into fixed-length values, usually no longer than a machine word, using operations such as addition or exclusive-or.

Second, the bits are scrambled so that the outputs spread evenly across the key space. Third, the result is mapped to a value no larger than the table. A good function should be very fast to compute and should minimise collisions, which occur when two different inputs produce the same slot. Because collisions are unavoidable in practice, a collision-resolution method such as chaining or open addressing is always paired with the hash function.

The performance of hashing depends on statistics rather than guarantees. Worst-case behaviour can be poor, but it is rare, while average-case behaviour can be close to optimal. A high table loading factor or a badly chosen function can push access times toward linear in the number of items. Designers therefore aim for good average performance and, where the keys are known in advance, sometimes a perfect function with no collisions, though finding one for large key sets is usually computationally impractical. Hash functions also reach beyond tables. They underpin Bloom filters, which test efficiently whether an element belongs to a set, and they are used in cryptography for integrity checks, key derivation, message authentication and password storage. Cryptographic hashes differ from the non-cryptographic kind used in ordinary tables, and the two should not be confused. Hash functions are related to checksums and fingerprints, but each has its own purpose and design.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/technology-hash-function.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…