Editing Hash function (section)

== Analysis ==
Worst case results for a hash function can be assessed two ways: theoretical and practical. The theoretical worst case is the probability that all keys map to a single slot.  The practical worst case is the expected longest probe sequence (hash function + collision resolution method).  This analysis considers uniform hashing, that is, any key will map to any particular slot with probability {{math|1/''m''}}, a characteristic of universal hash functions.

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|&alpha;<sup>''k''</sup> / (''e''<sup>&alpha;</sup> ''k''!)}}, where {{math|''&alpha;''}} 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>