学部生が40年前の仮説を反証、新しいハッシュテーブルを発明

この物語 のオリジナル版はQuanta Magazineに掲載されました。

2021年の秋のある日、ラトガース大学の学部生だったアンドリュー・クラピビンは、人生を変えることになる論文に出会いました。当時、クラピビンは深く考えませんでした。しかし2年後、ついにその論文を読む時間（彼曰く「ただの楽しみ」）を作った時、彼の努力はコンピューターサイエンスで広く使われているツールの見直しへと繋がりました。

論文のタイトル「小さなポインタ」は、コンピューターのメモリ内の情報、つまり要素にユーザーを誘導する矢印のような物体を指していました。クラピビンはすぐに、ポインタをさらに小型化してメモリ消費量を削減する方法を思いつきました。しかし、それを実現するには、ポインタが指し示すデータを整理するより優れた方法が必要でした。

彼はハッシュテーブルと呼ばれるデータ保存の一般的な手法に着目しました。しかし、試行錯誤の過程で、クラピビンは新しい種類のハッシュテーブルを発明したことに気づきました。それは予想以上に高速で、特定の要素を見つけるのにかかる時間とステップ数が少なくて済みました。

「Tiny Pointers」論文の共著者であり、ラトガース大学でクラピビン教授を指導したマーティン・ファラハ＝コルトン氏は、当初クラピビン氏の新設計に懐疑的だった。ハッシュテーブルはコンピュータサイエンス全体の中でも最も徹底的に研究されているデータ構造の一つであり、その進歩はあまりにも素晴らしい話に思えた。しかし念のため、彼はクラピビン氏の頻繁な共同研究者であり、「Tiny Pointers」論文の共著者でもあるカーネギーメロン大学のウィリアム・クズマウル氏に、クラピビン氏の発明品を検証するよう依頼した。クズマウル氏の反応は違った。「ただクールなハッシュテーブルを思いついただけじゃない」と彼はクラピビン氏に言ったのを覚えている。「40年来の仮説を完全に覆したんだぞ！」

クラピビン（現在はケンブリッジ大学の大学院生）、ファラハ・コルトン（現在はニューヨーク大学）、クズマウルは共同で、この新しいハッシュテーブルは実際にこれまで考えられていたよりも速く要素を見つけることができることを2025年1月の論文で実証した。そうすることで、彼らは長い間真実であると信じられていた推測を反証した。

「これは重要な論文です」と、ニューヨーク市コーネル工科大学のアレックス・コンウェイ氏は述べた。「ハッシュテーブルは現存するデータ構造の中で最も古いものの一つであり、今でも最も効率的なデータ保存方法の一つです。」しかし、その仕組みについては未解決の疑問が残っていると彼は述べた。「この論文は、それらの疑問のいくつかに驚くべき形で答えを出しています。」

ハッシュテーブルは、そのシンプルさと使いやすさもあって、コンピューティングの世界で広く普及しています。ハッシュテーブルは、要素の「クエリ」（検索）、要素の削除、空きスロットへの要素の挿入という、まさに3つの操作を実行できるように設計されています。最初のハッシュテーブルは1950年代初頭にまで遡り、それ以来、コンピュータ科学者たちはハッシュテーブルを研究し、活用してきました。研究者たちは、これらの操作の速度限界を解明しようと試みてきました。例えば、新しい検索や挿入はどれくらいの速度で実行できるのでしょうか？

答えは通常、ハッシュ テーブル内の空きスペースを見つけるのにかかる時間によって決まります。これは通常、ハッシュ テーブルがどの程度埋まっているかによって決まります。埋まり具合は、全体的なパーセンテージで表すことができます (このテーブルは 50% 埋まっていて、あのテーブルは 90% 埋まっています)。しかし、研究者ははるかに埋まっているテーブルを扱うことがよくあります。そのため、代わりに、xで表される整数を使用して、ハッシュ テーブルが 100% にどの程度近いかを指定する場合があります。xが 100 の場合、テーブルは 99% 埋まっています。xが 1,000 の場合、テーブルは 99.9% 埋まっています。この埋まり具合の測定値は、クエリや挿入などのアクションの実行にかかる時間を評価するのに便利な方法を提供します。

