大学生が40年間信じられてきたデータサイエンスの定説を覆した

コンピューターサイエンスの世界には、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年以来の壁』は、その存在を知らずに問題へ向き合った一人の若い研究者の自由な発想によって、ついに越えられました。

クラピヴィン氏は現在、イギリスのケンブリッジ大学で大学院生として研究を続けています。

知識は時に、次の発見を遠ざけていた――少し皮肉で、しかし希望に満ちたこの教訓は、私たちが最も身近に使うテクノロジーの奥底から、今あらためて投げかけられているのです。

セクション４：専門家向け補遺

この論文の価値は、「少し速いハッシュテーブルを1本出した」ことではありません。

著者らがやっているのは、並べ替えなしの open addressing の理論地図を、上界と下界の両方から描き直したことです。

論文の導入で立てられている問いは二つで、ひとつは「並べ替えなしで、平均的な探索手数を一様探索の達成する対数オーダーより下げられるか」、もうひとつは「並べ替えなしで、最悪ケースの期待探索手数を一様探索の達成する逆数オーダーより下げられるか」です。

著者らはまず、この二つの問いに同時に「できる」と答える非貪欲な構成――elastic hashing――を与えています。

ここで重要なのは、要素をあとで動かさないまま、しかも最初の空きに即決しないことで、挿入時に試した棚の数と、あとでその要素を取り出すときに試される棚の数を切り離している点です。

論文中でも、先の候補をかなり遠くまで見てから、最終的には手前の適切な位置に“戻る”振る舞いが本質だと説明されています。

その結果、表の中にすでに入っている要素に対する amortized expected probe complexity は定数、worst-case expected probe complexity は対数オーダー、worst-case expected insertion time も対数オーダーまで落ちます。

しかも著者らは、この worst-case expected の対数オーダーが、並べ替えなしの任意のスキーム（greedy か否かを問わず）における下界とちょうど一致することを示し、この意味で Theorem 1 が最適であることまで証明しています。

二つ目が funnel hashing です。

こちらはとくに意味が大きい結果です。

というのも、ヤオの未解決予想が刺さっていたのは、まさに greedy open addressing の側だからです。

ここで一点、誤解されやすいので補足しておくと、Yao が1985年の論文『Uniform Hashing is Optimal』で証明したのは、Ullman が1972年に立てた amortized expected に関する予想の方で、Yao 自身が予想として残したのは、それより一段強い worst-case expected についての下界でした。

今回の論文が覆したのは、この後者――Yao が未解決問題として残した方の予想です。

論文は、greedy のままでも worst-case expected probe complexity を対数の二乗オーダーまで落とせると示します。

これは、長く「最悪ケースの期待探索手数についてはほぼ逆数オーダーが限界ではないか」と見られていた世界に対する、はっきりした反例です。要するにこの論文は、「非貪欲なら逃げ道がある」だけでなく、「greedy の土俵の中でも、思っていたほど悪くはならない」と言っているわけです。

ここが、単なる設計改良ではなく、古典予想の否定として重いところです。

さらに大事なのは、この論文が上界だけの論文ではないことです。elastic hashing 側では、先に述べた通り、並べ替えなし一般の worst-case expected probe complexity に対して対数オーダーの下界を与えています。

funnel hashing 側では、greedy に対して対数の二乗オーダーの matching lower bound を与えています。

加えて、高確率の最悪 probe complexity についても、並べ替えなし一般で対数の二乗に log log n が加わる形の下界を示しています。

ここで特筆すべきは、この最後の下界が greedy に限らず、non-greedy な並べ替えなしスキームにまで及ぶという点です。

つまり funnel hashing の達成した対数の二乗オーダーは、greedy の枠を超えた意味でも本質的な限界の一部を成しているということです。

著者らは「ここまで速くできる」を言ったあとで、「しかもそこが本質的な限界だ」と押さえている。

理論論文としての完成度は、むしろここで決まっています。

ただ当然ながら限界もあります。

まず、amortized probe complexity は表の中に存在する要素に対する量であり、存在しないキーへの negative query と同じ意味ではありません。

negative query について論文が直接きれいに触れているのは greedy 側で、greedy アルゴリズム一般では存在しないキーへの問い合わせ時間が挿入時間と等しくなるため、Theorem 2 の挿入時間に関する保証は、そのまま存在しないキーへの問い合わせ時間に対する保証にも延長できます。

一方で、削除を含む無限時間の設定は別問題で、論文自身も、先行研究で示された下界（この設定での amortized expected probe complexity が δ⁻Ω(1) 以上になる）を引いて、Theorem 1 や Theorem 2 の型の結果は原理的に成立しないと述べています。

ここを落とすと、「ハッシュテーブル一般の最終回答が出た」という誤読が起きやすいので注意が必要です。

最後に、論文の本当の見どころを一文で言えば、ボトルネックは“高負荷そのもの”ではなく、“挿入時に見た候補列と、後の検索コストが直結してしまうこと”だったと示した点にあります（少なくともこのモデルでは、ボトルネックを『高負荷そのもの』だけで語るのでは足りず、挿入時の probe と後の search probe complexity の結びつきが重要だったことを示唆しています）。

著者らは導入部で、uniform probing が抱える coupon-collector bottleneck を、non-greedy な設計でどう迂回するかをかなり意識的に説明しています。

だからこの論文は、「古い予想を壊した話」であると同時に、「open addressing における本当の難所は何か」を言い直した論文でもあります。

そのため重要なのは結果そのものに加えて、reordering の必要性と non-greediness の必要性を切り分けたこと、そして greedy と non-greedy の境界を、定量的なかたちで再定義したことにあるはずです。

元論文

Optimal Bounds for Open Addressing Without Reordering
https://doi.org/10.48550/arXiv.2501.02305

ライター

川勝康弘: ナゾロジー副編集長。 大学で研究生活を送ること10年と少し。 小説家としての活動履歴あり。 専門は生物学ですが、量子力学・社会学・医学・薬学なども担当します。 日々の記事作成は可能な限り、一次資料たる論文を元にするよう心がけています。 夢は最新科学をまとめて小学生用に本にすること。

編集者

ナゾロジー 編集部