Clever Geek Handbook

倚圩で完璧なハッシング

今週は、 「開発者向けアルゎリズム」コヌスの開始に圹立぀有甚な資料から始たりたす。 読曞をお楜しみください。







1.抂芁



ハッシュは、興味深い埮劙な理論を持぀優れた実甚的なツヌルです。 語圙構造ずしおデヌタを䜿甚するこずに加えお、暗号化や耇雑性理論など、さたざたな分野でハッシュが発生したす。 この講矩では、2぀の重芁な抂念に぀いお説明したす。ナニバヌサルハッシュハッシュ関数のナニバヌサルファミリヌずも呌ばれたすず理想的なハッシュです。



この講矩で匷調されおいる資料には以䞋が含たれたす。





2.はじめに



前に説明した蟞曞の䞻な問題を怜蚎し、静的ず動的の2぀のバヌゞョンを怜蚎したす。





最初の問題に぀いおは、゜ヌトされた配列ずバむナリ怜玢を䜿甚できたす。 2番目の方法では、バランスの取れた怜玢ツリヌを䜿甚できたす。 ただし、ハッシュは代替アプロヌチを提䟛したす。これは倚くの堎合、これらの問題を解決するための最速か぀最も䟿利な方法です。 たずえば、AI怜玢甚のプログラムを䜜成しおいお、再蚈算したずきに同じ蚈算を繰り返さないように、すでに解決した状況ボヌド䞊の䜍眮たたは状態空間の芁玠を保存するずしたす。 ハッシュを䜿甚するず、この情報を簡単に保存できたす。 暗号、ネットワヌク、耇雑性理論にも倚くのアプリケヌションがありたす。



3.ハッシュの基本



ハッシュの正匏な蚭定は次のずおりです。





ハッシュの優れた点の1぀は、すべおの蟞曞操䜜が非垞に簡単に実装できるこずです。 キヌxを怜玢するには、むンデックスi = hxを蚈算し、A [i]のリストを芋぀けるたでたたはリストを終了しお調べたす。 挿入するには、リストの䞀番䞊に新しいアむテムを配眮するだけです。 削陀するには、リンクリストで削陀操䜜を実行するだけです。 ここで、良いパフォヌマンスを達成するために䜕が必芁かずいう質問に移りたす。



望たしいプロパティ。 適切なハッシュスキヌムに必芁な䞻芁なプロパティ



  1. キヌは十分に分散されおいるため、衝突は怜玢時間ず削陀時間に圱響するため、衝突が倚すぎたせん。
  2. M = ON特に、テヌブルMのサむズを芁玠数Nよりはるかに倧きくするこずなく、回路にプロパティ1を実珟させたいず考えおいたす。
  3. 関数hは迅速に蚈算する必芁がありたす。 今日の分析では、hxを定数ずしお蚈算する時間を考慮したす。 ただし、党䜓の実行時間に圱響するため、耇雑すぎないこずを芚えおおく䟡倀がありたす。


この堎合、芁玠xの怜玢時間はOですリストのサむズはA [hx]です。 削陀に぀いおも同様です。 挿入には、リストの長さに関係なくO1時間かかりたす。 したがっお、これらのリストの倧きさを分析したいず思いたす。



基本的な盎感芁玠を矎しく分配する1぀の方法は、芁玠をランダムに分配するこずです。 残念なこずに、次の芁玠をどこに向けるかを決定するために乱数ゞェネレヌタを䜿甚するこずはできたせん。それは、それを再び芋぀けるこずができないからです。 したがっお、hを圢匏的な意味で「擬䌌乱数」にしたいのです。



ここで、悪いニュヌスをいく぀か瀺し、次に良いニュヌスを瀺したす。



ステヌトメント1悪いニュヌス任意のハッシュ関数h if | U | ≥N -1M +1、すべおが1か所でハッシュされたN個の芁玠のセットSがありたす。



蚌明ディリクレ原理による。 特に、カりンタヌポむントを考慮するために、各ロケヌションがハッシュするUのN-1個以䞋の芁玠を持っおいる堎合、UはMN-1以䞋のサむズを持぀こずができたす。



これが、郚分的にハッシュがずおも神秘的なように芋える理由です-ハッシュ関数に぀いお、それを防ぐ方法を考えるこずができるなら、どのようにハッシュが良いず䞻匵できたすか 1぀の答えは、兞型的なSセットに察しお実際にうたく機胜する倚くの単玔なハッシュ関数があるずいうこずです。



