Editing Hash table (section)

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