Editing Hash table (section)

==Performance==
The performance of a hash table is dependent on the hash function's ability in generating [[Low-discrepancy sequence|quasi-random numbers]] (<math>\sigma</math>) for entries in the hash table where <math>K</math>, <math>n</math> and <math>h(x)</math> denotes the key, number of buckets and the hash function such that <math>\sigma\ =\ h(K)\ \%\ n</math>. If the hash function generates the same <math>\sigma</math> for distinct keys (<math>K_1 \ne K_2,\ h(K_1)\ =\ h(K_2)</math>), this results in ''collision'', which is dealt with in a variety of ways. The constant time complexity (<math>O(1)</math>) of the operation in a hash table is presupposed on the condition that the hash function doesn't generate colliding indices; thus, the performance of the hash table is [[Proportionality (mathematics)#Direct proportionality|directly proportional]] to the chosen hash function's ability to [[Statistical dispersion|disperse]] the indices.<ref name="dijk10">{{cite web|title=Analysing and Improving Hash Table Performance|first=Tom Van|last=Dijk|publisher=[[University of Twente]]|location=[[Netherlands]]|url=https://www.tvandijk.nl/pdf/bscthesis.pdf|access-date=31 December 2021|archive-url=https://web.archive.org/web/20211106094558/http://www.tvandijk.nl/pdf/bscthesis.pdf|archive-date=6 November 2021|url-status=live|year=2010}}</ref>{{rp|1}} However, construction of such a hash function is [[NP-hardness|practically infeasible]], that being so, implementations depend on [[Use case|case-specific]] [[#Collision resolution|collision resolution techniques]] in achieving higher performance.{{r|dijk10|p=2}}