Editing Perfect hash function (section)

==Related constructions==

While well-dimensioned hash tables have amortized average O(1) time (amortized average constant time) for lookups, insertions, and deletion, most hash table algorithms suffer from possible worst-case times that take much longer.
A worst-case O(1) time (constant time even in the worst case) would be better for many applications (including [[network router]] and [[memory cache]]s).<ref name="davis" >
Timothy A. Davis.
[https://www.cs.wm.edu/~tadavis/cs303/ch05sm.pdf "Chapter 5 Hashing"]: subsection "Hash Tables with Worst-Case O(1) Access"
</ref>{{rp|41}}

Few hash table algorithms support worst-case O(1) lookup time (constant lookup time even in the worst case). The few that do include: perfect hashing; [[dynamic perfect hashing]]; [[cuckoo hashing]]; [[hopscotch hashing]]; and [[extendible hashing]].<ref name="davis" />{{rp|42-69}}

A simple alternative to perfect hashing, which also allows dynamic updates, is [[cuckoo hashing]]. This scheme maps keys to two or more locations within a range (unlike perfect hashing which maps each key to a single location) but does so in such a way that the keys can be assigned one-to-one to locations to which they have been mapped. Lookups with this scheme are slower, because multiple locations must be checked, but nevertheless take constant worst-case time.<ref>{{citation
 | last1 = Pagh | first1 = Rasmus | author1-link = Rasmus Pagh
 | last2 = Rodler | first2 = Flemming Friche
 | doi = 10.1016/j.jalgor.2003.12.002
 | issue = 2
 | journal = Journal of Algorithms
 | mr = 2050140
 | pages = 122–144
 | title = Cuckoo hashing
 | volume = 51
 | year = 2004}}.</ref>