約70年前、ハンス・ピーター・ルーンというIBMのエンジニアは、コンピュータサイエンスの流れを静かに変えました。ルーン氏はすでにいくつかの特許を取得しており、その中には布地の糸数を測定できる装置に関する特許や、キッチンにある材料からどのような混合ドリンクを作ることができるかを決定するガイドに関する特許などが含まれます。しかし、1953 年の IBM 社内論文で、彼は情報を保存および取得するための新しい技術、つまり現在ほぼすべての計算システムに組み込まれているハッシュ テーブルを提案しました。

ハッシュ テーブルは、データ構造の主要なクラスです。これらは、大規模なデータベース内の情報にアクセスして変更するための特に便利な方法を提供します。しかし、このテクノロジーには避けられないトレードオフが伴います。

1957で 紙 に発表され IBM 研究開発ジャーナル, W. Wesley Peterson は、ハッシュ テーブルが引き起こす主な技術的課題を次のように特定しました。ハッシュ テーブルは高速である必要があります。つまり、必要な情報をすぐに取得できる必要があります。ただし、メモリ使用量をできるだけ少なくしてコンパクトにする必要もあります。これら 2 つの目的は根本的に矛盾しています。ハッシュ テーブルのメモリが多いほど、データベースへのアクセスと変更をより迅速に行うことができます。また、使用するスペースが少ないハッシュ テーブルでは操作が遅くなります。ピーターソンがこの課題を提示して以来、研究者たちは時間と空間の間の最適なバランスを見つけようと努めてきました。

コンピューター科学者たちは、最適なトレードオフを見つけたことを数学的に証明しました。解決策は次のようなものから生まれました。 ペア 最近の 論文 お互いを補い合ったもの。 「これらの論文は、可能な限り最良の時空のトレードオフに関する長年の未解決の疑問を解決し、非常に驚​​くべき結果をもたらし、今後長年にわたって大きな影響を与えると期待しています」と同氏は述べた。 マイケル・ミッツェンマッハー、ハーバード大学のコンピューター科学者ですが、どちらの研究にも関与していませんでした。

「これは大きな出来事だと間違いなく言えます」と付け加えた ラスムス・パーグ、コペンハーゲン大学のコンピューター科学者。 「多くの人がこの問題に取り組み、時間効率の高い操作を行いながら、スペースをどれだけ圧縮できるかを試してきました。これは私が解決したかった問題です。」

ハッシュを作成する

ハッシュ テーブルは、現在最も古く、最も単純で、最も高速で、最も広く使用されているデータ構造の 1 つです。これらは 3 つの基本的な操作を実行するように設計されています。挿入。データベースに新しい項目を追加します。クエリ。アイテムにアクセスするか、アイテムが存在するかどうかを確認します。そして削除。ハッシュ テーブルは、特定のプログラムが実行されている間のみ存在する一時的なものにすることも、コンピューターのオペレーティング システムの永続的な部分にすることもできます。 Chrome や Safari などの Web ブラウザには、さまざまな種類のデータを追跡することを目的とした複数の組み込みハッシュ テーブルがある場合があります。

ハッシュ テーブル内のエントリは、情報を識別するキーに関連付けられた項目 (情報そのもの) とのペアとして保存されます。キーをハッシュ テーブルのクエリ アルゴリズムに接続すると、アイテムに直接アクセスできます。これはそれほど特別なことではないと思われるかもしれませんが、巨大なデータベースの場合、大幅な時間の節約になります。

非常に単純化した例として、600,000 を超える単語の定義があるオックスフォード英語辞典を考えてみましょう。デジタル版がハッシュ テーブルに依存している場合は、特定の単語をキーとして使用するだけで、定義に直接進むことができます。ハッシュ テーブルがないと、辞書は、最終的に要求された定義に収束するために消去法を使用する、はるかに遅い検索メカニズムに依存する可能性があります。また、ハッシュ テーブルでは一定の時間 (通常はほんの数分の XNUMX 秒) であらゆる単語を検索できますが、他の方法の検索時間は、辞書内の単語の数が増加するにつれて長くなる可能性があります。ハッシュ テーブルには別の利点もあります。辞書を動的に維持できるため、新しい単語の挿入や古い単語の削除が簡単になります。

