Editing Hash table (section)

===Load factor===
A ''load factor'' <math>\alpha</math> is a critical statistic of a hash table, and is defined as follows:<ref name="Cormen et al" />
<math display="block">\text{load factor}\ (\alpha) = \frac{n}{m},</math>
where
* <math>n</math> is the number of entries occupied in the hash table.
* <math>m</math> is the number of buckets.

The performance of the hash table deteriorates in relation to the load factor <math>\alpha</math>.{{r|hashhist|p=2}}

The software typically ensures that the load factor <math>\alpha</math> remains below a certain constant, <math>\alpha_{\max}</math>. This helps maintain good performance. Therefore, a common approach is to resize or "rehash" the hash table whenever the load factor <math>\alpha</math> reaches <math>\alpha_{\max}</math>. Similarly the table may also be resized if the load factor drops below <math>\alpha_{\max}/4</math>.<ref name="cornell08">{{cite web|url=https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|title=CS 312: Hash tables and amortized analysis|publisher=[[Cornell University]], Department of Computer Science|first=Andrew|last=Mayers|access-date=26 October 2021|year=2008|archive-url=https://web.archive.org/web/20210426052033/http://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref>

==== Load factor for separate chaining ====

With separate chaining hash tables, each slot of the bucket array stores a pointer to a list or array of data.<ref name="plank" />

Separate chaining hash tables suffer gradually declining performance as the load factor grows, and no fixed point beyond which resizing is absolutely needed.<ref name="cornell08" />

With separate chaining, the value of <math>\alpha_{\max}</math> that gives best performance is typically between 1 and 3.<ref name="cornell08" />

==== Load factor for open addressing ====

With open addressing, each slot of the bucket array holds exactly one item. Therefore an open-addressed hash table cannot have a load factor greater than 1.<ref name="plank" >
James S. Plank and Brad Vander Zanden.
[http://web.eecs.utk.edu/~bvanderz/teaching/cs140Sp15/Notes/Hashing/ "CS140 Lecture notes -- Hashing"].
</ref>

The performance of open addressing becomes very bad when the load factor approaches 1.<ref name="cornell08" />

Therefore a hash table that uses open addressing ''must'' be resized or ''rehashed'' if the load factor <math>\alpha</math> approaches 1.<ref name="cornell08" />

With open addressing, acceptable figures of max load factor <math>\alpha_{\max}</math> should range around 0.6 to 0.75.<ref>{{cite journal |last1=Maurer |first1=W. D. |last2=Lewis |first2=T. G. |title=Hash Table Methods |journal=ACM Computing Surveys |date=March 1975 |volume=7 |issue=1 |pages=5–19 |doi=10.1145/356643.356645 |s2cid=17874775 }}</ref>{{r|owo03|p=110}}