2026-08-13·無料·論文·9分で読めます

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

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

要点

ハッシュ表はハッシュ関数で置き場所を計算し、完全一致検索を平均 $O(1)$ で行う。
異なる鍵が同じ棚に落ちる衝突は避けられず、性能は負荷率が左右する。
良いハッシュは雪崩効果で似た入力を無関係な棚に飛ばすため、類似検索には向かない。
LSHは似ているほど同じ棚に落ちるハッシュで、角度を衝突確率に翻訳する。
HNSWは多層の近傍グラフを貪欲に渡り歩く方式で、現在のベクトルDBの主流である。

#hash #lsh #hnsw #vector-search #data-structures

対象textタスクbasics

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

一次資料 — この記事の根拠

この解説の公開 2026-08-13

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphsarXiv:1603.09320論文ページ·PDF

巨大な倉庫で1冊を探す

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

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

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

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

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

h(k) = k \bmod m

(1)

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

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

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

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

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

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

FIG 1全件走査 O(n)・二分探索 O(log n)・ハッシュ O(1) の差は、nを増やすと「桁」になる。スライダーでnを動かし、対数表示にも切り替えてみてください

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

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

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

厳密にやるなら、クエリと全ベクトルの距離を計算して最小を選ぶ——つまり倉庫の全件走査に逆戻りです。数億件・数百次元では1クエリごとに待たされます。そこで実務は「厳密な1位」を諦め、高い確率でほぼ1位を当てる近似最近傍探索（ANN: Approximate Nearest Neighbor）を使います。その二大流派が、これから見るLSHとHNSWです。

LSH: わざと「雑な」ハッシュを作る

LSH（Locality-Sensitive Hashing、局所鋭敏ハッシュ）は発想の逆転です。雪崩効果とは正反対に、似ている入力ほど高い確率で同じ棚に落ちるハッシュ関数を意図的に設計します。

コサイン類似度向けの代表例「ランダム超平面法」は拍子抜けするほど単純です。空間にランダムな向きの板（超平面）を1枚立て、ベクトルが板の表側なら1、裏側なら0とする。これがハッシュ1ビットです。板を16枚立てれば16ビット、つまり最大65536個の棚ができます。

似た方向を向く2本のベクトルは、ランダムに立てた板のどちら側かも一致しやすい。これを式にすると、板1枚で値が一致する確率は

\Pr[h(\mathbf{x}) = h(\mathbf{y})] = 1 - \frac{\theta}{\pi}

(2)

読み方: $\theta$ （シータ）は2本のベクトル $\mathbf{x}$ と $\mathbf{y}$ のなす角度です。角度がゼロ（完全に同じ向き）なら一致確率は1、直角なら1/2、正反対なら0。「角度の近さ」がそのまま「同じ棚に落ちる確率」に翻訳される——これがLSHの心臓部です。

FIG 22本のベクトルを回して、なす角と余弦（類似度）の関係を確かめてください。LSHはこの角度を「ランダムな板のどちら側に落ちるかの一致率」に置き換えて、計算せずに近さを当てる

検索時はクエリを同じ板でハッシュし、同じ棚に入っている少数の候補だけを厳密に距離計算します。全件の代わりに棚1つ分で済むわけです。ただしビット数を増やすほど棚が細かくなり、本当の近傍が惜しくも隣の棚に落ちて取りこぼす確率も上がります。そこで実務では、板のセットを変えたハッシュ表を複数持ち、どれかの表で同じ棚に入れば候補にする、という形で取りこぼしを減らします。

コードで書くLSH（numpy擬似コード）

中核は3行です。

import numpy as np

def lsh_codes(X, planes):
    return X @ planes > 0            # (N, k) の True/False = kビットの棚番号

rng = np.random.default_rng(0)
planes = rng.normal(size=(768, 16))  # 768次元空間にランダムな板を16枚
codes = lsh_codes(vectors, planes)   # 全ベクトルを16ビットに要約
query_code = lsh_codes(query[None], planes)
# codes が query_code と一致する行だけを候補にして、厳密に距離計算する

