40年前の姚其之の予想が、一学部生によって思いがけず覆された！

2000 年以降の学部生であるアンドリュー・クラピビン氏は、従来のどの方法よりも高速にデータを検索できる新しいタイプのハッシュ テーブルを発見しました。

ハッシュ テーブルは、そのシンプルさ、速度、および高性能のため、コンピューター サイエンスとプログラミングで広く使用されていることを知っておくことが重要です。

この新しいハッシュ テーブルの最悪ケースのクエリおよび挿入時間は (log x)² に比例し、これは x がこれまで考えられていたよりもはるかに高速です。

後者はまさに 1985 年に姚其之が提唱した予想です。

さらに、Xiao Ke 氏と彼の同僚は、非貪欲ハッシュ テーブルの平均クエリ時間はハッシュ テーブル x とは無関係に一定値に達する可能性があることを発見しました。これはまったく予想外の発見でした。

ネットユーザーたちは「これはすごい！こういうクレイジーな発見をするのはいつも学生だ」とコメントした。

この発見は、データ構造を理解し、改善するために非常に重要です。

予想外の激変

ハッシュ テーブルは、キーに基づいてメモリ内の保存場所に直接アクセスできるデータ構造です。

つまり、キー値を計算することで、クエリ対象のデータをテーブル内の特定の場所にマッピングし、検索を高速化します。このマッピング関数はハッシュ関数と呼ばれ、レコードを格納する配列はハッシュテーブルと呼ばれます。

もっと簡単に言えば、ハッシュテーブルはたくさんの引き出し（スロット）を持つ大きなファイルキャビネットのようなものです。それぞれの引き出しにはファイル（データ項目）を収納できます。しかし、ファイルキャビネットは大きいため、手動でファイルを探すのは面倒です。そこで、ファイル番号（ハッシュ関数）を使用します。ファイル番号は、どの引き出しにファイルを入れるか、あるいはファイルを探す必要があるときにどの引き出しに行くかを示します。

たとえば、「apple」という名前のファイルを保存し、ファイル番号付けルール (ハッシュ関数) を使用して番号 (たとえば 3) を取得した場合、「apple」ファイルをファイリング キャビネットの 3 番目の引き出しに入れることになります。

2つのファイル（「リンゴ」と「バナナ」など）が同じ番号付け規則（ハッシュ関数）を持つ場合（例えば、両方とも引き出し3に配置されている場合）、衝突が発生します。この問題に対処するため、ハッシュテーブルでは、衝突するすべてのファイルを保存するための「フォルダ」（リンクリスト）を引き出し内に配置したり、ファイルを次の引き出しに移動したりするといった衝突処理戦略を採用しています。

ハッシュ テーブルで使用されるスペースと合計スペースの比率を負荷係数と呼びます。

負荷係数（α）＝格納されている要素数／ハッシュテーブルバケット数＝n／m

負荷係数が小さい場合、ハッシュ テーブルには空のバケットが多くなり、衝突が少なくなるため、検索効率は高くなりますが、メモリが無駄になる可能性があります。

負荷係数が高い場合、ハッシュ テーブルの衝突が増加し、検索パフォーマンスが低下する可能性があります。

1985 年、Yao Qizhi は論文「Uniform Hashing Is Optimal」の中で、特定の特性を持つハッシュ テーブル内の単一の要素または空きスペースを見つける最良の方法は、均一なプロービングであり、最悪の場合の挿入時間は x に比例すると提案しました。

つまり、ハッシュ テーブルが 99% 埋まっている場合、空のスロットを見つけるには 100 個の異なる位置をチェックする必要があります。

ここで、x はハッシュ テーブルが埋められる距離を表します。

x=100 の場合、ハッシュテーブルの使用率は 99% で、負荷率は 0.99 です。x=1000 の場合、ハッシュテーブルの使用率は 99.9% で、負荷率は 0.999 です。

この仮定は 2021 年に疑問視されましたが、それはすべて偶然でした。

当時、ラトガース大学の学部生だったクライン氏は、 「Tiny Pointers」という論文を読みました。

この論文では、コンピュータ メモリ内の情報または要素を指すことができる小さなポインタの概念を紹介します。

論文を読んだ後、Xiao Ke は小さなポインタのメモリ使用量をさらに削減する方法があることに気付きました。

したがって、小さなポインタが指すデータを格納するにはハッシュ テーブルを使用する必要があります。

その過程で、彼ははるかに高速に動作するハッシュ テーブルを発見しました。

つまり、最悪のケースのクエリと挿入に必要な時間は (log x)² に比例し、これは Yao Qizhi の以前の論文で提案された x よりもはるかに高速です。

ハッシュ テーブルは 1950 年代に誕生して以来、徹底的に研究されてきたため、当初、Xiao Ke の指導教官はこの新しい発見に懐疑的でした。

この発見が正しいかどうかを確認するために、アドバイザーのファラック・コルトンはカーネギーメロン大学のウィリアム・クズマウル氏を招き、一緒に検証しました。

その結果、クスモアは、クラックが新しいハッシュ テーブルを発見しただけでなく、 40 年前になされた推測を覆したことを発見しました。

ネットユーザー：「知らないこと」は実は伝統的な道から抜け出すのに役立つ。

なぜシャオ・ケはそんなに簡単に前提を覆すことができるのでしょうか?

彼は姚其之の推測について何も知らなかったため、それは意図せぬ結果だった。

革新を起こす最良の方法は過去のやり方を無視することだと嘆く人もいます。現代人は先人たちの思考パターンに囚われやすいのです。

そして偶然にも、医療専門家が複合台形式を再発見したという話もありました。

もちろん、新しいハッシュ テーブルを提案できるのも、K がそれ自体優れているからこそです。

彼はラトガース大学で数学とコンピュータサイエンスの二重専攻で学士号を取得しました。

彼は、ニューブランズウィックのラトガース大学からケンブリッジ大学院奨学金を受け取ったほぼ10年ぶりの学生です。

その後、彼はケンブリッジ大学に進学し、コンピューターサイエンスと哲学の修士号を取得する予定です。

クライン氏の教師であるファラ・コルトン氏は、ラトガース大学での32年間でクライン氏は最も優秀な学部生だったとさえ語っている。

勉強の他に、チェス、写真撮影、詩作、CPU、GPU、AI プロセッサのいじりを楽しんでいます。

リトルKの兄弟もラトガース大学を卒業していることは特筆に値します。

参考リンク: [1] https://www.quantamagazine.or... [2] https://arxiv.org/pdf/2501.02305