まえがき

プログラマは、業界で有名な MD5、SHA、CRC などのハッシュアルゴリズムに精通している必要があります。 , など; 日常の開発では、Map を使用して (キー、値) 構造を持つデータをロードしたり、ハッシュアルゴリズム O(1) の時間計算量を使用してプログラムの処理効率を向上させたりすることがよくあります。ハッシュアルゴリズムの他の応用シナリオをご存知ですか?

1. ハッシュアルゴリズムとは何ですか?

ハッシュアルゴリズムのアプリケーションシナリオを理解する前に、まず ハッシュ (ハッシュ) の概念を見てみましょう. ハッシュとは、任意の長さの入力を固定長の出力に変換することです。入力は Key と呼ばれ、出力はハッシュ値、つまりハッシュ値 hash(key) で、ハッシュアルゴリズムは hash() 関数です (ハッシュとハッシュはハッシュ の異なる翻訳です)。 ; 実際には、これらのハッシュ値は、ハッシュテーブルと呼ばれる配列に格納されます。ハッシュテーブルは、配列の機能を使用して、添え字に従ってデータへのランダムアクセスをサポートします。データ値と配列の添え字は、ハッシュ関数。1 対 1 のマッピングにより、時間計算量 O(1) のクエリを実現します。

#1.1 ハッシュの競合

現在のハッシュアルゴリズム MD5、SHA、CRC などは、異なるキーに対応する異なるハッシュ値を持つハッシュ関数を実現できません。つまり、異なるキーが同じ値にマッピングされる状況を避けることは不可能です。 ハッシュの競合、アレイのストレージ容量は限られているため、ハッシュの競合が発生する可能性も高くなります。ハッシュの衝突を解決するにはどうすればよいですか?私たちが一般的に使用するハッシュ競合解決方法には、オープンアドレッシングとチェーンという 2 種類があります。

1.1.1 オープンアドレッシング方法

線形検出によりハッシュテーブル内の空き位置を見つけ、ハッシュ値を書き込みます:

#図に示すように、834313 はハッシュテーブルの位置 303432 にハッシュされ、競合が発生します。空き位置が見つかるまでハッシュテーブルが順次走査され、834313 が書き込まれます。ハッシュテーブルに空き位置がないと、ハッシュ競合の可能性が大幅に増加します。通常の状況では、ハッシュテーブルに一定の割合の空きスロットが存在するように最善を尽くします。このとき、## を使用します。 #Loading Factor

は空きスロットの数を表し、計算式は次のとおりです: ハッシュテーブルのロード係数 = テーブルに埋められた要素の数 / ハッシュテーブルの長さ。負荷率が大きいほど、空き場所が少なくなり、競合が多くなり、ハッシュテーブルのパフォーマンスが低下します。データ量が比較的少なく、負荷率が小さい場合には、オープンアドレッシング方式を使用するのが適しているため、Java の ThreadLocalMap では、オープンアドレッシング方式を使用してハッシュの競合を解決します。

1.1.2 リンクリスト方式

リンクリスト方式は、より一般的に使用されるハッシュ競合解決方式であり、より簡単です。図に示すように:

ハッシュテーブルでは、各バケット/スロットがリンクリストに対応し、同じハッシュ値を持つすべての要素が対応するリンクリストに配置されます。中; ハッシュの競合が多い場合、リンクリストの長さも長くなり、ハッシュ値のクエリにはリンクリストを走査する必要があり、クエリ効率が O(1) から O に低下します。 (n)。

ハッシュ競合を解決するこの方法は、大きなオブジェクトと大量のデータを含むハッシュテーブルにより適しており、リンクリストの代わりに赤黒ツリーを使用するなど、より多くの最適化戦略をサポートしています。jdk1.8 は設計されています。 HashMap をサポートするために、さらに最適化するために、赤黒ツリーが導入されます。リンクリストの長さが長すぎる場合 (デフォルトは 8 を超える場合)、リンクリストは赤黒ツリーに変換されます。このとき、赤-black ツリーを使用すると、HashMap のパフォーマンスを向上させるために、迅速に追加、削除、確認、および変更を行うことができます。赤黒ツリーノードの数が 8 未満の場合、赤黒ツリーはリンクリストに変換されます。データ量が比較的少ない場合、赤黒ツリーはバランスを保つ必要があるため、リンクリストと比較してパフォーマンス上の利点は明らかではありません。

