Editing Hash table (section)

=====Robin Hood hashing=====
Robin Hood hashing is an open addressing based collision resolution algorithm; the collisions are resolved through favouring the displacement of the element that is farthest—or longest ''probe sequence length'' (PSL)—from its "home location" i.e. the bucket to which the item was hashed into.<ref name="waterloo86">{{cite book|title=Robin Hood Hashing|first=Pedro|last=Celis|publisher=[[University of Waterloo]], Dept. of Computer Science|year=1986|url=https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf |location=Ontario, Canada|isbn= 978-0-315-29700-5 |oclc= 14083698|archive-url=https://web.archive.org/web/20211101071032/https://cs.uwaterloo.ca/research/tr/1986/CS-86-14.pdf|archive-date=1 November 2021|access-date=2 November 2021|url-status=live}}</ref>{{rp|p=12}} Although Robin Hood hashing does not change the [[Computational complexity theory|theoretical search cost]], it significantly affects the [[variance]] of the [[Probability distribution|distribution]] of the items on the buckets,<ref>{{cite journal |last1=Poblete |first1=P. V. |last2=Viola |first2=A. |title=Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions |journal=Combinatorics, Probability and Computing |date=July 2019 |volume=28 |issue=4 |pages=600–617 |doi=10.1017/S0963548318000408 |s2cid=125374363 }}</ref>{{rp|p=2}} i.e. dealing with [[Cluster analysis|cluster]] formation in the hash table.<ref name="cornell14">{{cite web|url=https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|title= Lecture 13: Hash tables|publisher=[[Cornell University]], Department of Computer Science|first=Michael|last=Clarkson|access-date=1 November 2021|year=2014|archive-url=https://web.archive.org/web/20211007011300/https://www.cs.cornell.edu/courses/cs3110/2014fa/lectures/13/lec13.html|archive-date=7 October 2021|url-status=live|via=cs.cornell.edu}}</ref> Each node within the hash table that uses Robin Hood hashing should be augmented to store an extra PSL value.<ref>{{cite web|publisher=[[Cornell University]], Department of Computer Science|url=https://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|title=JavaHyperText and Data Structure: Robin Hood Hashing|access-date=2 November 2021|first=David|last=Gries|year=2017|archive-url=https://web.archive.org/web/20210426051503/http://www.cs.cornell.edu/courses/JavaAndDS/files/hashing_RobinHood.pdf|archive-date=26 April 2021|url-status=live|via=cs.cornell.edu}}</ref> Let <math>x</math> be the key to be inserted, <math>x{.}\text{psl}</math> be the (incremental) PSL length of <math>x</math>, <math>T</math> be the hash table and <math>j</math> be the index, the insertion procedure is as follows:{{r|waterloo86|pp=12-13}}<ref name="indiana88">{{cite tech report|first=Pedro|last=Celis|date=28 March 1988| number=246|institution=[[Indiana University]], Department of Computer Science|location=Bloomington, Indiana| url=https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-url=https://web.archive.org/web/20211103013505/https://legacy.cs.indiana.edu/ftp/techreports/TR246.pdf|archive-date=3 November 2021|access-date=2 November 2021|url-status=live| title=External Robin Hood Hashing}}</ref>{{rp|p=5}}
* If <math>x{.}\text{psl}\ \le\ T[j]{.}\text{psl}</math>: the iteration goes into the next bucket without attempting an external probe.
* If <math>x{.}\text{psl}\ >\ T[j]{.}\text{psl}</math>: insert the item <math>x</math> into the bucket <math>j</math>; swap <math>x</math> with <math>T[j]</math>—let it be <math>x'</math>; continue the probe from the <math>(j+1)</math>th bucket to insert <math>x'</math>; repeat the procedure until every element is inserted.