12


インタビューで、整数または文字列にハッシュ関数を使用する必要がある状況に遭遇しました。そのような状況では、どちらを選択する必要がありますか? これらの状況で私は間違っていました。なぜなら、多くの衝突を生成するものを選択することになりますが、ハッシュ関数は数学的な傾向があり、インタビューで思い出すことができないからです。少なくともインタビュアーが整数または文字列入力に対するあなたのアプローチに満足するように、一般的な推奨事項はありますか? 「インタビューの状況」で両方の入力に適している関数はどれですか

4

3 に答える 3

8

以下は、 Effective Java page 33の簡単なレシピです。

  1. result という名前の int 変数に、0 以外の一定の値、たとえば 17 を格納します。
  2. オブジェクトの重要なフィールド f (equals メソッドによって考慮される各フィールド) ごとに、次の操作を行います。
    1. フィールドの int ハッシュ コード c を計算します。
      • フィールドがブール値の場合、(f ? 1 : 0) を計算します。
      • フィールドが byte、char、short、または int の場合、(int) f を計算します。
      • フィールドが long の場合、(int) (f ^ (f >>> 32)) を計算します。
      • フィールドが float の場合は、Float.floatToIntBits(f) を計算します。
      • フィールドが double の場合、Double.doubleToLongBits(f) を計算し、ステップ 2.1.iii のように結果の long をハッシュします。
      • フィールドがオブジェクト参照であり、このクラスの equals メソッドが equals を再帰的に呼び出してフィールドを比較する場合、フィールドで hashCode を再帰的に呼び出します。より複雑な比較が必要な場合は、このフィールドの「正規表現」を計算し、正規表現で hashCode を呼び出します。フィールドの値が null の場合は、0 を返します (またはその他の定数ですが、0 が伝統的です)。48 第 3 章 すべてのオブジェクトに共通のメソッド
      • フィールドが配列の場合は、各要素が個別のフィールドであるかのように扱います。つまり、これらのルールを再帰的に適用して重要な要素ごとにハッシュ コードを計算し、ステップ 2.b に従ってこれらの値を結合します。配列フィールドのすべての要素が重要な場合は、リリース 1.5 で追加された Arrays.hashCode メソッドのいずれかを使用できます。
    2. 次のように、手順 2.1 で計算されたハッシュ コード c を結果に結合します。
  3. 結果を返します。
  4. hashCode メソッドの記述が完了したら、等しいインスタンスのハッシュ コードが等しいかどうかを自問してください。単体テストを書いて直感を検証しましょう! 等しいインスタンスのハッシュ コードが等しくない場合は、その理由を突き止めて問題を解決してください。
于 2011-05-21T16:32:41.080 に答える
5

インタビュアーにハッシュ関数の目的を尋ねる必要があります。この質問に対する答えによって、適切なハッシュ関数の種類が決まります。

  • ハッシュマップのようなハッシュ化されたデータ構造で使用する場合は、可能な限り単純にして (実行が速く)、衝突を回避する必要があります (最も一般的な値が異なるハッシュ値にマップされます)。良い例は、同じ整数への整数ハッシュです。これは、java.lang.Integer の標準的な hashCode() 実装です。

  • セキュリティ目的の場合は、暗号化ハッシュ関数を使用する必要があります。これらは主に、ハッシュ関数を逆にしたり衝突を見つけたりするのが難しいように設計されています。

  • 高速な疑似乱数っぽいハッシュ値が必要な場合 (シミュレーションなど)、通常は疑似乱数ジェネレーターを変更してこれらを作成できます。私の個人的なお気に入りは次のとおりです。

public static final int hash(int a) {         
      a ^= (a << 13);
      a ^= (a >>> 17);        
      a ^= (a << 5);
      return a;   
}

何らかの形式の複合構造 (複数の文字を含む文字列、配列、または複数のフィールドを含むオブジェクトなど) のハッシュを計算する場合、組み合わせたハッシュ関数を作成するために使用できるさまざまな手法があります。構成部分の回転されたハッシュ値を XOR することをお勧めします。たとえば、次のようになります。

public static <T> int hashCode(T[] data) {
    int result=0;
    for(int i=0; i<data.length; i++) {
        result^=data[i].hashCode();
        result=Integer.rotateRight(result, 1);
    }
    return result;
}

上記は暗号的に安全ではないことに注意してください。ただし、他のほとんどの目的には使用できます。明らかに衝突が発生しますが、大きな構造を整数にハッシュする場合は避けられません:-)

于 2011-05-21T16:36:01.450 に答える
2

整数の場合、通常は k % p を使用します。ここで、p = ハッシュ テーブルのサイズであり、素数です。文字列の場合は、String クラスからハッシュコードを選択します。大手テック企業との面接にはこれで十分でしょうか? – フェニックス 2日前

そうでないかもしれない。実装が不明なハッシュ テーブルにハッシュ関数を提供する必要があることは珍しくありません。さらに、素数のバケットを使用して実装に依存する方法でハッシュすると、新しいライブラリ、コンパイラ、OS ポートなどによって実装が変更されると、パフォーマンスが低下する可能性があります。

個人的には、インタビューで重要なことは、汎用ハッシュ アルゴリズムの理想的な特性を明確に理解することだと思います。出力が反転する可能性は約 50/50 です。私が最初に見たハッシュ関数の多くは、ビットシフトと XOR を使用し、反転された入力ビットは通常、1 つの出力ビットを反転したため、直感に反することがわかりました (通常は別のビット位置にあるため、1-input-bit-affects-many -output-bits は、Knuth の本の 1 つで読んだとき、ちょっとした啓示の瞬間でした. この知識があれば、実装方法に関係なく、少なくとも特定の実装をテストして評価することができます.

この理想を達成し、覚えやすいので、私が言及する1つのアプローチは、メモリ使用量が数学的アプローチよりも遅くなる可能性がありますが（ハードウェアによっては高速になる可能性があります）、入力の各バイトを単純に使用して検索することです。ランダム int のテーブル。たとえば、24 ビットの RGB 値と が与えられた場合int table[3][256]、table[0][r] ^ table[1][g] ^ table[2][b]は優れたsizeof intハッシュ値です。実際、入力がint値全体にランダムに分散している場合 (インクリメントと言うのではなく、以下を参照) は「完全」です。このアプローチは、長いキーや任意の長さのキーには理想的ではありませんが、テーブルを再確認して値をビットシフトすることはできます.

とはいえ、入力キーのパターンおよび/または関連するバケットの数を認識している特定のケースでは、このランダム化アプローチよりもうまくいく場合があります (たとえば、入力キーが 1 から100 個あり、128 個のバケットがあるため、キーを渡すことなくキーを渡すことができます。衝突)。ただし、入力が期待に応えなくなった場合、恐ろしい衝突の問題が発生する可能性がありますが、「ランダム化」アプローチは load (size() / buckets) が示すよりもはるかに悪化することはありません。もう 1 つの興味深い洞察は、迅速かつ平凡なハッシュが必要な場合、ハッシュを生成するときに必ずしもすべての入力データを組み込む必要はないということです。入力として使用するテキストに沿って....

于 2011-05-24T08:25:24.720 に答える