本科生发现了一种新型哈希表颠覆了姚期智 40 年前的猜想

[lavvrence]

Source

Quote:

for this new hash table, the time required for worst-case queries and insertions is proportional to (log x)^2 — far faster than x

即便是满载（负载因子 100%）的一张哈希表，最差也能实现(log x)^2 时间复杂度的查询，比姚期智提出的理论下限 x 要快很多，（不依赖 hash 表内的负载程度）。基于 Tiny Pointers 实现。

这是不是意味着很多编程语言内置的哈希表实现将被重写？