ハッシュと近傍探索 — ベクトル検索の下地

「探す」を速くする2つの発明——完全一致のハッシュ表と、意味の近さで探すLSH・HNSW——を前提知識ゼロから解説。RAGやベクトルDBの裏で動いている近傍探索の仕組みが分かる。

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

巨大な倉庫で1冊を探す

100万冊の本が順番も決めずに積んである倉庫を想像してください。目当ての1冊を探すには、端から1冊ずつ確認するしかありません。運が悪ければ100万回。これが線形走査で、データ量 $n$ に比例する手間、つまり $O(n)$ です。

本をタイトルの五十音順に並べておけば、真ん中を開いて「目当てはこれより前か後か」で半分ずつ絞れます。100万冊でも約20回で届く二分探索、$O(\log n)$ です。

しかし、もっと過激な方法があります。探すのをやめるのです。「このタイトルの本は、計算すると棚番号814になる」——置くときも探すときも同じ計算をすれば、並べる必要も絞り込む必要もなく、一発で棚に手が届きます。この「置き場所を計算で決める」発想がハッシュです。

ハッシュ表: 住所を計算で出す

ハッシュ関数は、どんなデータ（鍵）でも決まった範囲の整数に変換する関数です。最も素朴な形はこうです。

読み方: 鍵 $k$（文字列なら文字コードから作った整数）を、棚の数 $m$ で割った余りを置き場所にする、というだけの式です。余りは必ず $0$ から $m-1$ に収まるので、どんな鍵でも必ずどれかの棚に落ちます。同じ入力からは必ず同じ出力が出るので、しまった場所と探す場所が一致します。

Pythonの辞書（dict）やJavaScriptのオブジェクトの裏側はこの仕組みで、キーから値を平均 $O(1)$——データが何億件あってもほぼ一定時間——で引けます。データ構造の全体地図はデータ構造ツアーで描いたので、この記事はその中の「探す」を深掘りします。

衝突 — 同じ住所に2人が来る

棚が $m$ 個しかないのに鍵の種類は事実上無限なので、違う鍵が同じ棚に落ちることは避けられません（鳩の巣原理）。これがハッシュ衝突です。対策は主に2つあります。

• チェイン法: 各棚をリストにして、同じ棚に来たものを鎖状にぶら下げる。探すときは棚の中だけ線形に見る
• オープンアドレス法: 棚が埋まっていたら、決まった規則で次の棚を試す

どちらでも、性能を決めるのは負荷率（棚数に対する収納数の割合）です。棚がスカスカなら衝突は稀で $O(1)$ のまま。詰め込みすぎると棚の中の鎖が伸びて線形走査に退化します。だから実装は、負荷率が一定（例えば0.75）を超えたら棚を倍に増やして全部置き直します。dictへの挿入がたまにだけ遅いのはこの引っ越しの瞬間です。

ハッシュは「完全一致」しか探せない

ここまでのハッシュ表には、意外な弱点があります。良いハッシュ関数はわざと雪崩効果を持つよう設計されています。入力が1ビットでも違えば出力は無関係な値に飛ぶ、という性質です。衝突をまんべんなく散らすには理想的ですが、裏を返すと "cat" と "cats" はまったく別の棚に置かれます。「似ているものを近くに置く」能力はゼロなのです。

ところが、いまのAIが必要とする検索はまさに「似ているもの探し」です。文章や画像は埋め込みベクトル——意味が近いほど方向が近くなる数百次元の数値の並び——に変換され、「クエリのベクトルに最も近いベクトルを探す」問題、最近傍探索になります。RAGが関連文書を引っ張ってくる裏側もこれです。