Talk:SUHA (computer science)

Latest comment: 10 years ago by 24.7.25.79

Simple Uniform Hashing Assumption ≠ Uniform Hashing Assumption

edit

These 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)Reply