40年間の常識を大学生が覆したハッシュテーブル ― DB検索はまだ速くなる？

最近、データベースやRAGについて調べていて、かなり面白い研究に行き着きました。

きっかけは、

「若い研究者がデータベースの検索方法に関する40年来の常識を覆した」

という海外ニュースです。

調べていくと、2025年に大学生の Andrew Krapivin が、ハッシュテーブルに関する40年前の予想を覆す研究を発表していました。

しかも単純に「新しいDBを作った」という話ではありません。

データをどう配置するかを少し変えるだけで、検索・挿入の理論的な限界を改善できる

という話です。

この記事では、専門的な数学をできるだけ省いて、この研究が何を変えたのか、そして将来的にPostgreSQLなどのDBに入ったら何が起きるのかを整理します。

---

1. そもそもハッシュテーブルとは？

ハッシュテーブルは、データを高速に見つけるための非常に基本的なデータ構造です。

例えば、

user_id = 12345