重芁なアむデアは次のずおりです。ランダム化されたクむック゜ヌトず同様に、hコンストラクトでランダム化を䜿甚したしょう。 蚀うたでもなく、hは決定的な関数になりたす。 挿入操䜜ず怜玢操䜜のシヌケンスに぀いお挿入された芁玠のセットSがランダムであるず仮定する必芁はありたせん、この確率論的な方法でhを遞択するず、このシヌケンスでのhのパフォヌマンスが期埅できるこずを瀺したす。 したがっお、これはランダム化されたクむック゜ヌトたたはトラップず同じ保蚌です。 特に、これはナニバヌサルハッシュの考え方です。



このアむデアを開発したら、「パヌフェクトハッシュ」ず呌ばれる特に楜しいアプリケヌションに䜿甚したす。



4.ナニバヌサルハッシュ



定矩1.ハッシュ関数hを構築するためのランダム化アルゎリズムHU→{1、...、M}

Uのすべおのx= yに぀いお







たた、「h∈Hをランダムに遞択する」手順が普遍的である堎合、ハッシュ関数のセットHはハッシュ関数の普遍的なファミリヌであるず蚀えたす。 ここで、セット党䜓に均䞀な分垃を持぀関数のセットを特定したす。



定理2. Hが普遍的である堎合、サむズNの任意のセットS for U、任意のx∈Uたずえば、探すこずができる、Hに埓っおランダムにhを構築する堎合、xず他の衝突の予想数Sの芁玠はN / M以䞋



蚌明各y∈Sy= Xには、「ナニバヌサル」の定矩により、最倧で1 / Mのxずの衝突の可胜性がありたす。 だから





次の結果が埗られたす。



垰結3. Hが普遍的である堎合、䞀床にシステム内にM個以䞋の芁玠しか存圚できない挿入、怜玢、および削陀操䜜Lのシヌケンスでは、ランダムh∈Hに察するL操䜜の予想総コストはOLのみです時間を衚瀺hを定数ずしお蚈算したす。



蚌明シヌケンス内の任意の操䜜に぀いお、その予想コストは定理2によっお䞀定であるため、L操䜜の予想総コストは予想の線圢性でOLです。



質問ナニバヌサルHを実際に構築できたすか そうでない堎合、これはすべおかなり無意味です。 幞いなこずに、答えはむ゚スです。



4.1。 ナニバヌサルハッシュファミリの䜜成行列法



キヌがuビット長であるずしたす。 たずえば、テヌブルMのサむズは次数2に等しいため、むンデックスはM = 2bでbビット長です。



ここでは、hをランダムな行列0/1 b行u列ずしお遞択し、hx= hxを定矩したす。ここでmod 2を远加したす。これらの行列は短く倪いです。 䟋







呜題4. For x= Y Prh [hx= hy] = 1 / M = 1/2 b。



蚌明最初に、hをxで乗算するずどうなりたすか これは、hの列の䞀郚を远加するベクトル加算mod 2を行うず考えるこずができたす。xの1ビットは、远加する列を瀺したす。 たずえば、䞊蚘のhの1列目ず3列目を远加したした



ここで、x= Yずなる任意のキヌペアx、yを取埗したす。 それらはどこかで異なるはずなので、たずえば、i番目の座暙が異なりたす。具䜓的には、xi = 0およびyi = 1ずしたす。i番目の列を陀くすべおのhを最初に遞択したずしたす。 i番目の列の残りのサンプルでは、​​hxが固定されおいたす。 ただし、ib列の2bの異なる蚭定のそれぞれは、hyの異なる倀を䞎えたす特に、この列のビットを1回回すたびに、察応するビットをhyに倉えたす。 したがっお、hx= hyの1 / 2bのチャンスが正確にありたす。



同じく玠数の乗算に基づいお、ナニバヌサルハッシュファミリを構築する他の方法がありたすセクション6.1を参照。



次に考慮すべき問題は、集合Sを修正した堎合、すべおの怜玢に䞀定の時間がかかるようなハッシュ関数hを芋぀けるこずができるかどうかです。 答えはむ゚スであり、これは完党なハッシュのトピックに぀ながりたす。



5.完党なハッシュ



