Editing Binary search (section)

=== Hashing ===
For implementing [[associative arrays]], [[hash table]]s, a data structure that maps keys to [[record (computer science)|records]] using a [[hash function]], are generally faster than binary search on a sorted array of records.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing")}} Most hash table implementations require only [[Amortized analysis|amortized]] constant time on average.{{efn|It is possible to search some hash table implementations in guaranteed constant time.{{Sfn|Knuth|1998|loc=§6.4 ("Hashing"), subsection "History"}}}}<ref>{{cite journal|last1=Dietzfelbinger|first1=Martin|last2=Karlin|first2=Anna|last3=Mehlhorn|first3=Kurt|last4=Meyer auf der Heide|first4=Friedhelm|last5=Rohnert|first5=Hans|last6=Tarjan|first6=Robert E.|author-link2=Anna Karlin|author-link3=Kurt Mehlhorn|author-link6=Robert Tarjan|title=Dynamic perfect hashing: upper and lower bounds|journal=[[SIAM Journal on Computing]]|date=August 1994|volume=23|issue=4|pages=738–761|doi=10.1137/S0097539791194094}}</ref> However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record.<ref>{{cite web|last1=Morin|first1=Pat|title=Hash tables|url=http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://cglab.ca/~morin/teaching/5408/notes/hashing.pdf |archive-date=2022-10-09 |url-status=live|access-date=28 March 2016|page=1}}</ref> Binary search is ideal for such matches, performing them in logarithmic time. Binary search also supports approximate matches. Some operations, like finding the smallest and largest element, can be done efficiently on sorted arrays but not on hash tables.<ref name="pred" />