news.volyx.in

Undergraduate shows that searches within hash tables can be much faster (quantamagazine.org)

1304 points by Jhsto · 539 days ago · 584 comments on HN

Article summary

An undergraduate student, Andrew Krapivin, has developed a new kind of hash table that can find elements faster than previously thought possible, disproving a 40-year-old conjecture. The new hash table has a search time proportional to (log x)^2, which is faster than the previously assumed limit of x. This breakthrough has implications for the study of data structures and could potentially lead to improvements in computer science. The discovery was made while Krapivin was exploring ways to miniaturize 'tiny pointers' that direct to stored data.

Main themes

  • Hash tables
  • Data structures
  • Computer science
  • Algorithmic complexity
  • Big-O notation
  • Data storage

What commenters say

  • The concept of O(1) lookup time for hash tables is misleading because it ignores the memory hierarchy and the complexity of hash functions.
  • The new hash table's improved search time is a significant breakthrough, but its practical applications and implementability are still unknown.
  • The article's use of the term 'data science' is incorrect, and the discovery is actually related to data structures, a subfield of computer science.
  • The big-O notation is a useful tool for analyzing algorithmic complexity, but it has limitations and should be considered in the context of specific cost analyses.
  • The discovery of the new hash table's properties is a theoretical result that may not have immediate practical implications, but it advances our understanding of data structures.
  • The assumption that memory operations and comparisons are O(1) is a common simplification in big-O analysis, but it may not always reflect real-world complexity.
  • The article's lack of detail about the improvement and its benchmarking is a limitation, making it difficult to fully understand the significance of the discovery.
  • The distinction between average-case and worst-case analysis is important in understanding the implications of the new hash table's properties.