 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
| ||||||||||||||||||
Simple Uniform Hashing Assumption ≠ Uniform Hashing Assumption
editThese are two different assumptions. The simple uniform hashing assumption deals with hash functions that simply map a key to a slot in the table; h(k) = d where 1 ≤ d ≤ table size (m). SUHA says that "each key is equally likely to be hashed to any slot of table, independent of where other keys are hashed." [1] UHA, on the other hand, deals with hash functions that output a sequence of table slots to try to insert the key into; h(k, i) = d for attempt number i. The uniform hashing assumption says that "Each key is equally likely to have any one of the m! permutations as its probe sequence." [2] The source used by linked references is Introduction to Algorithms textbook by Cormen, Leiserson, Rivest, and Stein (CLRS), chapter 11 sections 2 and 3.
24.7.25.79 (talk) 17:52, 14 December 2013 (UTC)
- ^ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec08.pdf
- ^ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec10.pdf