ハッシュテーブル検索の限界を覆した学部生の研究
(quantamagazine.org)- Rutgers大学の学部生だったAndrew Krapivinは Tiny Pointers 論文をきっかけに新しいハッシュテーブルを考案し、従来は限界と見なされていた検索・挿入性能を上回れることを示した
- Krapivin、Martín Farach-Colton、William Kuszmaulは2025年1月の論文で、特定のハッシュテーブル分類に関する Yaoの40年来の予想 を反証した
- 従来の予想では、テーブルがどれほど満杯に近いかを表す x について、最悪の検索・挿入時間は x より良くできないとされていたが、新しい構造は (log x)² に比例する時間を達成した
- 研究チームは、Yaoが扱った人気の高いハッシュテーブル分類において (log x)² がこれ以上下げられない最適境界であることも示し、非貪欲ハッシュテーブルでは平均検索時間が x に依存しない定数にまでできることも示した
- すぐに応用へつながらないとしても、古典的なデータ構造である ハッシュテーブル の性能限界を改めて整理し、実務上の改善可能性を開く理論的基盤となる
Tiny Pointersから始まった新しいハッシュテーブル
- Andrew Krapivinは2021年秋、Rutgers Universityの学部生だった頃に Tiny Pointers 論文に触れ、2年後にこれを詳しく読み込む中で、より小さなポインタを作る方法を思いついた
- ポインタが指すデータをよりうまく整理する必要があったため、一般的なデータ保存方式である ハッシュテーブル が研究対象になった
- 実験の過程でKrapivinは、一様探索（uniform probing）に依存しない新しいハッシュテーブルを作り、特定の要素を見つける時間とステップ数が予想より少ないことを発見した
- Martín Farach-Coltonは当初この設計を疑っていたが、William KuszmaulはKrapivinの構造が単に興味深いハッシュテーブルにとどまらず、40年来の予想 を打ち砕く結果だと判断した
ハッシュテーブルの性能限界という問題
- ハッシュテーブルはデータを保存・アクセスするデータ構造であり、基本的に3つの操作をサポートする
- 要素を 検索（query） する
- 要素を削除する
- 空きスロットに要素を挿入する
- 最初のハッシュテーブルは1950年代初頭にさかのぼり、その後もコンピュータ科学で研究・利用され続けてきた古いデータ構造である
- 検索や挿入の速度限界は通常、ハッシュテーブル内で 空き領域 を見つけるのにかかる時間と結びついている
- ハッシュテーブルがどれほど埋まっているかは全体の比率で表せるが、研究者たちはほぼ満杯の表を扱うときに値 x を使う
- xが100ならテーブルは99%埋まっている
- xが1,000ならテーブルは99.9%埋まっている
- 特定の一般的なハッシュテーブルでは、最後に残った空き領域へ要素を入れるような最悪の挿入期待時間は xに比例 すると知られていた
Yaoの1985年の予想とその反証
- Andrew Yaoは1985年の論文で、特定の性質を持つハッシュテーブルでは、個々の要素や空き領域を見つける最良の方法は、取り得る位置をランダムに調べる 一様探索 だと考えた
- 最悪の場合、つまり最後に残った空き領域を見つける状況では xより良くはできない という予想が、40年にわたりおおむね正しいものとして受け止められてきた
- KrapivinはYaoの予想を知らないままTiny Pointersに関連する探究を進め、一様探索に依存しない新しいハッシュテーブルを作った
- Krapivin、Farach-Colton、Kuszmaulによる 2025年1月の論文 は、この新しいハッシュテーブルで最悪の検索・挿入時間が (log x)² に比例することを示した
- この結果はYaoの予想と真っ向から衝突しており、研究チームはYaoが扱った人気の高いハッシュテーブル分類において (log x)² がこれ以上下げられない最適境界であることも証明した
平均検索時間に関するさらに驚くべき結果
- Yaoは1985年に最悪の検索時間だけでなく、考えられるすべての検索にわたる 平均時間 も扱っていた
- 特定の性質を持つハッシュテーブル、とりわけ新しい要素を最初に可能な位置へ入れなければならない 貪欲（greedy） ハッシュテーブルでは、平均時間は log x より良くできないことを証明していた
- Farach-Colton、Krapivin、Kuszmaulは、同じ限界が非貪欲ハッシュテーブルにも当てはまるかを確かめようとし、反例によってそうではないことを示した
- この反例である非貪欲ハッシュテーブルでは、平均検索時間は log xよりはるかに良く、実際には x にまったく依存しない
- ハッシュテーブルがどれほど埋まっているかに関係なく 定数の平均検索時間 を達成できるという点は、研究チーム自身にとっても予想外の結果だった
古典的データ構造に対する理論的アップデート
- Alex Conwayは、ハッシュテーブルは最も古いデータ構造の一つでありながら、今なおデータを保存する最も効率的な方法の一つだと評価した
- Guy Blellochは、この結果が古典的な問題を扱い、しかも解決している点で美しいと見ている
- Sepehr Assadiは、研究チームがYaoの予想を反証しただけでなく、彼の問いに対する 最良の答え も見つけたと評価した
- Conwayは、この結果がすぐに応用へつながらないとしても、この種のデータ構造をより深く理解すること自体が重要だと考えている
- ハッシュテーブルの理論的限界を改めて整理した今回の結果は、将来の実際の性能改善につながり得る基盤となる
1件のコメント
Hacker Newsのコメント
KrapivinはYaoの予想を知らなかったからこそこのブレークスルーを成し遂げ、Balatroの開発者も既存のデッキビルダーをあまり知らなかったから受賞作を作れたのだと思う
問題に取り組む最良の方法は、過去の似たような試みの大半を知らない、あるいは無視することなのかもしれないと思えてくる
今の世界はあまりにもつながりすぎていて、先人たちの思考の枠組みにはまらない新鮮さを見ることが珍しくなったし、インターネットは素晴らしいものだが、思考を均質化してしまう点は残念
たいていは過去の成功例を無視すると、すでに不毛だった土地にまた種をまくことになる
先行研究を早く読みすぎると既存の考え方に閉じ込められ、まったく読まなければ自分では思いつけなかった重要なことを見落としてしまう
自分のアプローチが既存の最先端に劣っていたとしても、比較を通じてなぜ最先端のアプローチのほうが優れているのかという重要な洞察が得られる
開発者本人の引用によると、Balatroに最も大きな影響を与えたのはLuck be a Landlordで、Northernlionのプレイ動画をいくつか見たあと、非ファンタジー題材のスコアアタック型ローグライクというコンセプトが気に入り、当時作っていたカードゲームをローグライクに変えたという
その時点から意図的にジャンルと距離を置き、自分で失敗しながら設計空間を素朴に探索したかったという
Slay the Spireと比較されることは多いが、Balatroを設計していた時点ではそのゲームをプレイしたことも動画を見たこともなく、ずっと後になって初めて触れたという
https://www.reddit.com/r/Games/comments/1bdtmlg/comment/kup7...
「でも、みんなの助けがなければ絶対にやり遂げられなかったです」と[Milo]は言い返した
「そうかもしれないね」とReasonは厳かに言った。「でもあなたには挑戦する勇気があったし、あなたにできることはたいてい、あなたがやろうとすることにかかっているのよ」
King Azazが言った。「だから君の冒険でとても重要なことの一つは、君が戻ってくるまで言えなかったのだ」
「覚えています」とMiloは熱心に言った。「今、教えてください」
「それは不可能だったのだ」と王はMathemagicianを見ながら言った
「まったく不可能だった」とMathemagicianは王を見ながら言った
「つまり……」と虫が急にくらくらしながら言った
「そう、そのとおり」と二人は一緒に言った。「だがその時に話していたら、君は行かなかったかもしれない……そして君が知ったように、不可能だと知らない限り、本当に多くのことが可能なのだ」
— The Phantom Tollbooth (1961)
私はいろいろ事情があってその授業を落とし、再履修したことで一つの癖に気づいた
毎学期、後半の課題の一つで、30問ほどある問題セットのうち一つを実は未解決問題の形で出し、締め切りの1、2日前に「あ、間違いだった」と言って修正版を送っていた
いつも必ず一度だけそういうことがあったのを見ると、偶然ではなかったのだと思う
monort [0] が動画 [1] のリンクをくれて、とても助かった
動画を一度見た時点でのざっくりした要約だが、名前は Funnel Hashing
アイデアは、配列を指数関数的に小さいサブ配列に分けるというもの。最初の塊は n/m、2つ目は n/(m^2) というように小さくしていき、単一要素まで下る。これを A0、A1 などと呼ぶと、|A0| = n/m、|A1| = n/(m^2) で、合計 k 段階になる
A0 に c 回挿入を試み、失敗したら A1 に c 回試す。それも失敗したら、空きスロットが見つかるまで「ファネル」を下っていく
\delta を空きスロットの割合と呼ぶらしいが、この値がハッシュテーブル作成時に決まるパラメータなのか、動的に更新される値なのかはよく分からない。c = log(1/d), k = log(1/d) とすると、最悪時間計算量は O(log^2(1/d)) になる
この方式は貪欲的ではないため、Yao の結果を回避しているのだと理解した。Yao の結果は貪欲的な挿入・検索ポリシーについて成り立つもので、上の方式はファネルを連鎖的に下っていくので非貪欲的だ
細部には難しいところが多いだろうが、自分が理解したアイデアはこの程度。完全に見当違いなら教えてほしい
Chakraborty、Vinodchandran、Meel の “Distinct Elements in Streams” のアイデア [2] をかなり思い出す
[0] https://news.ycombinator.com/item?id=43007860
[1] https://www.youtube.com/watch?v=ArQNyOU1hyE
[2] https://arxiv.org/pdf/2301.10191
Funnel Hashing は「貪欲的」で、貪欲的ハッシュメカニズムに関する Yao の予想を破っている
Elastic Hashing は「非貪欲的」で、貪欲的アルゴリズムよりも良い償却時間を提供する
記事が間違っているのか、論文の理解が間違っているのか分からないが、記事の筆者が分かっていない点を指摘しているのか気になる
動画の14:41あたりの「いくつかのキーを捕まえるための特別な最終段階」に関係しているようだが、それも固定サイズでなければならないなら満杯になり得る。その場合はどうすればいいのだろう？
[露骨な宣伝]: ハッシュテーブルに興味があるなら Dandelion Hashtable [0] も見る価値がある
私たちの次世代データベースで使っていて、HPDC'24 で発表され、現在実運用ベースで最速のインメモリハッシュテーブルだ
制限付きキャッシュラインチェイニングでクローズドアドレッシングを改善し、一般的なサーバーで毎秒10億件以上のインメモリリクエストを処理する
[0] https://dandelion-datastore.com/#dlht
発明者の発表: https://www.youtube.com/watch?v=ArQNyOU1hyE
制約にぶつかり、リソースが不足しているときにやる リソース管理の小技 の一つに見える
優先度ごとに分けるのはリソース配分ではよくあるアプローチで、これはその変種だ
現場で人々がやってきた他の「塹壕の中の小技」のうち、発明者本人も大したことだとは思っていなかったのに、広く受け入れられているものを覆すようなものがどれだけあるのか気になる。「配達するものが多いとき、たいてい最速ルートを描く賢い方法を見つけたんだけど……」というような話だ
もちろん、それを見抜いて形式化し、作業し、論文として出すのは大きな努力だ。その功績を貶めるつもりはない
論文には単に 動画発表 が含まれていてほしい
ただ、このアプローチも補助配列を通じてメモリを追加で割り当てるのに、単に 過剰割り当て してキー衝突の可能性を下げ、最悪ケースもましにするよりどう優れているのかは、少し不思議に感じる
論文 [1] をざっと見ると、核心的な違いは、ハッシュテーブルの挿入アルゴリズムが最初に見つけた空きスロットを貪欲的に埋めるのではなく、それより先まで探索する点にあるようだ
これを賢い探索順序と組み合わせ、テーブルが非常に埋まっている状況でも空きスロットを効率よく見つけられることを証明している
つまり、ハッシュテーブルがあまり埋まっていないときの挿入は遅くなるが、最後に残った数個の空きスロットがどこにあるか分からないまま探索する最悪の状況を避ける
[1]: https://arxiv.org/pdf/2501.02305
興味深い理論的結果だが、実際には必要より大きなテーブルを割り当てる現在の「コツ」のほうが良い解法だろうと予想する
たとえば Rust の hashbrown は意図的にテーブルの 1/8、つまり 12.5% を空けており、メモリは少し多く使うが、挿入と検索を高い確率で非常に高速にしている
この方式は、テーブルがあまり埋まっていないときでも平均探索位置数を増やす
それでもこの戦略の中では、最初に見た空きスロットに項目を配置する
「スロットを飛ばす」ことは、ハッシュ順序で前方にジャンプすることに関係している
‘Tiny pointers’ の簡単な実装を持っている人はいる？ 私の頭は、証明より先に コードや疑似コード を見るほうを好む
すばらしい。こういう形でテーブルをコンテナ化する方法があるのか、ずっと気になっていた。
通常のテーブルは、何でも詰め込んだばら積み船のようなもの。コンテナ船のようにもっと整理できれば、はるかに多くのものをより効率よく載せ、より速く降ろせるようにも思える。
テーブルの行を文字列や JSON のようなものに変換し、その変数に base16 を適用すれば、そのデータの base16 文字列になる。
ハッシュテーブルを作って、その base16 文字列に対するキー値を設定すれば、データを入れたコンテナができる。
あとは 16 進文字列をデコードするだけで、base32 データが得られる。
ハッシュテーブルの理論的性質は、いつも魔法に近いほど印象的だったし、今回の結果はそれをさらに拡張するものだ。
奇妙に感じていたのは、直感的にはデータを保存する最も効率的な方法に見えるツリーより、ハッシュテーブルがどうしてそこまでずっと優れ得るのか、という点だった。
気づいたのは、ハッシュテーブル理論は固定サイズのオブジェクト集合を扱っているということだ。この固定された集合に対してハッシュ関数を作り、それをベクターのインデックスのように使って、事前に割り当てたベクターに保存する。だから挿入、削除、参照を O(1) に近くできる処方箋が出てくる。一方で各種ツリー構造は、特定のサイズを仮定しない。
問題は、サイズをあらかじめ決める必要があり、ベクターがほぼ埋まると挿入などの処理が遅くなり得ることだ。
記事をざっと見る限り、今回の結果はその遅くなる部分を解決するもののようで、ほぼ満杯のテーブルにも高速な挿入を可能にする。
興味深く巧妙だが、実用上の大きな進歩ではなさそうだ。実戦では、テーブルを賢く埋める方法を考えるより、想定サイズを大きくすればよいと思う。
自分の理解が合っているか確認したくて書いているので、間違っていたら直してほしい。
リサイズが発生する挿入では、テーブルサイズに線形な、はるかに大きい時間がかかるが、その時間はそれまでに行われたすべての挿入に償却される。
テーブルが詰まり始めるたびに十分大きく拡張すれば、発生頻度はだんだん下がるので、平均的には依然として定数時間になる。
関数型の世界では、依然としてツリーのほうが適している可能性が高い。
論文を完全に理解する時間はなかったが、この方式で挿入が一貫して速いと主張している。全体容量の 75% までは理解できるが、すべての行が 75% に達したときに別のモードがあるのかは分からない。
参照も速いと主張しているが、参照がどう動くのか、なぜ速いのかまでは十分に読めていない。
ほぼ満杯のハッシュテーブルでもなお動くなら、本当にありがたい場面は多い。プログラム実行中に常にサイズ変更できるわけではないし、環境によってはメモリが非常に重要だ。
それでも実装を見て、自分で触ってみたい。一般的なケースでこれに「それだけの価値」があるのかは確信が持てない。
キャッシュ効率も良くない可能性が高い。ほとんどのハッシュテーブルはそうだが、かなり埋まったテーブルで線形探索で読む場合だけは例外的に、メモリ上で連続して取り出して確認できる。
性能面で価値があるのかはまだ明確ではないが、興味深い新しいアイデアなので、完全に理解してみたい。
「この新しいハッシュテーブルでは、最悪ケースのクエリと挿入に必要な時間は (log x)2 に比例し、x よりはるかに速い」としながらも、「チームの結果が即時の応用につながるとは限らない」としている部分が理解できない。
なぜ即時の応用につながらないのだろうか。実際のユースケース分析によって、純粋に数学的なアプローチよりハッシュ実装をうまく調整できる状況だ、という意味なのか？
速度向上を見るには、データセットが非現実的なほど大きくなければならない場合がある。
そうすると x が 4 より大きくならないので、O(x) を O((log x)^2) に改善しても、x がそれほど小さいと意味がない。
メモリ制約のある一部の特殊なアプリケーションでは x をもっと大きくするだろうが、個人的にはそういうケースに出会ったことがない。
非常に高い負荷率、たとえば 90% 超が必要なときはいつもカッコーハッシュで十分だったし、70〜80% 以下では線形探索が非常に速く、十分に優れていた。
新しい結果には、「良いケース」の挿入が遅くなるコストもある。
論文には、実務に影響しそうな内容は見当たらない。
この結果は、ハッシュテーブルがほぼ満杯の場合にだけ重要に見える。
それならテーブルサイズを 10% 大きく取るか、リサイズ可能ならもっと早めにリサイズすればいいのでは？
ハッシュ衝突の可能性が高くなりすぎると、自分でサイズを調整する。
テーブルが詰まりすぎたら、単にメモリを 2 倍または一定倍率で追加確保し、既存の項目をコピーする。
ほとんどの非線形探索テーブル、たとえばカッコーハッシュは、RAM がまったく「ランダム」ではないという事実のせいで損をする。
この実装があるGitHub リポジトリを知っている人はいる？