Hash function

between keys "John Smith" and "Sandra Dee".

Uses your system voice; voice and rate in settings.

≈ 7 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

between keys "John Smith" and "Sandra Dee". A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a hash function are called hash values, hash codes, (hash/message) digests, or simply hashes.

The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter-storage addressing. Hash functions and their associated hash tables are used in data storage and retrieval applications to access data in a small and nearly constant time per retrieval.

They require an amount of storage space only fractionally greater than the total space required for the data or records themselves. Hashing is a way to access data quickly and efficiently. Unlike lists or trees, it provides near-constant access time.

It also uses much less storage than trying to store all possible keys directly, especially when keys are large or variable in length. Use of hash functions relies on statistical properties of key and function interaction: worst-case behavior is intolerably bad but rare, and average-case behavior can be nearly optimal (minimal collision).

Hash functions are related to (and often confused with) checksums, check digits, fingerprints, lossy compression, randomization functions, error-correcting codes, and ciphers. Although the concepts overlap to some extent, each one has its own uses and requirements and is designed and optimized differently. The hash function differs from these concepts mainly in terms of data integrity.

Hash tables may use non-cryptographic hash functions, while cryptographic hash functions are used in cybersecurity to secure sensitive data such as passwords. \frac{m}{n}{\sum_{j=1}^m b_j^2} - n where is the number of keys, is the number of buckets, and is the number of items in bucket . A ratio within one confidence interval (such as 0.95 to 1.05) is indicative that the hash function evaluated has an expected uniform distribution.

Hash functions can have some technical properties that make it more likely that they will have a uniform distribution when applied. One is the strict avalanche criterion: whenever a single input bit is complemented, each of the output bits changes with a 50% probability. The reason for this property is that selected subsets of the keyspace may have low variability.

For the output to be uniformly distributed, a low amount of variability, even one bit, should translate into a high amount of variability (i.e. distribution over the tablespace) in the output. Each bit should change with a probability of 50% because, if some bits are reluctant to change, then the keys become clustered around those values.

If the bits want to change too readily, then the mapping is approaching a fixed XOR function of a single bit. Standard tests for this property have been described in the literature. The relevance of the criterion to a multiplicative hash function is assessed here.

Applicability

A hash function that allows only certain table sizes or strings only up to a certain length, or cannot accept a seed (i.e. allow double hashing) is less useful than one that does. A hash function is applicable in a variety of situations.

Particularly within cryptography, notable applications include: Integrity checking: Identical hash values for different files imply equality, providing a reliable means to detect file modifications. Key derivation: Minor input changes result in a random-looking output alteration, known as the diffusion property. Thus, hash functions are valuable for key derivation functions.

Message authentication codes (MACs): Through the integration of a confidential key with the input data, hash functions can generate MACs ensuring the genuineness of the data, such as in HMACs. Password storage: The password's hash value does not expose any password details, emphasizing the importance of securely storing hashed passwords on the server.

Signatures: Message hashes are signed rather than the whole message.

Hashing integer data types

There are several common algorithms for hashing integers. The method giving the best distribution is data-dependent. One of the simplest and most common methods in practice is the modulo division method.

Other types of data can also use this hashing scheme. For example, when mapping character strings between upper and lower case, one can use the binary encoding of each character, interpreted as an integer, to index a table that gives the alternative form of that character ("A" for "a", "8" for "8", etc.). If each character is stored in 8 bits (as in extended ASCII or ISO Latin 1), the table has only 2 8 = 256 entries; in the case of Unicode characters, the table would have 17 × 2 16 = entries.

The same technique can be used to map two-letter country codes like "us" or "za" to country names (26 2 = 676 table entries), 5-digit ZIP codes like 13083 to city names ( entries), etc. Invalid data values (such as the country code "xx" or the ZIP code 00000) may be left undefined in the table or mapped to some appropriate "null" value. Define P(x)=\prod_{j\in S}(x-\alpha^j) where and where the coefficients of are computed in this field.

Then the degree of . Since is a root of whenever is a root, it follows that the coefficients of satisfy , so they are all 0 or 1. If is any nonzero polynomial modulo 2 with at most nonzero coefficients, then is not a multiple of modulo 2.

If follows that the corresponding hash function will map keys with fewer than bits in common to unique indices. The usual outcome is that either will get large, or will get large, or both, for the scheme to be computationally feasible.

Therefore, it is more suited to hardware or microcode implementation. unsigned hash(unsigned K) { return (a * K) >> (w - m); } and for fixed and this translates into a single integer multiplication and right-shift, making it one of the fastest hash functions to compute. Multiplicative hashing is susceptible to a "common mistake" that leads to poor diffusion—higher-value input bits do not affect lower-value output bits.

A transmutation on the input which shifts the span of retained top bits down and XORs or ADDs them to the key before the multiplication step corrects for this. The resulting function looks like: unsigned hash(unsigned K) { K ^= K >> (w - m); return (a * K) >> (w - m); } 16: a = 9E37 16 = 10 32: a = 16 = 10 48: a = 16 = 10 64: a = 16 = 10 The multiplier should be odd, so the least significant bit of the output is invertible modulo .

The last two values given above are rounded (up and down, respectively) by more than 1/2 of a least-significant bit to achieve this. The most familiar algorithm of this type is Rabin-Karp with best and average case performance and worst case (in all fairness, the worst case here is gravely pathological: both the text string and substring are composed of a repeated single character, such as ="AAAAAAAAAAA", and ="AAA").

The hash function used for the algorithm is usually the Rabin fingerprint, designed to avoid collisions in 8-bit character strings, but other suitable hash functions are also used.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378286790 under CC BY-SA 4.0; modifications have been made.

Words in each sectionHashing integer data ty…Hashing integer data typesHashing integer data types: 586 words586ApplicabilityApplicabilityApplicability: 158 words158
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001378286790 · captured 2026-10-03 · ledger · version history

Cite this page as: encyclopegia.org, “Hash function”, snapshot enwiki-001378286790. https://encyclopegia.org/a/hash-function

Sources cited in this revision

10 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.