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

あなたが毎日使っている「一瞬で探す魔法」

クラピヴィン氏らが改良したのは「ハッシュテーブル」と呼ばれる仕組みです。

聞き慣れない言葉かもしれませんが、実はあなたがスマホを触っている間にも、何度も動いている基礎技術です。

巨大な図書館を想像してみてください。

蔵書は100万冊です。 もし本が適当に並んでいたら、1冊を探すのに丸一日かかってしまいます。

だから現実の図書館は「著者名の頭文字で棚を分ける」といったルールを設け、一瞬で目的の棚にたどり着けるように工夫しています。

コンピューターもまったく同じ問題を抱えています。

検索サービス、SNS、メッセージアプリ、地図アプリ――どれも膨大なデータの中から「今あなたが欲しい情報」を瞬時に取り出さなければなりません。

そのために使われているのがハッシュテーブルです。

仕組みはこうです。

たとえば「田中」という名前を特別な計算式に通すと、「棚番号473」という数字が返ってきます。

取り出すときも同じ計算をすれば、「田中さんは473番にいる」とすぐに分かります。

100万人の中から一人を探すのに、運がよければ棚をたった一つのぞくだけで済みます。

これがハッシュテーブルの魔法であり、現代の多くのデジタルサービスを支える、最も基礎的な仕組みの一つです。

ただし、この魔法には一つだけ弱点があります。

棚が混んでくると遅くなるのです。

1985年、後にコンピューターサイエンス界のノーベル賞とも呼ばれるチューリング賞を受賞することになるヤオ氏が、この混雑問題について一本の論文を発表しました。

タイトルは「一様ハッシングは最適である」です。

その名の通り、彼はある種のハッシュテーブルに関する重要な結果を証明し、さらに論文の流れの中で一つの予想を残しました。

ヤオ予想の主張を、思い切ってかみ砕くとこうなります。

「貪欲な（最初に見つけた空き棚にすぐ物を入れる）従来型のオープンアドレス方式では、棚が混雑してくると検索にかかる時間は必ず増えます。その増え方には『これ以上は下げられない』という床（下限）が存在し、その枠組みの中ではどんな工夫をしても、この床より速くはできないだろう」

この予想は長く強い影響力を持ち、専門家の間でも「これは誰にも崩せないだろう」と半ばあきらめ気味に語られてきました。

そして証明も反証もされないまま、ヤオ予想はコンピューターサイエンスの基礎を縛る『1985年以来の壁』として静かに君臨し続けてきたのです。