局所性鋭敏型ハッシュ
このとき d ( p , q ) {\displaystyle d(p,q)} は2点 p , q {\displaystyle p,q} の距離を表す関数であり、 P 1 > P 2 {\displaystyle P_{1}>P_{2}} となるよう設計する。このような族 F {\displaystyle {\mathcal {F}}} は ( R , c R , P 1 , P 2 ) {\displaystyle (R,cR,P_{1},P_{2})} に鋭敏であるという。
これに準ずる定義として、領域 U {\displaystyle U} における類似度関数 φ : U × U → [ 0 , 1 ] {\displaystyle \phi :U\times U\to [0,1]} によるものがある。局所性鋭敏型ハッシュの性質は、ハッシュ関数の集合 H {\displaystyle H} と確率分布 D {\displaystyle D} により与えられる。あるハッシュ関数 h {\displaystyle h} は集合 H {\displaystyle H} から確率分布 D {\displaystyle D} により選ばれるが、 D {\displaystyle D} とは領域 U {\displaystyle U} に存在する2点 a , b {\displaystyle a,b} について、
P r h ∈ H [ h ( a ) = h ( b ) ] = φ ( a , b ) {\displaystyle Pr_{h\in H}[h(a)=h(b)]=\phi (a,b)}
を満たすような確率分布である。