Explain the concept of universal hashing in data structures.

Universal hashing refers to a method of creating hash functions that reduces the chance of collision by randomisation.

In more detail, universal hashing is a scheme for choosing hash functions in a way that they are evenly distributed, which means that no particular key is favoured. This is achieved by selecting the hash function at random from a carefully designed class of functions. The main goal of universal hashing is to minimise the probability of a hash collision, which occurs when two different keys hash to the same value.

In a universal hashing system, the hash function used is not fixed. Instead, it is chosen randomly from a set of possible hash functions. This set is designed so that for any given pair of distinct keys, the number of hash functions that will produce the same hash value for the pair is small. This randomness ensures that the distribution of keys is likely to be uniform, reducing the likelihood of collisions.

The concept of universal hashing was introduced to overcome the worst-case scenario in hashing, where all keys map to the same hash value, leading to a time complexity of O(n) for search operations. By ensuring a more evenly distributed set of hash values, universal hashing can help maintain the average-case time complexity of O(1) for search operations.

Universal hashing is particularly useful in situations where the distribution of keys is not known in advance or may change over time. By choosing a new hash function at random whenever the table is resized, universal hashing can adapt to changing key distributions.

In summary, universal hashing is a technique used in data structures to ensure a more uniform distribution of keys and reduce the likelihood of collisions. It does this by selecting the hash function at random from a set of carefully designed functions. This randomness helps to maintain the efficiency of search operations, making universal hashing a valuable tool in many computing applications.