Hash function: Difference between revisions

{{Redirect|Hash code|the programming competition|Hash Code (programming competition)}}

{{about|a computer programming construct|other meanings of "hash" and "hashing"|Hash (disambiguation)}}

*{{cite web|url=https://csrc.nist.gov/glossary/term/hash_digest|title=hash digest|publisher=[[NIST]] |website=Computer Security Resource Center - Glossary}}

*{{cite web |url=https://csrc.nist.gov/glossary/term/message_digest |title=message digest |publisher=[[NIST]] |website=Computer Security Resource Center - Glossary}}</ref> 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''.

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 [[hash collision|collision]]).<ref name="knuth-1973">{{cite book |last=Knuth |first=Donald E. |author-link=Donald Knuth |date=1973 |title=The Art of Computer Programming, Vol. 3, Sorting and Searching |publisher=[[Addison-Wesley]] |location=Reading, MA., United States|isbn=978-0-201-03803-3|bibcode=1973acp..book.....K }}</ref>{{rp|page=527}}

== Overview ==

In a hash table, a hash function takes a key as an input, which is associated with a datum or record and used to identify it to the data storage and retrieval application. The keys may be fixed-length, like an integer, or variable-length, like a name.  In some cases, the key is the datum itself.  The output is a hash code used to index a hash table holding the data or records, or pointers to them.

=== Uniformity ===

This criterion only requires the value to be ''uniformly distributed'', not ''random'' in any sense. A good randomizing function is (barring computational efficiency concerns) generally a good choice as a hash function, but the converse need not be true.

When testing a hash function, the uniformity of the distribution of hash values can be evaluated by the [[chi-squared test]].  This test is a goodness-of-fit measure: it is the actual distribution of items in buckets versus the expected (or uniform) distribution of items. The formula is

   

where {{Mvar|n}} is the number of keys, {{Mvar|m}} is the number of buckets, and {{Math|''b''_''j''}} is the number of items in bucket {{Mvar|j}}.

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.<ref>{{cite journal |first1=Julio Cesar Hernandez |last1=Castro |first2=José María |last2=Sierra |first3=Andre |last3=Seznec |first4=Antonio |last4=Izquierdo |first5=Arturo |last5=Ribagorda |display-authors=1 |date=3 February 2005 |title=The strict avalanche criterion randomness test |journal=Mathematics and Computers in Simulation |volume=68 |issue=1 |pages=1–7 |publisher=[[Elsevier]] |doi=10.1016/j.matcom.2004.09.001|s2cid=18086276 }}</ref>  The relevance of the criterion to a multiplicative hash function is assessed here.<ref name="fibonacci-hashing">{{cite web |first=Malte |last=Sharupke |title=Fibonacci Hashing: The Optimization that the World Forgot |url=https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/ |website=Probably Dance |date=16 June 2018}}</ref>

Because collisions should be infrequent, and cause a marginal delay but are otherwise harmless, it is usually preferable to choose a faster hash function over one that needs more computation but saves a few collisions.

We can allow the table size {{math|''n''}} to not be a power of 2 and still not have to perform any remainder or division operation, as these computations are sometimes costly. For example, let {{math|''n''}} be significantly less than {{math|2^''b''}}. Consider a [[pseudorandom number generator]] function {{math|''P''(key)}} that is uniform on the interval {{math|[0, 2^''b''&nbsp;−&nbsp;1]}}. A hash function uniform on the interval {{math|[0, ''n'' &minus; 1]}} is {{math|''n'' ''P''(key) / 2^''b''}}. We can replace the division by a (possibly faster) right [[bit shifting|bit shift]]: {{math|''n P''(key) >> ''b''}}.

=== Universality ===

{{main|Universal hashing}}

A ''universal hashing'' scheme is a [[randomized algorithm]] that selects a hash function {{math|''h''}} among a family of such functions, in such a way that the probability of a collision of any two distinct keys is {{math|1/''m''}}, where {{math|''m''}} is the number of distinct hash values desired—independently of the two keys. Universal hashing ensures (in a probabilistic sense) that the hash [[function application]] will behave as well as if it were using a random function, for any distribution of the input data. It will, however, have more collisions than perfect hashing and may require more operations than a special-purpose hash function.

Multiplicative hashing is susceptible to a "common mistake" that leads to poor diffusion&mdash;higher-value input bits do not affect lower-value output bits.<ref>

<syntaxhighlight lang="c">

unsigned hash(unsigned K) {

=== Zobrist hashing ===

Later, the method was extended to hashing integers by representing each byte in each of 4 possible positions in the word by a unique 32-bit random number.  Thus, a table of 2⁸×4 random numbers is constructed. A 32-bit hashed integer is transcribed by successively indexing the table with the value of each byte of the plain text integer and XORing the loaded values together (again, the starting value can be the identity value or a random seed). The natural extension to 64-bit integers is by use of a table of 2⁸×8 64-bit random numbers.

=== Rolling hash ===

{{Main|Rolling hash}}

{{See also|Linear congruential generator}}

In some applications, such as [[string searching algorithm|substring search]], one can compute a hash function {{math|''h''}} for every {{math|''k''}}-character [[substring]] of a given {{math|''n''}}-character string by advancing a window of width {{math|''k''}} characters along the string, where  {{math|''k''}} is a fixed integer, and {{Math|''n'' > ''k''}}. The straightforward solution, which is to extract such a substring at every character position in the text and compute {{math|''h''}} separately, requires a number of operations proportional to {{math|''k''·''n''}}. However, with the proper choice of {{math|''h''}}, one can use the technique of rolling hash to compute all those hashes with an effort proportional to {{math|''mk''&nbsp;+&nbsp;''n''}} where {{math|''m''}} is the number of occurrences of the substring.<ref>{{Cite book |last=Singh |first=N. B. |url=https://books.google.com/books?id=ALIMEQAAQBAJ&dq=rolling+hash&pg=PT102 |title=A Handbook of Algorithms |publisher=N.B. Singh |language=en}}</ref>{{fix|text=what is the choice of h?}}