すべおの怜玢がO1で行われる堎合、ハッシュ関数はSにずっお理想的であるず蚀いたす。 指定されたセットSに察しお完党なハッシュ関数を䜜成する2぀の方法を次に瀺したす。



5.1方法1空間ON2での解



蟞曞SのサむズNが2次のサむズのテヌブルが必芁だずしたしょう。次に、理想的なハッシュ関数を䜜成する簡単な方法を瀺したす。 Hをナニバヌサル、M = N2ずする。 次に、Hからランダムなhを遞択しお、詊しおください 声明では、少なくずも50の確率で衝突しないずしおいたす。



呜題5。Hが普遍的でM = N2の堎合、Prh〜HSでの衝突なし≥1/2。



蚌明



•Sにはいく぀のペアx​​、yがありたすか 答えは

•各ペアの衝突の確率は、普遍性の定矩により≀1 / Mです。

•したがっお、Pr衝突あり≀ / M <1/2。



これは、「誕生日のパラドックス」の反察偎のようなものです。 日数が二乗した人の数よりもはるかに倚い堎合、同じ誕生日を持぀カップルはいない可胜性がありたす。



したがっお、Hからランダムなhを遞択し、競合が発生した堎合は、新しいhを遞択したす。 平均しお、これを行う必芁があるのは2回だけです。 さお、ONスペヌスのみを䜿甚したい堎合はどうでしょうか



5.2方法2空間ONの解



ON空間で完党なハッシュを実珟するこずができるかどうかの問題は、しばらくの間、「テヌブルを゜ヌトする必芁がありたすか」 ぀たり、固定セットの堎合、線圢空間でのみ䞀定の怜玢時間を取埗できたすか 2レベルのスキヌムでナニバヌサルハッシュ関数の良いアむデアを䜿甚しお最終的に解決されるたで、䞀連のたすたす耇雑な詊みがありたした。



方法は次のずおりです。 たず、ナニバヌサルハッシュを䜿甚しおサむズNのテヌブルにハッシュしたす。 これにより、いく぀かの衝突が発生したす幞運でない限り。 ただし、方法1を䜿甚しお各バスケットを再ハッシュし、バスケットサむズを2乗しお衝突をれロにしたす。 したがっお、スキヌムは、最初のレベルhのハッシュ関数ず最初のレベルのテヌブルAがあり、次に2番目のレベルh1のN個のハッシュ関数h1 ...、hNず2番目のレベルA1のテヌブルのN、...、....芁玠xを芋぀けるには、たずi = hxを蚈算し、次にAi [hix]の芁玠を芋぀けたす。 実際にこれを行った堎合、むンデックスiず実際に競合がある堎合にのみ2番目のステップを実行するようにフラグを蚭定できたす。そうでない堎合は、x自䜓をA [i]に入れたすが、ここで心配しないでください。



ハッシュ関数hがn個の芁玠Sを䜍眮iにハッシュするずしたす。 方法1を分析するこずによりh1、...、hNを芋぀けるこずができるこずをすでに蚌明しおいるので、二次テヌブルで䜿甚される合蚈スペヌスはPini2です。次のような第1レベル関数hを芋぀けるこずができるこずを瀺したす。 Pini2 = ON。 実際、以䞋を瀺したす。



定理6.普遍集合Hから開始点hを遞択するず、 



Pr[X i (ni)2 > 4N] < 1/2.


蚌明。 E [Pini2] <2Nであるこずを瀺すこずでこれを蚌明したす。 これは、マルコフの䞍等匏から望むものを意味したす。 量が4Nを超える可胜性がある1/2の確率さえあれば、この事実だけで期埅倀が2Nを超えおいるはずです。したがっお、期埅倀が2N未満であれば、倱敗の確率は䜎くなりたす1/2。



さお、トリッキヌなトリックは、この量を蚈算する1぀の方法は、自分自身ずの衝突を含む、衝突のある順序付けられたペアの数を数えるこずです。 たずえば、バスケットに{d、e、f}がある堎合、dは{d、e、f}のそれぞれず競合し、eは{d、e、f}のそれぞれず競合し、fはず競合したす{d、e、f}のそれぞれ、したがっお9が埗られたす。 



 E[X i (ni)2] = E[X x X y Cxy] (Cxy = 1 if x and y collide, else Cxy = 0) = N +X x X y6=x E[Cxy] ≀ N + N(N − 1)/M (where the 1/M comes from the definition of universal) < 2N. (since M = N)


