レインボーテーブル - Wikipedia
レインボーテーブル (rainbow table) は、ハッシュから平文を得るために使われるテクニックの一つである。特殊なテーブルを使用して表引きを行うことで、時間と空間のトレードオフを実現している。 以降では、このテクニックの元となっているアイディアについて説明する。 3 種類の還元関数を使った簡単なレインボーテーブルの例 最も単純な方法[編集] レインボーテーブルは「あるハッシュ値に対して総当たり攻撃を行った際の計算結果を、別のハッシュ値を攻撃する際に使用する」というアイデアに端を発する。例えば、平文 Pi (i = 1, 2, ...) と、それらをハッシュ化した値 Ci をテーブルに格納しておき、このテーブルを逆引きすればハッシュ値から対応する平文が得られる。 ただし、この方法では、得られた平文とハッシュ値とのペアを全て記録しておく必要があり、実現には莫大な記憶領域を必要とする。
Cuckoo Hashing - Radium Software
ハッシュテーブルからエントリーを検索する処理は，一般に定数時間で済むとされている。つまり，どんなにエントリーが増えても検索の速さは変わらない，ということ。データ構造の教科書には必ず載っていることだね。 でも実際には，ハッシュの衝突が起こった場合に，速度の低下が発生する可能性がある。例えば，一般的なチェイン法（オープンハッシュ）だと，衝突したエントリーに関して線形検索を行うことになるから，衝突が多ければ多いほど，定数時間からは遠のいてしまう。 この速度低下を防ぐ方法はいろいろある。なかでも cuckoo hashing （カッコウ・ハッシング）は仕組みが面白い。こいつは，エントリーの検索を必ず定数時間で済ませてくれるという優れものなんだ。 Cuckoo hashing では，２つのハッシュ関数と，２つのテーブルを用いる。ここでは，２つのハッシュ関数をそれぞれ h1, h2 として，２つのテー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