研究者は、速度を最大化しメモリを最小化するハッシュ テーブルの構築に数十年を費やしてきました。 20 世紀のソリューションは、時間または空間という 2003 つの側面だけで大きな利益をもたらす傾向がありました。そして XNUMX 年に、研究者たちは 示されました 理論的には、時間と空間の両方で効率を大幅に飛躍させることが同時に可能であるということです。ただし、研究者がこの 2 つの間の理想的なバランスを見つけるにはさらに 20 年かかります。

データシャッフル

その目標に向けた最初の大きな一歩は、2022 年に行われました。 主要なコンピュータサイエンスカンファレンス ローマで。そこでチームは、これまでに考えられている時間とスペースの効率の最良の組み合わせを実現できる新機能を備えたハッシュ テーブルを提案しました。この論文 (アルファベット順に記載) の最初の著者はストーニー ブルック大学の Michael Bender であったため、一般にこの論文は Bender et al. と呼ばれます。ハッシュ表。チームは機能するハッシュ テーブルを構築しようとはしませんでしたが、原理的には説明した機能を使用してハッシュ テーブルを構築できることを証明しました。

彼らが考え出したハッシュ テーブルを評価するために、グループはトレードオフ カーブを作成しました。これは、1 つの軸に操作 (挿入または削除) ごとの時間をプロットし、もう 1 つの軸にメモリが占​​めるスペースをプロットしたグラフです。ただし、このグラフは特別な方法で領域を定義します。ハッシュ テーブルの構築方法により、特定の項目セットを格納するために必要な最小限のメモリよりも多くのメモリが必要になります。コンピューター科学者は、実際には無駄ではなく、ある程度必要であるにもかかわらず、この余分なスペースを「無駄なビット」と呼びます。トレードオフ曲線の空間軸は、キーあたりの無駄なビット数を測定します。

トレードオフ曲線を分析することで、研究者は、特定の量のスペースを使用するハッシュ テーブルの可能な最速時間を割り出すことができます。また、質問を裏返して、特定の操作時間内で可能な最小のスペースを割り出すこともできます。通常、一方の変数の小さな変化は、もう一方の変数の小さな変化につながります。 ウィリアム・クスマウル、ハーバード大学の理論コンピューター科学者であり、2022年の論文の共著者です。 「時間を XNUMX 倍にすれば、おそらくキーあたりの無駄なビット数が半分になるでしょう。」

しかし、彼らが設計したハッシュテーブルではそうではありません。 「時間を少し増やすと、キーあたりの無駄なビット数が指数関数的に減少します」と Kuszmaul 氏は言います。トレードオフ曲線は非常に急峻で、文字通りチャートから外れていました。

チームはハッシュ テーブルを 2 つの部分に分けて構築しました。これらには、アイテムが無駄なビットをまったく含まずに保存されるプライマリ データ構造と、クエリ リクエストが探しているアイテムを見つけるのに役立つセカンダリ データ構造がありました。このグループは二次データ構造の概念を発明したわけではありませんが、超効率的なハッシュ テーブルを可能にする重要な発見をしました。構造の全体的なメモリ効率は、一次構造が格納されている項目をどのように配置するかによって決まります。

基本的な考え方は、主要構造内のすべてのアイテムに優先保管場所 (最適な場所、1 番目に最適な場所、1 番目に最適な場所など) があるということです。項目が最適な場所にある場合は、番号 XNUMX が付けられ、その番号は XNUMX 次データ構造に保管されます。クエリに応答して、二次構造は数値 XNUMX だけを提供します。これは、一次構造内のアイテムの正確な位置を示します。

アイテムが 100 番目に良い位置にある場合、二次データ構造は数値 100 を付加します。また、システムはバイナリを使用するため、数値 100 を 1100100 として表します。数値 1100100 を格納するには、1 よりも多くのメモリが必要です。 — 最適な場所にあるアイテムに割り当てられる番号。たとえば XNUMX 万個のアイテムを保管している場合、このような違いは重要になります。

そこでチームは、プライマリ データ構造内の項目をより好ましい場所に継続的に移動すれば、クエリ時間を増やすことなく、セカンダリ構造で消費されるメモリを大幅に削減できることに気づきました。

「この取り組みが行われるまでは、情報を移動させることでデータ構造をさらに圧縮できるとは誰も考えていませんでした」とPagh氏は言います。 「それがベンダー論文の大きな洞察でした。」