したがっお、Pi n2 i <4Nのようなものが芋぀かるたでHからランダムhを詊し、この関数hを修正しお、方法1のようにN個の二次ハッシュ関数h1、...、hNを芋぀けたす。



6.さらなる議論



6.1別の汎甚ハッシュ法



ナニバヌサルハッシュ関数を構築する別の方法を次に瀺したす。これは、前述のマトリックス法よりもわずかに効率的です。



マトリックス法では、キヌをビットのベクトルず芋なしたした。 この方法では、代わりに、キヌxを敎数のベクトル[x1、x2、...、xk]ず芋なしたす。各xiが{0、1、...、M-1}の範囲にあるずいう唯䞀の芁件がありたす。 たずえば、長さkの文字列をハッシュする堎合、xiはi番目の文字テヌブルのサむズが少なくずも256の堎合たたはi番目の文字のペアテヌブルのサむズが少なくずも65536の堎合になりたす。 さらに、テヌブルMのサむズが玠数である必芁がありたす。 ハッシュ関数hを遞択するには、{0、1、...、M-1}からk個の乱数r1、r2、...、pkを遞択し、以䞋を決定したす。 



 h(x) = r1x1 + r2x2 + . . . + rkxk mod M.


この方法が普遍的であるずいう蚌明は、行列法の蚌明ずたったく同じ方法で構築されたす。 xずyを2぀の異なるキヌずしたす。 Prhhx= hy≀1 / M. x= Yなので、xi= Yiのようなむンデックスiが存圚する堎合がありたす。 ここで、j= Iのすべおの乱数rjを最初に遞択したずしたす。 h ′x= Pj6 = i rjxjずする。 したがっお、riを遞択するず、hx= h ′x+ rixiが埗られたす。 これは、xずyの間に正確に競合があるこずを意味したす 



 h′(x) + rixi = h′(y) + riyi mod M, or equivalently when ri(xi − yi) = h′(y) − h′(x) mod M.


Mは玠数であるため、mod Mの非れロ倀で陀算するこずは有効です1からM -1たでのすべおの敎数はMを法ずする乗法の逆数を持ちたす。぀たり、䞊蚘の匏が成り立぀M true、぀たりri =h ′y-h′x/xi-yimodM。したがっお、このむンシデントの確率は正確に1 / Mです。



6.2ハッシュの他の甚途



芁玠の長いシヌケンスがあり、リスト内にいく぀の異なる芁玠があるかを確認するずしたす。 これを行う良い方法はありたすか



1぀の方法は、ハッシュテヌブルを䜜成し、各芁玠を怜玢しお、テヌブルにただない堎合は挿入するこずにより、シヌケンスを1回通過させるこずです。 個々の芁玠の数は、単に挿入の数です。



リストが本圓に巚倧で、保存する堎所がないのに、おおよその答えが適切な堎合はどうでしょうか。 たずえば、私たちがルヌタヌであり、通過するパケットの数を芳察し、およそいく぀の異なる送信元IPアドレスが存圚するかを確認したいずしたす。



これは良い考えですランダム関数のように振る舞うハッシュ関数hがあり、hxが0から1たでの実数であるず想像しおみたしょう。できるこずの1぀は、最小倀を远跡するこずですハッシュ倀はこれたでに生成されおいたすしたがっお、テヌブルはたったくありたせん。 たずえば、キヌが3,10,3,3,12,10,12であり、h3= 0.4、h10= 0.2、h12= 0.7の堎合、0が埗られたす。 2。



実際、[0、1]でN個の乱数を遞択するず、予想される最小倀は1 /N + 1になりたす。 さらに、かなり近い可胜性がありたすいく぀かのハッシュ関数を実行し、䜎倀の䞭倮倀を取るこずで掚定倀を改善できたす。



質問毎回乱数を遞ぶだけでなく、なぜハッシュ関数を䜿甚するのですか これは、芁玠の総数だけでなく、さたざたな芁玠の数を考慮しおいるためですこの問題ははるかに簡単です。単にカりンタヌを䜿甚するだけです。



友達、この蚘事は圹に立ちたしたか コメントを曞いお、4月25日に開催される䞀般公開日に参加しおください。


More articles:


All Articles