Editing Hash table (section)

=====Hopscotch hashing=====
{{main| Hopscotch hashing}}

[[Hopscotch hashing]] is an open addressing based algorithm which combines the elements of [[cuckoo hashing]], [[linear probing]] and chaining through the notion of a ''neighbourhood'' of buckets—the subsequent buckets around any given occupied bucket, also called a "virtual" bucket.<ref name="nir08">{{cite book |doi=10.1007/978-3-540-87779-0_24 |chapter=Hopscotch Hashing |title=Distributed Computing |series=Lecture Notes in Computer Science |date=2008 |last1=Herlihy |first1=Maurice |last2=Shavit |first2=Nir |last3=Tzafrir |first3=Moran |volume=5218 |pages=350–364 |isbn=978-3-540-87778-3 }}</ref>{{rp|pp=351–352}} The algorithm is designed to deliver better performance when the load factor of the hash table grows beyond 90%; it also provides high throughput in [[Concurrent computing|concurrent settings]], thus well suited for implementing resizable [[concurrent hash table]].{{r|nir08|p=350}} The neighbourhood characteristic of hopscotch hashing guarantees a property that, the cost of finding the desired item from any given buckets within the neighbourhood is very close to the cost of finding it in the bucket itself; the algorithm attempts to be an item into its neighbourhood—with a possible cost involved in displacing other items.{{r|nir08|p=352}}

Each bucket within the hash table includes an additional "hop-information"—an ''H''-bit [[bit array]] for indicating the [[Euclidean distance#One dimension|relative distance]] of the item which was originally hashed into the current virtual bucket within ''H''&nbsp;−&nbsp;1 entries.{{r|nir08|p=352}} Let <math>k</math> and <math>Bk</math> be the key to be inserted and bucket to which the key is hashed into respectively; several cases are involved in the insertion procedure such that the neighbourhood property of the algorithm is vowed:{{r|nir08|pp=352–353}} if <math>Bk</math> is empty, the element is inserted, and the leftmost bit of bitmap is [[Bitwise operation|set]] to 1; if not empty, linear probing is used for finding an empty slot in the table, the bitmap of the bucket gets updated followed by the insertion; if the empty slot is not within the range of the ''neighbourhood,'' i.e. ''H''&nbsp;−&nbsp;1, subsequent swap and hop-info bit array manipulation of each bucket is performed in accordance with its neighbourhood [[Invariant (mathematics)|invariant properties]].{{r|nir08|p=353}}