Finding items in an universal hash table?

Question

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.

Answer 1

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.