Menu
If items are organized randomly, how does the table know where to start looking?
In a non-random table items are organized according to some characteristic. (i.e. name). So if the table needs to look up some arbitrary information about "John", it can start looking in the 'J' bucket.
In a universal hash table though, items are arranged randomly. There's no defining characteristic. Therefore to find some arbitrary info about "John", wouldn't the table have to look through every bucket?
Isn't that a huge waste of time? It's like looking through every cabinet in your house to find a spoon.
679
Whenever an element is to be searched, compute the hash code of the key passed and locate the element using that hash code as index in the array. Use linear probing to get the element ahead if the element is not found at the computed hash code.
A set H of hash functions is called a universal hash function family if the procedure “choose h ∈ H at random” is universal. (Here the key is identifying the set of functions with the uniform distribution over the set.)
In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below).
A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.
While the previous answers are essentially correct, they don't directly address the random part of a universal hashing algorithm. Universal hashing algorithms do not use randomness when calculating a hash for a key. Random numbers are only used during the initialization of the hash table to choose a hash function from a family of hash functions. This prevents an adversary with access to the details of the hash function from devising a worst case set of keys.
In other words, during the lifetime of the hash table, the bucket for a given key is consistent. However, a different instance (such as next time the program runs) may place that same key in a different bucket.
114
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
