27

ハッシュ テーブルは、データを保存/取得する最速/最良の方法であると言われています。

ハッシュテーブル、ハッシュについての私の理解は次のとおりです（間違っている場合は修正してください。他に何かあれば追加してください）：

  • ハッシュ テーブルは、値を格納するための配列 (単一または多次元) に他なりません。
  • ハッシュは、データを挿入/取得するために配列内のインデックス/場所を見つけるプロセスです。データ項目を取得し、それをキーとしてハッシュ関数に渡すと、データを挿入/取得するインデックス/場所を取得できます。

質問があります：

データの保存/取得に使用されるハッシュ関数は、MD5、HMAC、SHA-1 などの認証用のセキュリティ アプリケーションで使用される暗号化ハッシュ関数とは異なりますか?

それらはどのように異なりますか？

  • Cでハッシュ関数を書くには?
  • それに対する標準やガイドラインはありますか？
  • ハッシュ関数の出力、つまりインデックスが範囲外にならないようにするにはどうすればよいでしょうか?

これらをよりよく理解するための良いリンクをいくつか挙げていただければ幸いです。

4

3 に答える 3

11

暗号化ハッシュは、誰かが意図的に衝突を起こすことを困難にすることを強調しています。ハッシュ テーブルの場合、通常、妥当な範囲の結果を迅速に生成することに重点が置かれます。そのため、通常、この 2 つはまったく異なります (特に、暗号化ハッシュは通常、はるかに低速です)。

典型的なハッシュ関数の場合、結果は型によってのみ制限されます。たとえば、size_t を返す場合、可能な任意の size_t を返すことはまったく問題ありません。その出力範囲をテーブルのサイズに縮小するのはあなた次第です (たとえば、テーブルのサイズで割った剰余を使用します。これは多くの場合、素数になるはずです)。

例として、かなり典型的な通常のハッシュ関数は次のようになります。

// warning: untested code.
size_t hash(char const *input) { 

    const int ret_size = 32;
    size_t ret = 0x555555;
    const int per_char = 7;

    while (*input) { 
        ret ^= *input++;
        ret = ((ret << per_char) | (ret >> (ret_size - per_char));
   }
   return ret;
}

ここでの基本的な考え方は、入力文字列のすべてのビットが結果に影響を与え、結果のすべてのビットが入力の少なくとも一部の影響を受けるようにすることです。これを優れたハッシュ関数として特に推奨しているわけではないことに注意してください。達成しようとしていることの基本のいくつかを説明しようとしているだけです。

于 2010-02-10T15:54:31.263 に答える
4

Bob Jenkins は、彼の優れた (少し時代遅れではあるが)ハッシュ関数の詳細な説明を書きました。この記事には、より新しい、より優れたハッシュ関数へのリンクがありますが、この記事では、優れたハッシュ関数を構築する際の懸念事項に対処しています。

また、ほとんどのハッシュ テーブルの実装では、実際には連結リストの配列を使用して衝突を解決しています。配列だけを使用したい場合は、ハッシュ関数で衝突をチェックし、新しいハッシュ インデックスを作成する必要があります。

あなたが言及した暗号化ハッシュ関数は、ハッシュテーブルのハッシュ関数として使用できますが、ハッシュテーブル用に設計されたハッシュ関数よりもはるかに遅くなります。速度は総当たり攻撃を容易にします。

于 2010-02-10T15:50:40.807 に答える
0

設計目標が異なります。

たとえば、暗号化ハッシュ関数では、ハッシュとハッシュ関数を使用して、元のデータまたは同じハッシュを生成する他のデータを決定できないようにする必要があります。

ハッシュ テーブルやその他のデータ構造で使用されるハッシュ関数には、このようなセキュリティ プロパティは必要ありません。多くの場合、ハッシュ関数が高速で、入力セットを可能なハッシュのセットに均等に分散させれば十分です (不要なクラスタリング/衝突を回避するため)。

于 2010-02-10T21:42:54.553 に答える