Editing Hash table (section)

===Choosing a hash function===

[[Uniform distribution (discrete)|Uniform distribution]] of the hash values is a fundamental requirement of a hash function. A non-uniform distribution increases the number of collisions and the cost of resolving them. Uniformity is sometimes difficult to ensure by design, but may be evaluated empirically using statistical tests, e.g., a [[Pearson's chi-squared test#Discrete uniform distribution|Pearson's chi-squared test]] for discrete uniform distributions.<ref name="chernoff">{{Cite journal | first=Karl |last=Pearson |author1-link=Karl Pearson | year = 1900 | title = On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling | journal = Philosophical Magazine |series=Series 5 | volume = 50 | number = 302 | pages = 157–175 | doi=10.1080/14786440009463897 |url=https://zenodo.org/record/1430618 }}</ref><ref name="plackett">{{Cite journal |first=Robin |last=Plackett |author1-link=Robin Plackett | year = 1983 | title =  Karl Pearson and the Chi-Squared Test | journal = International Statistical Review | volume = 51 | number = 1 | pages = 59–72 | doi=10.2307/1402731 |jstor=1402731 }}</ref>
	
The distribution needs to be uniform only for table sizes that occur in the application. In particular, if one uses dynamic resizing with exact doubling and halving of the table size, then the hash function needs to be uniform only when the size is a [[power of two]]. Here the index can be computed as some range of bits of the hash function. On the other hand, some hashing algorithms prefer to have the size be a [[prime number]].<ref name=":0">{{Cite web|title = Prime Double Hash Table|url = https://www.concentric.net/~Ttwang/tech/primehash.htm|date = March 1997|access-date = 2015-05-10|last = Wang|first = Thomas|archive-url = https://web.archive.org/web/19990903133921/http://www.concentric.net/~Ttwang/tech/primehash.htm|archive-date = 1999-09-03|url-status=dead}}</ref>

For [[open addressing]] schemes, the hash function should also avoid ''[[Primary clustering|clustering]]'', the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash is claimed to have particularly poor clustering behavior.<ref name=":0" /><ref name="knuth"/>
	
[[K-independent hashing]] offers a way to prove a certain hash function does not have bad keysets for a given type of hashtable. A number of K-independence results are known for collision resolution schemes such as linear probing and cuckoo hashing. Since K-independence can prove a hash function works, one can then focus on finding the fastest possible such hash function.<ref>{{cite journal |last1=Wegman |first1=Mark N. |last2=Carter |first2=J.Lawrence |title=New hash functions and their use in authentication and set equality |journal=Journal of Computer and System Sciences |date=June 1981 |volume=22 |issue=3 |pages=265–279 |doi=10.1016/0022-0000(81)90033-7 |doi-access=free }}</ref>