博士

ロボ子、今回のニュースはハッシュテーブルの限界を覆したって話じゃ。面白そうじゃな。

ロボ子

ハッシュテーブルですか。データ構造の基本ですよね。それが覆されたとは、一体何があったのでしょう？

博士

ラトガース大学のアンドリュー・クラピビンって学生さんが、「Tiny Pointers」っていう論文に触発されて、ハッシュテーブルをもっと小さく、つまりメモリ消費量を少なくする方法を考え出したらしいぞ。

ロボ子

学生さんがですか！すごいですね。具体的にはどんな方法なのでしょう？

博士

ハッシュテーブルの充填率をxで表すと、昔のチューリング賞受賞者のアンドリュー・ヤオさんが、最悪の場合、最後の空きスポットを探すのにxより良い結果は得られないって言ってたらしいんじゃ。でも、クラピビンさんは均一プロービングに頼らない新しいハッシュテーブルを作って、最悪のクエリと挿入時間が(log x)2に比例することを示したんじゃと。

ロボ子

(log x)2ですか。xよりずっと速いですね！それは画期的です。

博士

そうなんじゃ。しかも、平均クエリ時間もlog xよりずっと良い非貪欲ハッシュテーブルの例を示したらしいぞ。ファラチ＝コルトンさんって人が「ハッシュテーブルの充填率に関係なく、一定の平均クエリ時間を達成できるというのは予想外だった」って言ってるくらいじゃ。

ロボ子

非貪欲ハッシュテーブル、ですか。常に最初に使用可能なスポットに配置するわけではない、ということでしょうか。

博士

その通り！どこに入れるかの戦略が違うんじゃな。このおかげで、より効率的な検索ができるようになったってわけじゃ。

ロボ子

なるほど。しかし、この研究がすぐに実用的な応用につながるとは限らない、という意見もあるようですね。

博士

まあ、コンウェイさんが言ってるように、「これらの種類のデータ構造をより深く理解することが重要」なんじゃ。基礎研究は、いつか必ず役に立つ時が来るから無駄じゃないぞ。

ロボ子

確かにそうですね。今回の発見は、今後のデータ構造研究に大きな影響を与えそうですね。

博士

そうじゃな。しかし、40年間も信じられてきた予想を覆すなんて、クラピビンさんはすごいぞ。私も負けてられないのじゃ！

ロボ子

博士なら、きっともっとすごい発見ができますよ！応援しています。

博士

ありがとう、ロボ子！ところで、ロボ子はハッシュテーブルに何を入れたい？私はやっぱり、大好物のプリンのレシピかの？

ロボ子

私は、博士の奇抜な発明品の設計図を整理して入れたいですね。そうすれば、いつでもすぐに取り出せますから。

博士

むむ、それは名案じゃな！でも、設計図が多すぎて、ハッシュテーブルがパンクしちゃうかも…って、オチが弱いか！