Unveiling the Novel Algorithimic Hash Table O(log² δ⁻¹) to Overcome Decades-old Limitations

A team of undergraduate researchers has proposed a new data structure to improve the open-addressing hash table, which directly stores data in a hash table. This structure can create algorithms that are faster than anticipated by Andrew Yao’s speed limits set for this problem since 1985.

The team consists of Martin Farach-Colton from the University of New York, Andrew Krapivin from Cambridge University, and William Kuszmaul from Carnegie Mellon University. They have proposed two new types of hashing processes: Elastic Hashing and Funnel Hashing. The crucial one being Funnel Hashing, which resiliently handles data retrieval even in the worst-case scenario at O(log² δ⁻¹).

An open-addressing hash table is a data structure that stores data directly in a hash table. When hash collisions occur, the system must find a way to search for empty spaces to store the data, known as probing. This makes the efficiency in searching and inserting data larger than O(1) at its worst-case scenario when the table is nearly full. If the probing process involves continuous scanning for empty slots, the time complexity can go up to O(n) based on the table size. However, Funnel Hashing can reduce the Big-O to a mere log² level, which is significantly lower.

Source – Quanta Magazine

TLDR: Undergraduate researchers propose a new data structure to enhance the open-addressing hash table, introducing Elastic Hashing and the particularly resilient Funnel Hashing, significantly improving search and insertion efficiency.