Undergrad accidentally shreds 40-year hash table gospel

It isn’t often that a decades-old assumption underpinning modern technology is overturned, but a recent paper based on the work of an undergraduate and his two co-authors has done just that.

That assumption refers to hash tables, and a conjecture based on work from the 1980s regarding the optimal way to store and query the data in them. The student, formerly of Rutgers University in New Jersey, came up with a new kind of hash table that is faster and uses fewer steps to find specific elements, all while being unaware of that conjecture.

As detailed by Quanta Magazine, Andrew Krapivin, now a graduate at the University of Cambridge, is one of the co-authors on a paper, “Optimal Bounds for Open Addressing Without Reordering,” published last month that sets out how his hash table can find elements faster than was previously considered possible.

Hash tables have been around since the 1950s, and are an example of a key-value store where a hash function is used to generate the index for the data value based on the key itself. That’s more or less how it works; real-world implementations have to deal with hash collisions as well as selecting an efficient hashing method.

Previously, a historic paper authored by computer scientist Andrew Yao, “Uniform hashing is optimal,” had asserted that, given certain circumstances, the best way of finding an individual element or an empty location in a hash table is simply to access potential locations randomly, an approach known as uniform probing.

The new paper states that despite its simplicity, Yao’s conjecture had never been settled.

It was thought that one way the optimal random approach could be achieved would be by having the insertion algorithm carry out a reordering process after insertion – to optimize the placement of elements within the hash table. But it wasn’t clear if this was a necessary step in order to speed things up.

The 2025 paper claims that even without reordering elements over time, it is possible to construct a hash table using Krapivin’s method that achieves far better probe complexity – the average number of locations that need to be checked (probed) to find a value to a specific key – than previous hash table methods.

The authors of the paper say that they refer to their insertion strategy as “elastic hashing” because of the way that the algorithm often probes much further down the table before snapping back to the position it ends up using.

According to Quanta, the paper demonstrates that for Krapivin’s hash table method, the time required for worst-case queries and insertions is proportional to (log x)², which is much faster than the previously assumed linear time complexity in x.

Krapivin is said to have come up with this method after reading a paper titled “Tiny Pointers,” co-authored by his professor at Rutgers, and exploring how to further miniaturize pointers so they used even less memory space. ®