Hash tables have been studied and used in computer science since the 1950s. They allow users to search, add, and delete information in large databases, manage passwords, and cache computer memory.

In 1985, Andrew Yao, a computer scientist, theorized that if a table has a certain number of slots, in the worst-case scenario, it would take the same number of steps to find an empty slot.

However, 22-year-old Andrew Krapivin, a graduate student at the University of Cambridge (UK), along with Professor Martin Farach-Colton of New York University and Associate Professor William Kuszmaul of Carnegie Mellon University (USA), discovered a new type of hash table. This discovery proves that even in the worst-case scenario, the number of steps required to find an empty slot is far fewer than the number of slots in the hash table.

The research was published on arXiv, an online repository of scientific papers, in 1/2025.

According to Quantamagazine, most computer scientists have believed Yao's theory to be true for years. Experts in the field consider this a breakthrough.

"Krapivin not only came up with an interesting hash table, but also effectively debunked a 40-year-old theory," Associate Professor Kuszmaul said.

"Hash tables are one of the oldest data structures and remain the most efficient way to store data. However, there are still open questions about how they work, and this paper answers some of them in a surprising way," commented Alex Conway, an expert from Cornell Tech, Cornell University's graduate school.

Andrew Krapivin. Photo: Quantamagazine

Andrew Krapivin. Photo: Quantamagazine

Krapivin, a former student at Rutgers University, USA, discovered the new type of hash table while researching how to save computer memory to speed up information retrieval by reorganizing data.

Initially, Professor Martin Farach-Colton, Krapivin's advisor, was skeptical of this new design because hash tables are one of the most thoroughly studied data structures in computer science. To be certain, he asked Associate Professor William Kuszmaul to double-check.

Thanks to this discovery, in 2023, Krapivin was awarded the Goldwater Scholarship, one of the most prestigious scholarships for students in the USA, to encourage research in STEM fields (Science, Technology, Engineering, and Mathematics). Last year, Krapivin became the first Rutgers University student in 10 years to receive the Churchill Scholarship to study at the University of Cambridge, a top-5 university in the world.

Huyen Trang (according to Quantamagazine)