Editing Hash table (section)

==Dynamic resizing==
Repeated insertions cause the number of entries in a hash table to grow, which consequently increases the load factor; to maintain the amortized <math>O(1)</math> performance of the lookup and insertion operations, a hash table is dynamically resized and the items of the tables are ''rehashed'' into the buckets of the new hash table,<ref name="cornell08" /> since the items cannot be copied over as varying table sizes results in different hash value due to [[modulo operation]].<ref>{{cite web|url=https://people.computing.clemson.edu/~goddard/texts/algor/C5.pdf|first=Wayne|last=Goddard|year=2021|access-date=4 December 2023|title=Chapter C5: Hash Tables|publisher=[[Clemson University]]|pages=15–16}}</ref> If a hash table becomes "too empty" after deleting some elements, resizing may be performed to avoid excessive [[Memory footprint|memory usage]].<ref>{{cite web|url=https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|title=Intro to Algorithms: Resizing Hash Tables|date=25 February 2011|first1=Srini|last1=Devadas|first2=Erik|last2=Demaine|publisher=[[Massachusetts Institute of Technology]], Department of Computer Science|via=[[MIT OpenCourseWare]]|archive-url=https://web.archive.org/web/20210507102944/https://courses.csail.mit.edu/6.006/spring11/rec/rec07.pdf|archive-date=7 May 2021|url-status=live|access-date=9 November 2021}}</ref>

===Resizing by moving all entries===
Generally, a new hash table with a size double that of the original hash table gets [[dynamic memory allocation|allocated]] privately and every item in the original hash table gets moved to the newly allocated one by computing the hash values of the items followed by the insertion operation. Rehashing is simple, but computationally expensive.<ref>{{cite book |last1=Thareja |first1=Reema |title=Data Structures Using C |date=2014 |publisher=Oxford University Press |isbn=978-0-19-809930-7 |chapter=Hashing and Collision |pages=464–488 }}</ref>{{rp|pp=478–479}}

===Alternatives to all-at-once rehashing===
Some hash table implementations, notably in [[real-time system]]s, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. If one cannot avoid dynamic resizing, a solution is to perform the resizing gradually to avoid storage blip—typically at 50% of new table's size—during rehashing and to avoid [[Fragmentation (computing)|memory fragmentation]] that triggers [[Mark-compact algorithm|heap compaction]] due to deallocation of large [[Page (computer memory)|memory blocks]] caused by the old hash table.<ref name="scott03">{{cite journal|journal=All Computer Science and Engineering Research|url=https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|doi= 10.7936/K7WD3XXV |date=18 March 2003|first1=Scott|last1=Friedman|first2=Anand|last2=Krishnan|first3=Nicholas|last3=Leidefrost|title=Hash Tables for Embedded and Real-time systems|publisher=[[Washington University in St. Louis]]|via=[[Northwestern University]], Department of Computer Science|archive-url=https://web.archive.org/web/20210609163643/https://users.cs.northwestern.edu/~sef318/docs/hashtables.pdf|archive-date=9 June 2021|access-date=9 November 2021|url-status=live}}</ref>{{rp|pp=2–3}} In such case, the rehashing operation is done incrementally through extending prior memory block allocated for the old hash table such that the buckets of the hash table remain unaltered. A common approach for amortized rehashing involves maintaining two hash functions <math>h_\text{old}</math> and <math>h_\text{new}</math>. The process of rehashing a bucket's items in accordance with the new hash function is termed as ''cleaning'', which is implemented through [[command pattern]] by encapsulating the operations such as <math>\mathrm{Add}(\mathrm{key})</math>, <math>\mathrm{Get}(\mathrm{key})</math> and <math>\mathrm{Delete}(\mathrm{key})</math> through a <math>\mathrm{Lookup}(\mathrm{key}, \text{command})</math> [[Wrapper function|wrapper]] such that each element in the bucket gets rehashed and its procedure involve as follows:{{r|scott03|p=3}}
* Clean <math>\mathrm{Table}[h_\text{old}(\mathrm{key})]</math> bucket.
* Clean <math>\mathrm{Table}[h_\text{new}(\mathrm{key})]</math> bucket.
* The ''command'' gets executed.

====Linear hashing====
{{main|Linear hashing}}
[[Linear hashing]] is an implementation of the hash table which enables dynamic growths or shrinks of the table one bucket at a time.<ref>{{cite conference | first=Witold | last=Litwin | title=Linear hashing: A new tool for file and table addressing | year=1980 | pages=212–223 | book-title=Proc. 6th Conference on Very Large Databases|publisher=[[Carnegie Mellon University]] | url=https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF | via=cs.cmu.edu|archive-url=https://web.archive.org/web/20210506233325/http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/linear-hashing.PDF|archive-date=6 May 2021|url-status=live|access-date=10 November 2021}}</ref>