2. ハッシュアルゴリズムの適用シナリオ

2.1 安全な暗号化

暗号化に最も一般的に使用されるハッシュアルゴリズムは MD5 です。 (MD5 Message-Digest Algorithm) や SHA (Secure Hash Algorithm) は、ハッシュの特性を利用して、元のデータを逆推定することが困難なハッシュ値を計算し、暗号化の目的を達成します。

MD5 を例にとると、ハッシュ値は固定の 128 ビットバイナリ文字列であり、最大 2^128 データを表すことができます。このデータはすでに天文学的な数であり、ハッシュの競合の可能性は低くなります。この MD5 と同じデータを網羅的に検索しようとすると、天文学的な時間がかかるため、限られた時間内にハッシュアルゴリズムを解読するのは依然として困難です。暗号化効果が得られることを示します。

2.2 データ検証

ハッシュ関数の

データ感度

機能を使用すると、ネットワーク送信中のデータが正しいかどうかを検証できます。、悪意のある改ざんを防ぐため。

2.3 ハッシュ関数

ハッシュ関数の相対的 一様分布特性を利用して、ハッシュ値はデータストレージの位置値として使用されます。データはコンテナ内に均等に分散されます。

2.4 負荷分散

ハッシュアルゴリズムを使用して、クライアント ID アドレスまたはセッション ID のハッシュ値を計算し、取得したハッシュ値をサーバーリストモジュロ演算を行った後の最終値は、ルーティング先のサーバー番号になります。

2.5 データの断片化

ユーザーの検索キーワードを記録する 1T ログファイルがある場合、各キーワードの回数をすばやくカウントしたいと考えます。キーワード が検索されました。どうすればよいですか?データの量が比較的多く、1 台のマシンのメモリに置くのは困難です。1 台のマシンに置いたとしても、処理時間は非常に長くなります。この問題を解決するには、まずデータを断片化して、次に、複数のマシンを使用して処理する方法を使用して、処理速度を向上させます。

具体的なアイデアは次のとおりです。処理速度を向上させるために、n 台のマシンを使用して並列処理します。検索記録のログファイルから、各検索キーワードを順番に分析し、ハッシュ関数を使用して n を法として計算したハッシュ値が、割り当てられるべきマシン番号になります。ハッシュ値同じ値を持つ検索キーワードは同じマシンに割り当てられ、各マシンはキーワードの出現数を個別にカウントし、最終的にそれらを結合して最終結果を取得します。実はここの処理プロセスはMapReduceの基本的な設計思想でもあります。

2.6 分散ストレージ

大量のデータをキャッシュする必要がある状況では、1 台のキャッシュマシンでは明らかに不十分であるため、データを 1 台の複数のキャッシュマシンに分散する必要があります。機械。このとき、以前のシャーディングのアイデアを使用できます。つまり、ハッシュアルゴリズムを使用してデータのハッシュ値を取得し、マシン数の剰余を取得して、保存する必要があるキャッシュマシン番号を取得します。

しかし、データが増加すると、元の10台のマシンでは耐えられなくなり、拡張する必要が生じます。このとき、すべてのデータのハッシュ値を再計算して正しいマシンに移動すると、キャッシュされたデータはすべて一度に無効になるため、キャッシュを突き抜けてソースに戻り、雪崩現象を引き起こしてデータベースを圧倒する可能性があります。すべてのデータを移動せずに新しいキャッシュマシンを追加するには、 Consistent Hash Algorithm がより良い選択です。主なアイデアは次のとおりです: kge マシンがあると仮定すると、データのハッシュ値の範囲は [0] , Max] で、範囲全体を m 個の小さな間隔に分割します (m は k よりもはるかに大きいです)。各マシンは m/k 個の小さな間隔を担当します。新しいマシンが参加すると、元のマシンから特定の小さな間隔のデータを分割します。この方法では、すべてのデータを再ハッシュして移動する必要がなく、各マシン上のデータ量のバランスが維持されます。

3. 最後に書かれています

実際、ハッシュアルゴリズムには、git commit id など、他にも多くのアプリケーションがあります。理解と拡張は、基本的なデータ構造とアルゴリズムの価値を体現するものでもあり、仕事の中でゆっくりと理解して経験する必要があります。

推奨チュートリアル: 「Java チュートリアル」

以上が一般的に使用されるアルゴリズム: ハッシュアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。