SUHA (computer science)

In computer science, SUHA (Simple Uniform Hashing Assumption) is a basic assumption that facilitates the mathematical analysis of hash tables. The assumption states that a hypothetical hashing function will evenly distribute items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. This assumption generalizes the details of the hash function and allows for certain assumptions about the stochastic system. SUHA is most commonly used as a foundation for mathematical proofs describing the properties and behavior of hash tables in theoretical computer science. Minimizing hashing collisions can be achieved with a uniform hashing function. These functions often rely on the specific input data set and can be quite difficult to implement. Assuming uniform hashing allows hash table analysis to be made without exact knowledge of the input or the hash function used. Certain properties of hash tables can be derived once uniform hashing is assumed. Under the assumption of uniform hashing, given a hash function h, and a hash table of size m, the probability that two non-equal elements will hash to the same slot is Under the assumption of uniform hashing, the load factor and the average chain length of a hash table of size m with n elements will be Under the assumption of uniform hashing, the average time (in big-O notation) to successfully find an element in a hash table using chaining is Under the assumption of uniform hashing, the average time (in big-O notation) to unsuccessfully find an element in a hash table using chaining is A simple example of using SUHA can be seen while observing an arbitrary hash table of size 10 and a data set of 30 unique elements. If chaining is used to deal with collisions, the average chain length of this hash table may be a desirable value. Without any assumptions and with no more additional information about the data or hash function, the chain length cannot be estimated.