大学院生が、ハッシュテーブルがどれほど高速に動作し得るかをめぐるコンピューター科学で最も長く続いてきた定説の一つを覆すことに貢献し、探索と挿入が多くの研究者の想定よりはるかに高速になり得ることを示した。資料に含まれるQuantaの記事によると、アンドリュー・クラピヴィンは、マルティン・ファラク＝コルトン、ウィリアム・クスマウルとともに、最悪時の照会・挿入時間が、従来の予想を長く支配してきた充填度の尺度xではなく、対数の2乗に比例する新たなハッシュテーブル設計を実証した。

この成果への道のりは、「Tiny Pointers」と題する論文から始まった。クラピヴィンは学生時代にこの論文に出会い、その後、ほとんど副次的なプロジェクトとして、より注意深く取り組むようになった。そこから彼は、使用するメモリーを減らすため、ポインターをさらに小さくしようと試みた。その結果、ポインターの背後にあるデータを整理するより良い方法を探さざるを得なくなり、それがハッシュテーブルへとつながった。そうした試行錯誤の過程で、予想以上に高速に動作する新しいハッシュテーブルを自分が作り出していたことに気付いた。

ハッシュテーブルが徹底的に研究されてきたことを考えれば無理もないが、ファラク＝コルトンは当初、納得しなかった。しかし、クスマウルがそのアイデアを検討すると、反応は懐疑から興奮へと変わった。情報源の記事の表現を借りれば、クラピヴィンが見つけたのは単なる巧妙な仕掛けではなかった。彼は、特定のハッシュテーブルは一様プロービングを上回ることができず、最後に残った空きスロットを探す際の最悪時の探索時間はxに比例せざるを得ないと1985年に主張したアンドリュー・ヤオに関連する、40年来の予想を覆したのである。

新たな結果は、それとは異なる結論を示している。論文で論じられた種類のハッシュテーブルでは、最悪時のコストはxではなく、(log x)^2に比例する。xはテーブルが満杯にどれほど近いかを示し、ほぼ満杯のテーブルこそ研究者が重視する難しいケースであるため、これは劇的な転換だ。論文はさらに踏み込んでいる。xが増えても平均照会時間がまったく増加しない非貪欲型ハッシュテーブルを構築し、数十年にわたって想定されてきた別の限界も覆した。記事の言葉によれば、テーブルが満たされていっても平均値は一定になり得る。

より広い意義は、古くから親しまれているデータ構造にも、なお驚きの余地があったことだ。ハッシュテーブルは単純で効率的かつ広く理解されているため、膨大なソフトウェアの内部で使われている。理論上の限界を改善する成果が、あらゆる実装を一夜にして書き換えるわけではないが、何が可能かを示す地図は変わる。情報源の資料は、この論文が一つだけでなく複数の問いに答え、その過程で、学生のプロジェクトがコンピューター科学の古典的論争に決着をつけることもあると示したことを明確にしている。