09-09-2017, 12:35 PM
Hash-based data structures and algorithms are currently an expanding industry on the Internet, especially for applications related to measurement, monitoring and security. Hashtables and related structures, such as Bloom filters and their derivatives, are used billions of times a day and new uses continue to proliferate. In fact, one of the most notable trends over the last five years has been the increasing prevalence of hash-based algorithms and data structures in networks and other areas. At the same time, the field of hashing, which has enjoyed a long and rich history in computer science has also enjoyed something of a theoretical renaissance. It could be said that this burst of activity began with demonstrating the power of multiple options: by providing each element with multiple possible hash locations and storing them in the least-charged loads, one can obtain remarkably balanced loads, obtaining very efficient search schemes. An extension of this idea, the cuckoo hash, also allows elements to move among their multiple options to better avoid collisions, further enhancing memory utilization.