研究者たちは以前から、特定の一般的なハッシュテーブルにおいて、最悪の挿入（例えば、最後に残った空きスペースにアイテムを入れるなど）に必要な予想時間はxに比例することを知っていた。「ハッシュテーブルが99%埋まっている場合、空きスロットを見つけるには約100個の異なる位置を調べる必要があるのは当然です」とクズマウル氏は述べた。

1985年の論文で、後にAMチューリング賞を受賞したコンピュータ科学者アンドリュー・ヤオは、特定の特性を持つハッシュテーブルにおいて、個々の要素または空き領域を見つける最良の方法は、可能性のある領域をランダムに探索することであると主張しました。これは「ユニフォーム・プロービング」と呼ばれる手法です。彼はまた、最悪のシナリオ、つまり最後に残った空き領域を探す場合、xよりも良い結果を得ることは決してできないと述べました。40年間、ほとんどのコンピュータ科学者はヤオの予想が正しいと仮定していました。

クラピビンは、単にその常識を知らなかったという理由で、従来の常識にとらわれませんでした。「ヤオの予想を知らずにこれをやったんです」と彼は言います。小さなポインタを使った彼の探求は、均一な探索に依存しない新しい種類のハッシュテーブルにつながりました。そして、この新しいハッシュテーブルでは、最悪のケースのクエリと挿入に必要な時間は(log x ) ^{2に比例し、} xよりもはるかに高速でした。この結果はヤオの予想と真っ向から矛盾していました。ファラッハ＝コルトンとクズマウルの協力を得て、クラピビンはヤオが書いたハッシュテーブルの一般的なクラスにおいて、(log x ) ^{2 が最適かつ破られない上限値であることを証明しました。}

「この結果は、このような古典的な問題に取り組んで解決するという点で素晴らしい」とカーネギーメロン大学のガイ・ブレロック氏は語った。

「彼らは（ヤオの仮説を）反証しただけでなく、彼の問いに対する最善の答えも見つけました」とウォータールー大学のセペル・アサディ氏は述べた。「正しい答えがわかるまで、あと40年かかってもおかしくなかったでしょう。」

ヤオの予想を反駁するだけでなく、この論文には、多くの人がさらに驚くべき結果と考えるものも含まれています。それは、少し異なるものの、関連のある状況に関するものです。1985年、ヤオはクエリの最悪ケースの時間だけでなく、考えられるすべてのクエリの平均時間も調べました。彼は、特定の特性を持つハッシュテーブル（「貪欲」と呼ばれるもの、つまり新しい要素を最初に利用可能な場所に配置する必要があるものを含む）では、log xよりも短い平均時間を達成することは決してできないことを証明しました。

ファラッハ＝コルトン、クラピビン、そしてクズマウルは、同じ制限が非貪欲ハッシュテーブルにも適用されるかどうかを検証しようとしました。彼らは反例、つまり平均クエリ時間がlog xよりもはるかに短い非貪欲ハッシュテーブルを提示することで、制限が適用されないことを示しました。実際、この制限はxに全く依存しません。「得られる数値は、ハッシュテーブルの占有量に左右されない定数です」とファラッハ＝コルトンは述べています。ハッシュテーブルの占有量に関係なく、平均クエリ時間が一定になるという事実は、著者自身にとっても全く予想外のことでした。

チームの成果がすぐに応用につながるわけではないかもしれないが、重要なのはそれだけではないとコンウェイ氏は述べた。「こうしたデータ構造をより深く理解することが重要です。今回の結果が、いつ実践でより良い成果につながる何かを生み出すかは分かりません。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得 て転載されました。