Editing Hash table (section)

===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>