X @ planes は「各ベクトルと各板の法線との内積」で、符号が板のどちら側かを表します。学習は一切不要で、板は乱数で立てるだけ。この割り切りがLSHの美点です。

HNSW: グラフを渡り歩いて近づく

LSHは実装が軽い一方、取りこぼしを減らすには表を増やす必要があり、メモリと精度の両立が難しくなりがちです。現在のベクトルDBの主流は、グラフをたどる方式の HNSW（Hierarchical Navigable Small World）です。

比喩は「飛行機→新幹線→徒歩」の乗り継ぎです。東京の自宅からパリの1軒のパン屋へ行くのに、最初から徒歩では話になりません。まず飛行機で大陸レベルを移動し、鉄道で都市へ、最後は路地を歩く。HNSWはこれをグラフでやります。

各ベクトルを点とし、近い点どうしを辺でつなぐ（各点あたり最大 $M$ 本）
さらに点をまばらに間引いた上層を重ねる。最上層は点がごく少なく、辺は長距離をひとまたぎする

検索は最上層から始めます。今いる点の隣接点のうちクエリに最も近い点へ移る、を改善しなくなるまで繰り返し（貪欲探索）、1つ下の層へ降りてまた繰り返す。最下層に着く頃には、クエリの目と鼻の先にいる、という寸法です。この多層の間引き構造は、順序付きリストの検索を速くする「スキップリスト」の考え方を近傍グラフに移植したもので、Malkov と Yashunin の論文（一次資料参照）で提案されました。

挿入時も同じ探索で「近い点」を見つけて辺を張るだけなので、データを後から追加できます。LSHと違い構築にコストがかかる分、少ない候補数で高い的中率を出せるのが強みです。

現場ではこう使う

この技術に触るのは、RAG・検索・推薦を持つMLエンジニアとバックエンドエンジニアです。埋め込みモデルを選んだ翌日には必ず「どのインデックスで持つか」の判断が来ます。

道具: ライブラリなら FAISS（IndexFlatL2 が厳密全件、IndexHNSWFlat がHNSW）や hnswlib。DBなら pgvector・Qdrant・Milvus など。どれも中身は本記事のHNSW（またはIVF系）で、パラメータ名までほぼ共通
回すツマミ: HNSWなら3つ。M（1点あたりの辺数。メモリと精度の土台）、efConstruction（構築時にどれだけ丁寧に近傍を探すか。構築時間と引き換えにグラフの質が上がる）、efSearch（検索時の探索幅。レイテンシとrecallを日々調整する主ダイヤルはこれ）。pgvectorでは m / ef_construction / hnsw.ef_search という名前で同じものが出てくる
正しい評価手順: 小さめのサンプルで厳密全件検索を回して「本当の上位10件」を作り、ANNがそのうち何件を返せたか（recall@10）を測ってからツマミを決める。速度だけ見てrecallを測らずに本番投入が最も多い事故で、検索が「静かに」劣化するため障害としても検知されない
落とし穴: ①コサイン類似度のつもりで内積用インデックスを作り、ベクトルの正規化を忘れる（長いベクトルが常に上位に来る）②大量の削除・更新を繰り返すとグラフが傷んで精度が落ちるため、定期的な再構築を運用に組み込む ③埋め込みモデルを差し替えたらインデックスは全作り直し。次元も距離空間も変わるため、移行期間は新旧二重持ちになることを設計段階で見込む

まとめ

ハッシュ表は「置き場所を計算で決める」ことで完全一致検索を平均 $O(1)$ にする。衝突は必然で、負荷率の管理が性能の鍵
ただし良いハッシュほど「似ているもの」を遠くへ飛ばす。意味で探すには逆の性質が要る
LSHは「似ているほど同じ棚に落ちる」ハッシュで、角度を衝突確率に翻訳する
HNSWは多層の近傍グラフを貪欲に渡り歩く方式で、現在のベクトルDBの主流
この上に載る応用がRAGの基礎。検索の「速さと的中率」を決めているのは、本記事のツマミたちです