Content deleted Content added
315105 Tags: Reverted Visual edit Mobile edit Mobile web edit |
|||
Line 227:
While [[Donald Knuth|Knuth]] worries about adversarial attack on real time systems,<ref>{{cite book |last=Knuth |first=Donald E. |author-link=Donald Knuth |date=1975 |title=The Art of Computer Programming, Vol. 3, Sorting and Searching |page=540 |publisher=[[Addison-Wesley]] |___location=Reading, MA}}</ref> Gonnet has shown that the probability of such a case is "ridiculously small". His representation was that the probability of {{math|''k''}} of {{math|''n''}} keys mapping to a single slot is {{Math|α<sup>''k''</sup> / (''e''<sup>α</sup> ''k''!)}}, where {{math|''α''}} is the load factor, {{math|''n''/''m''}}.<ref>{{cite tech report |last=Gonnet |first=G. |date=1978 |title=Expected Length of the Longest Probe Sequence in Hash Code Searching |id=CS-RR-78-46 |publisher=[[University of Waterloo]] |___location=Ontario, Canada}}</ref>
==
The term ''hash'' offers a natural analogy with its non-technical meaning (to chop up or make a mess out of something), given how hash functions scramble their input data to derive their output.<ref name="knuth-2000">{{cite book|last1=Knuth|first1=Donald E.|author-link=Donald Knuth|title=The Art of Computer Programming, Vol. 3, Sorting and Searching|date=2000|publisher=Addison-Wesley|___location=Boston [u.a.]|isbn=978-0-201-89685-5|edition=2. ed., 6. printing, newly updated and rev.}}</ref>{{rp|page=514}} In his research for the precise origin of the term, [[Donald Knuth]] notes that, while [[Hans Peter Luhn]] of [[IBM]] appears to have been the first to use the concept of a hash function in a memo dated January 1953, the term itself did not appear in published literature until the late 1960s, in Herbert Hellerman's ''Digital Computer System Principles'', even though it was already widespread jargon by then.<ref name="knuth-2000" />{{rp|pages=547–548}}
| |||