Content deleted Content added
Fix cite date error |
mention yet another hash algorithm with constant time even in the worst case |
||
Line 161:
==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
| |||