40年間の予想が覆される：新しいハッシュテーブルが期待値を上回る

ケンブリッジ大学の大学院生であるクラピビンと、ニューヨーク大学のファラッハ・コルトン、クスマウルは、コンピューターサイエンスにおける長年の定説であるヤオの予想を覆しました。彼らが開発した新しいハッシュテーブルは、最悪の場合の要素検索における時間計算量が(log x)²となり、従来の最適解とされていたxを大きく下回ります。この画期的な研究は、ハッシュテーブル設計における古典的な問題を解決するだけでなく、データストレージの効率を劇的に向上させ、学術界に大きな注目を集めています。