アルゴリズム知識——ハッシュアルゴリズム(hash)

ハッシュアルゴリズム
ハッシュアルゴリズムは特定のアルゴリズムではなく、アルゴリズムの総称である.ハッシュアルゴリズムはハッシュアルゴリズムとも呼ばれ、一般的にはf(data)=keyを満たし、任意の長さのdataデータを入力し、ハッシュアルゴリズム処理後に一定の長さのデータkeyを出力する.ハッシュアルゴリズムの最も重要な2つの性質は,不可逆的で衝突がないことである.dataデータセットであれば、ハッシュアルゴリズム処理後にkeyのデータセットが得られ、その後、keysを元のデータと1つずつマッピングしてハッシュテーブルが得られる.一般にハッシュテーブルMは、M[key]=dataという形式に適合する.ハッシュテーブルの利点は、元のデータが大きい場合、ハッシュアルゴリズムで一定のハッシュ値keyを処理することができ、このkeyは元のデータよりずっと小さいことである.この小さなデータセットでインデックスを作成し、迅速な検索の目的を達成することができます.少し考えてみると、入力データが一定長ではなく、出力されるハッシュ値が一定長である以上、ハッシュ値は有限な集合であり、入力データは無限に複数であることを意味する.では、一対一の関係を築くのは明らかに現実的ではない.したがって、「衝突」(異なる入力データが同じハッシュ値に対応する)は必然的に発生するため、成熟したハッシュアルゴリズムは衝突に対する耐性が高い.同時にハッシュテーブルの構造を実現する際にもハッシュ競合の問題を考慮しなければならない.
列子:例えば、ここには1万曲があって、何らかの方法で保存するように要求されています.その时、あなたに新しい歌(Xと命名)をあげて、新しいこの歌がその1万曲の中にあるかどうかを確認するように要求します.
間違いなく、1万曲を1対1で比べるのはとても遅いです.しかし、1万曲の各曲のデータを1つの数字(ハッシュコードと呼ばれる)に濃縮して1万個の数字を得る方法があれば、同じアルゴリズムで新しい歌Xの符号化を計算し、歌Xの符号化が前の1万個の数字の中にあるかどうかを見て、歌Xがその1万曲の中にあるかどうかを知ることができる.
1曲の5 Mバイトのデータを1つの数字に濃縮するアルゴリズムがハッシュアルゴリズムである.その1万曲がそれぞれの符号化数字に従って小さいものから大きいものに並べられた表がハッシュ表である.
明らかに、情報量の損失により、複数の歌のハッシュコードが同じである可能性がある.良いハッシュアルゴリズムは、このような衝突をできるだけ減らし、異なる歌に異なるハッシュコードを持たせる.最悪のハッシュアルゴリズムは自然にすべての歌がそのアルゴリズムで計算されたのは同じハッシュコードである.
例として、もしあなたがその1万曲の歌を組織するならば、1つの簡単なハッシュアルゴリズムは歌が占めるハードディスクのバイト数をハッシュコードとすることです.これにより、1万曲を「大きさ順に並べ替える」ことができ、新しい歌に出会うことができます.新しい歌のバイト数が既存の1万曲のうちの1曲のバイト数と同じかどうかを見るだけで、新しい歌がその1万曲の中にあるかどうかを知ることができます.
1万曲の規模では、このアルゴリズムはかなり良いです.2曲のバイト数が全く同じではありませんから.たとえ本当に極小の確率で異なる歌が同じハッシュコードを持っているとしても、それはわずか数曲しかありません.この時、もう1曲ずつ比較すればいいです.
ここの情報要約の応用を適用します.
情報の概要たとえると.あなたは遠くの友达に手紙を出しましたが、途中で交換されるのではないかと心配して、別の方法で友达に伝えました.私のこの手紙には134文字、34文字の句読点、72文字のAがあります.すると友达は、手紙の真偽を弁解しやすくなりました.コンピュータでは、この方法は大きなファイルが正しく転送されているかどうかを検証するために使用されます.あなたは1 Gの大きなファイルをダウンロードします.さまざまな転送のエラーのため、いくつかのバイトのエラーが発生する可能性があります.伝統的には、元のファイルをもう一つ送って、両者が同じかどうかを比較することができます.異なる場合は、2つのファイルが同じになるまで、もう一度転送する必要があります.
しかし、この方法は極めて愚かで、1つの賢い方法は、大きなファイルの後に1つの情報を添付して、バイナリファイルの単数の1です.ファイルがランダムにエラーが発生した場合,ファイルの1の数を数えるだけでエラーが検出され,エラーが発生した場合に再送される可能性があることが推測される.この方法では1/2のエラーしか検出できないが,実際に採用されているハッシュアルゴリズムは,1つのファイルを1つの文字列に精練することができ,ファイルが変化してもこの文字列が変わらないようにするには,確率が極めて低い.これで大部分の誤りを検証することができる.——————————————————————————————————————————————————————————————情報要約の運用はそれだけではなく,コンピュータ上で最も広く用いられているのがルックアップアルゴリズムである.例えば金山速盤--人々は書類を速盤にアップロードした.しかし、実は多くのファイルが重複していて、MP 3などは、基本的に同じいくつかです.サーバは、このような多くの情報を繰り返し格納する必要はありません.1つの合理的な方法は、ユーザがファイルをアップロードすると、ファイルにハッシュコードを与えることである.別のユーザーが同じファイルをアップロードするとき、まずサーバーでこのハッシュコードの有無を調べて、もしあるならば、ユーザーはアップロードする必要はありません.これはいわゆる妙伝技術で、時には数百Mのファイルが、瞬間的にアップロードされました.—————————————————————————————————————————————————説明するのは、ファイル名がハッシュコードに代わることはできません.同じファイル名は、同名ですが異なる音質のMP 3のような2つの異なるファイルであることが多いです.ファイル名+ファイルサイズにも問題があります.一番いいのはやはりハッシュコードです.——————————————————————————補足するのは、情報要約はパスワード自体を記録しないため、パスワードによく使用されます.この方法では、管理者でもパスワードがわかりません
あなたの果物の殻のパスワードがAであれば、情報の要約はsfsgです.ログインすると、ブラウザはまずAの情報要約を計算してサーバに送信し、サーバは正しい情報要約を記録し、比較するとログインを許可します.管理者はサーバを開いても、sfsgというコードしか調べられず、パスワードを逆に出すことはできません.また、ハッシュテーブルはルックアップ演算において非常に重要であり、検索文字列は大量の情報を検索するよりもずっと速い.
多くの高速計算は、実は表を調べることです(答えをたくさん計算しておきます.本当に計算するときは、データベースで答えの有無を調べておけばいいです.)
ハッシュ・テーブルは、空間を時間に変換し、実際の記憶データ量より大きいメモリ空間をO(1)の読み取り速度に変換することを意味します.
したがって,ハッシュテーブルの空間利用率をどのように高めるか,いつが最適なre−hashの時点であるかなど,多くの詳細が議論されている.