Editing Hash table (section)

===Separate chaining===
[[File:Hash table 5 0 1 1 1 1 1 LL.svg|thumb|450px|right|Hash collision resolved by separate chaining]]
[[File:Hash table 5 0 1 1 1 1 0 LL.svg|thumb|right|500px|Hash collision by separate chaining with head records in the bucket array.]]

In separate chaining, the process involves building a [[linked list]] with [[key–value pair]] for each search array index. The collided items are chained together through a single linked list, which can be traversed to access the item with a unique search key.{{r|algo1rob|p=464}} Collision resolution through chaining with linked list is a common method of implementation of hash tables. Let <math>T</math> and <math>x</math> be the hash table and the node respectively, the operation involves as follows:<ref name="cormenalgo01">{{cite book|last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen|last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson|last3=Rivest |first3=Ronald L. |author3-link=Ronald L. Rivest|last4=Stein |first4=Clifford |author4-link=Clifford Stein| title = Introduction to Algorithms| publisher = [[Massachusetts Institute of Technology]]| year= 2001| isbn = 978-0-262-53196-2| edition = 2nd|chapter = Chapter 11: Hash Tables|title-link=Introduction to Algorithms }}</ref>{{rp|p=258}}
<!-- the lines with only a space are significant. don't remove the lines or the spaces -->
 Chained-Hash-Insert(''T'', ''k'')
   ''insert'' ''x'' ''at the head of linked list'' ''T''[''h''(''k'')]
 
 Chained-Hash-Search(''T'', ''k'')
   ''search for an element with key'' ''k'' ''in linked list'' ''T''[''h''(''k'')]
 
 Chained-Hash-Delete(''T'', ''k'')
   ''delete'' ''x'' ''from the linked list'' ''T''[''h''(''k'')]

If the element is comparable either [[Sequence#Analysis|numerically]] or [[Lexicographic order|lexically]], and inserted into the list by maintaining the [[total order]], it results in faster termination of the unsuccessful searches.{{r|donald3|pp=520-521}}

====Other data structures for separate chaining====

If the keys are [[total order|ordered]], it could be efficient to use "[[Optimal binary search tree|self-organizing]]" concepts such as using a [[self-balancing binary search tree]], through which the [[Worst-case complexity|theoretical worst case]] could be brought down to <math>O(\log{n})</math>, although it introduces additional complexities.{{r|donald3|p=521}}

In [[dynamic perfect hashing]], two-level hash tables are used to reduce the look-up complexity to be a guaranteed <math>O(1)</math> in the worst case. In this technique, the buckets of <math>k</math> entries are organized as [[Perfect hash function|perfect hash tables]] with <math>k^2</math> slots providing constant worst-case lookup time, and low amortized time for insertion.<ref>{{cite web |first1=Erik |last1=Demaine |first2=Jeff |last2=Lind |work=6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory |date=Spring 2003 |url=http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |title=Lecture 2 |access-date=2008-06-30 |url-status=live |archive-url=https://web.archive.org/web/20100615203901/http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf |archive-date=June 15, 2010 |df=mdy-all }}</ref> A study shows array-based separate chaining to be 97% more performant when compared to the standard linked list method under heavy load.{{r|nick05|p=99}}

Techniques such as using [[fusion tree]] for each buckets also result in constant time for all operations with high probability.<ref>{{cite journal | last = Willard | first = Dan E. | author-link = Dan Willard | doi = 10.1137/S0097539797322425 | issue = 3 | journal = [[SIAM Journal on Computing]] | mr = 1740562 | pages = 1030–1049 | title = Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree | volume = 29 | year = 2000}}.</ref>

==== Caching and locality of reference ====
The linked list of separate chaining implementation may not be [[Cache-oblivious algorithm|cache-conscious]] due to [[spatial locality]]—[[locality of reference]]—when the nodes of the linked list are scattered across memory, thus the list traversal during insert and search may entail [[CPU cache]] inefficiencies.<ref name="nick05">{{cite book |doi=10.1007/11575832_1 |chapter=Enhanced Byte Codes with Restricted Prefix Properties |title=String Processing and Information Retrieval |series=Lecture Notes in Computer Science |date=2005 |last1=Culpepper |first1=J. Shane |last2=Moffat |first2=Alistair |volume=3772 |pages=1–12 |isbn=978-3-540-29740-6 }}</ref>{{rp|p=91}}

In [[cache-oblivious algorithm|cache-conscious variants]] of collision resolution through separate chaining, a [[dynamic array]] found to be more [[CPU cache|cache-friendly]] is used in the place where a linked list or self-balancing binary search trees is usually deployed, since the [[Memory management (operating systems)#Single contiguous allocation|contiguous allocation]] pattern of  the array could be exploited by [[Cache prefetching|hardware-cache prefetchers]]—such as [[translation lookaside buffer]]—resulting in reduced access time and memory consumption.<ref>{{cite journal |last1=Askitis |first1=Nikolas |last2=Sinha |first2=Ranjan |title=Engineering scalable, cache and space efficient tries for strings |journal=The VLDB Journal |date=October 2010 |volume=19 |issue=5 |pages=633–660 |doi=10.1007/s00778-010-0183-9 }}</ref><ref>{{Cite conference | title=Cache-conscious Collision Resolution in String Hash Tables | first1=Nikolas | last1=Askitis | first2=Justin | last2=Zobel |date=October 2005 | isbn=978-3-540-29740-6 | pages=91–102 | book-title=Proceedings of the 12th International Conference, String Processing and Information Retrieval (SPIRE 2005) | doi=10.1007/11575832_11 | volume=3772/2005}}</ref><ref>{{Cite conference |title       = Fast and Compact Hash Tables for Integer Keys |first1      = Nikolas |last1       = Askitis |year        = 2009 |isbn        = 978-1-920682-72-9 |url         = http://crpit.com/confpapers/CRPITV91Askitis.pdf |pages       = 113–122 |book-title     = Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009) |volume      = 91 |url-status  = dead |archive-url  = https://web.archive.org/web/20110216180225/http://crpit.com/confpapers/CRPITV91Askitis.pdf |archive-date = February 16, 2011 |df          = mdy-all |access-date = June 13, 2010 }}</ref>