著者らは、自分たちの発明が最も効率的なハッシュ テーブルの新たな上限を確立したこと、つまり、それが時間効率と空間効率の両方の観点からこれまでに考案された最高のデータ構造であることを示しました。しかし、他の誰かがさらに良いことをするかもしれないという可能性は残されていました。

必ず成功する

翌年、彼が率いるチームは、 華城裕プリンストン大学のコンピューター科学者は、ベンダーチームのハッシュテーブルを改善しようとしました。 「一生懸命頑張ったのに、できなかった」 周仁飛、北京の清華大学の学生であり、ユウのチームのメンバーです。 「そのとき、私たちは上限が下限でもあるのではないかと疑ったのです。」つまり、達成できる最高の上限です。 「上限が下限と等しい場合、ゲームは終了し、答えは決まります。」どんなに賢くても、これ以上のハッシュ テーブルはありません。

Yu のチームは、第一原理から下限を計算することで、その予感が正しいかどうかを調べる新しい戦略を採用しました。まず、挿入または削除を実行するには、ハッシュ テーブル (実際にはあらゆるデータ構造) がコンピュータのメモリに何度もアクセスする必要があると彼らは推論しました。スペース効率の高いハッシュ テーブルに必要な最小回数を把握できれば、それにアクセスごとに必要な時間 (定数) を掛けて、実行時間の下限を設定できます。

しかし、ハッシュ テーブルについて何も知らなかった場合 (スペース効率が良いということ以外)、研究者はどうやってメモリへのアクセスに必要な最小回数を把握できるでしょうか?彼らは、二者間で情報を伝達するために何ビットが必要かを研究する、通信複雑性理論と呼ばれる一見無関係な分野を使用して、純粋に理論からこの理論を導き出しました。最終的に、チームは成功しました。データ構造が操作ごとにメモリに何回アクセスする必要があるかを把握しました。

これが彼らの重要な成果でした。その後、スペース効率の高いハッシュ テーブルのランタイムの下限を確立することができました。そして、それが Bender のハッシュ テーブルと正確に一致することがわかりました。 「私たちは（最初は）改善できると考えていました」と周氏は語った。 「私たちが間違っていたことが判明した。」つまり、それはピーターソンの問題が最終的に解決されたことを意味しました。

Kuszmaul 氏は、数十年来の疑問に答えることに加えて、Yu の証明の驚くべき点はその一般性であると述べました。 「その下限は、まだ発明されていないものも含め、考えられるすべてのデータ構造に適用されます。」つまり、メモリと速度の点でベンダー ハッシュ テーブルに勝てるデータ ストレージ方法は存在しないということです。

未来へのハッシュ

新しいハッシュ テーブルの前例のない効率にもかかわらず、すぐに構築しようとする人はいないでしょう。ただ構築が複雑すぎます。 「理論上は高速なアルゴリズムでも、実際には必ずしも高速であるとは限りません」と Zhou 氏は言います。

理論家は一定の要因を無視する傾向があるため、理論と実践の間のこのようなギャップが長期間続くことは珍しいことではないとクスマウル氏は述べた。操作の実行にかかる時間は通常、定数で乗算されますが、その正確な値は理論上の観点からは重要ではない可能性があります。 「しかし実際には、定数が本当に重要です」と彼は言いました。 「現実の世界では、係数 10 はゲームの終焉を意味します。」

実際のハッシュ テーブルは、たとえ理論上の理想には遠く及ばないとしても、実質的には改善され続けています。たとえば、次のような新しいハッシュ テーブルが作成されます。 アイスバーグHTベンダー、クスマウルらによって構築されたものは、以前のものよりもはるかに優れています。 Kuszmaul 氏によると、これは現在利用可能な最もスペース効率の高いハッシュ テーブルの 2 倍の速度であり、最速のハッシュ テーブルに比べて使用するスペースは 3 分の 1 です。

ミッツェンマッハー氏は、2023 年の結果がすぐに別の種類の恩恵をもたらすかもしれないと期待している。「新しい下限が得られるたびに、特にいくつかの新しい技術を伴うものには、関連する問題にそれらを使用できるという期待が常にあります。」

また、長年の困難な問題を解決できたという知的な満足感もある、とコンピューター科学者は語った ピョートル・インディク マサチューセッツ工科大学の博士号。 「特定のデータ構造を改善できないことがわかれば、研究の焦点を絞ることができます。」最後に、データ研究者はピーターソンの挑戦から注意をそらし、不足のない理論コンピューターサイエンスの新しい問題に焦点を当てることができます。