コンピューターサイエンスの世界には、1985年にアンドリュー・ヤオ（Andrew Yao）氏が残した一つの予想がありました。
それは「目的のデータを探すとき、その手数には、これ以上減らせない理論的な下限が存在するはずだ」というものでした。
以後40年にわたり、多くの研究者はこれを長く有力な予想として受け止め、計算機科学の議論に深く影響を与えてきました。
多くの人が「これは破れないだろう」と考えていたのです。
しかし、この40年来の予想を真正面から覆す結果が発表されました。
設計を最初に確認したクーズマウル氏は、こう語ったとされています。
「君は単にカッコいい仕組みを作っただけじゃない。40年来の予想を完全に吹き飛ばしたんだ」
さらに驚くべきことに、発見者のクラピヴィン氏自身はその予想の存在すら知らなかったといいます。
知らなかったからこそ彼は「これは破れないはず」という先入観が働かず、誰も試そうとしなかった設計にたどり着いたのでしょう。
今回の成果は、「時に知識が足かせになる」という科学の皮肉を映していると言えるでしょう。
研究内容の詳細はプレプリントサーバーである『arXiv』にて公開されています。
目次
- あなたが毎日使っている「一瞬で探す魔法」
- 『知らなかった』が生んだ革命
- 専門家向け補遺
あなたが毎日使っている「一瞬で探す魔法」
クラピヴィン氏らが改良したのは「ハッシュテーブル」と呼ばれる仕組みです。
聞き慣れない言葉かもしれませんが、実はあなたがスマホを触っている間にも、何度も動いている基礎技術です。
巨大な図書館を想像してみてください。
蔵書は100万冊です。 もし本が適当に並んでいたら、1冊を探すのに丸一日かかってしまいます。
だから現実の図書館は「著者名の頭文字で棚を分ける」といったルールを設け、一瞬で目的の棚にたどり着けるように工夫しています。
コンピューターもまったく同じ問題を抱えています。
検索サービス、SNS、メッセージアプリ、地図アプリ――どれも膨大なデータの中から「今あなたが欲しい情報」を瞬時に取り出さなければなりません。
そのために使われているのがハッシュテーブルです。
仕組みはこうです。
たとえば「田中」という名前を特別な計算式に通すと、「棚番号473」という数字が返ってきます。
取り出すときも同じ計算をすれば、「田中さんは473番にいる」とすぐに分かります。
100万人の中から一人を探すのに、運がよければ棚をたった一つのぞくだけで済みます。
これがハッシュテーブルの魔法であり、現代の多くのデジタルサービスを支える、最も基礎的な仕組みの一つです。
ただし、この魔法には一つだけ弱点があります。
棚が混んでくると遅くなるのです。
1985年、後にコンピューターサイエンス界のノーベル賞とも呼ばれるチューリング賞を受賞することになるヤオ氏が、この混雑問題について一本の論文を発表しました。
タイトルは「一様ハッシングは最適である」です。
その名の通り、彼はある種のハッシュテーブルに関する重要な結果を証明し、さらに論文の流れの中で一つの予想を残しました。
ヤオ予想の主張を、思い切ってかみ砕くとこうなります。
「貪欲な（最初に見つけた空き棚にすぐ物を入れる）従来型のオープンアドレス方式では、棚が混雑してくると検索にかかる時間は必ず増えます。その増え方には『これ以上は下げられない』という床（下限）が存在し、その枠組みの中ではどんな工夫をしても、この床より速くはできないだろう」
この予想は長く強い影響力を持ち、専門家の間でも「これは誰にも崩せないだろう」と半ばあきらめ気味に語られてきました。
そして証明も反証もされないまま、ヤオ予想はコンピューターサイエンスの基礎を縛る『1985年以来の壁』として静かに君臨し続けてきたのです。
『知らなかった』が生んだ革命
しかしその壁は、2025年1月に公開されたたった1本の論文で崩れ落ちることになります。
論文のタイトルは「並べ替えを行わないオープンアドレッシングの最適境界」。
クラピヴィン氏らがアーカイブ（arXiv）に投稿したこの論文は、あまりに鮮やかに壁を崩してみせたため、世界中の研究者を唖然とさせました。
ただ、この論文の凄さを楽しむには、ちょっとだけ準備運動が必要です。
難しい話ではなく、「ハッシュテーブルの速さ」には実は二つの顔があるのだと知っておくだけで十分です。
一つ目の顔は、一番運が悪かったときの速さ。
満室寸前のぎゅうぎゅうの棚に物を突っ込むとき、平均して何回くらい空き探しに失敗するか、という見方です。
もう一つは、全体をならしたときの速さ。
表にずらりと並んだ要素を一つずつ取り出していって、全部の平均を取るとどれくらいで済んでいるか、という見方です。
満員電車でたとえるなら、前者は「一番混む時間帯に駆け込んだときの所要時間」、後者は「一日を通した平均の乗り降り時間」。
この二つは別物で、片方だけ速くてもう片方は遅いということが普通に起きます。
さて、準備運動はこれだけです。
ではいよいよ、クラピヴィン氏らが何をやってのけたのかを見ていきましょう。
実はこの論文、新設計を一つではなく二つ同時に提示しています。
そしてこの二つが、それぞれ違う方向から、ヤオ予想とその周辺の難問を崩していくのです。
一つ目の設計「じょうご型ハッシング（funnel hashing）」。
これがまず信じがたい成果でした。
なにしろこの設計、40年来の暗黙のしきたりだった「貪欲ルール」――つまり「計算で割り当てられた候補を順番に試して、最初に見つけた空きにすぐ物を突っ込む」という素直なやり方――を律儀に守ったまま、運の悪いケースの速さを一気に改善してしまうのです。
どれくらい改善されるかというと、従来は棚の混み具合に正比例して試行回数が増えていたのに対し、じょうご型ではその「対数の二乗」程度にしか増えません。
対数というのは「大きな数をぐっと小さくしてしまう演算」だと思ってもらえれば十分で、たとえば従来なら100万回の試行が必要な最悪ケースが、じょうご型ではほんの数百回で片付いてしまう、というほどの差です。
ヤオが1985年に「貪欲ルールを守っている限り、こんなことは無理だろう」と予想したまさにそのことを、ルールを一文字も破らずにやってのけた――ヤオ予想が正面から覆された瞬間でした。
二つ目の設計「弾性ハッシング（elastic hashing）」。
こちらはさらに大胆です。
なんと40年来の貪欲ルール自体を、あえてぶち破ってしまうのです。
「最初に見つけた空きに即決で突っ込む」という素直な掟をいったん捨て、棚の先々まで一度ざっと下見をしてから、戻ってきてしかるべき場所に要素をそっと置く――そんな、一見すると遠回りに見える戦略を採ります。
ところが、この寄り道が思わぬ効果を生みました。
表の中にすでに入っている要素を取り出すときの平均の試行回数が、棚がどれだけ混んでいようと、ほぼ一定のまま動かなくなるのです。
長年「貪欲ルールを破ったらもっと速くできるかもしれないが、本当にできるのかは誰にも分からない」と言われ続けてきた、もう一つの大きな未解決問題への答えでした。
そしてこの論文の凄さは、ここで終わりません。
クラピヴィン氏らは「これまでより速くできる」と示しただけではなく、同じ論文の中で「これ以上はもう速くできない」という下限まで、数学的に証明してしまったのです。
じょうご型も弾性ハッシングも、「これより速い設計はもう作れない」ことが証明された最適解だった――つまり、40年越しの問題が、上限と下限の両方を同時に埋める形で完全に決着してしまったということです。
この成果は「穴が埋まった」というより、むしろ「扉が閉まった」事件だったと言えるかもしれません。
別々の二つの壁を、同じ一本の論文でほぼ同時にぶち破り、しかもその先に「もうこれ以上はない」という看板まで立ててみせた――これが、世界中の専門家をあれほど驚かせた本当の理由でした。
クラピヴィン氏がこの設計を最初に見せたのは、元指導教官のファラク＝コルトン氏でした。
ところが教授の最初の反応は、半信半疑だったと報じられています。
ハッシュテーブルはすでに何十年も研究され尽くされた分野で、学部生が根本的な改良を加える余地があるとは、とても思えなかったからです。
念のため共同研究者のクーズマウル氏に確認を依頼したところ、返ってきたのがあの「君は単にカッコいい仕組みを作っただけじゃない。40年来の予想を完全に吹き飛ばしたんだ」という一言でした。
取材の中で、クラピヴィン氏はこう語っています。
「僕はヤオ予想のことを知らずにこれをやりました」
知らなかったからこそ、「これは破れないはず」という心理的ブレーキが働かなかったのかもしれません。
もし彼が教科書通りに標準的な道筋をたどって学んでいたなら、一様ランダムに棚を試すという発想から離れること自体を、思いつかなかった可能性もあります。
ヤオが1985年に残した『1985年以来の壁』は、その存在を知らずに問題へ向き合った一人の若い研究者の自由な発想によって、ついに越えられました。
クラピヴィン氏は現在、イギリスのケンブリッジ大学で大学院生として研究を続けています。
知識は時に、次の発見を遠ざけていた――少し皮肉で、しかし希望に満ちたこの教訓は、私たちが最も身近に使うテクノロジーの奥底から、今あらためて投げかけられているのです。
