ハッシュ関数とハッシュコード-＆＃＆チュートリアル-php.cn

ハッシュ関数とハッシュコード

WBOY

リリース： 2024-07-28 07:24:33

オリジナル

1074 人が閲覧しました

Hash Functions and Hash Codes

一般的なハッシュ関数は、まず検索キーをハッシュコードと呼ばれる整数値に変換し、次にハッシュコードをハッシュテーブルのインデックスに圧縮します。 Java のルートクラス Object には、整数のハッシュコードを返す hashCode メソッドがあります。デフォルトでは、メソッドはオブジェクトのメモリアドレスを返します。 hashCode メソッドの一般規約は次のとおりです:

equals メソッドがオーバーライドされるたびに、hashCode メソッドをオーバーライドして、2 つの等しいオブジェクトが同じハッシュコードを返すようにする必要があります。
プログラムの実行中に、hashCode メソッドを複数回呼び出すと、オブジェクトのデータが変更されていない限り、同じ整数が返されます。
2 つの等しくないオブジェクトが同じハッシュコードを持つ場合がありますが、そのようなケースが多すぎるのを避けるために hashCode メソッドを実装する必要があります。

プリミティブ型のハッシュコード

byte、short、int、および char タイプの検索キーの場合は、単純に int にキャストします。 。したがって、これらのタイプのいずれかの 2 つの異なる検索キーは、異なるハッシュコードを持ちます。

float タイプの検索キーの場合、ハッシュコードとして Float.floatToIntBits(key) を使用します。 floatToIntBits(float f) は、ビット表現が浮動小数点 f のビット表現と同じである int 値を返すことに注意してください。したがって、float タイプの 2 つの異なる検索キーは、異なるハッシュコードを持ちます。

タイプ long の検索キーの場合、最初の 32 ビットのみが異なるすべてのキーには、同じハッシュコード。最初の 32 ビットを考慮するには、64 ビットを 2 つの半分に分割し、排他的論理和演算を実行して 2 つの半分を結合します。このプロセスは折り畳みと呼ばれます。長いキーのハッシュコードはです int hashCode = (int)(key ^ (key >> 32));

>>>

は、ビットを 32 位置右にシフトする右シフト演算子であることに注意してください。たとえば、1010110 >> のようになります。 2 は 0010101 を生成します。 ^ はビットごとの排他的論理和演算子です。これは、バイナリオペランドの 2 つの対応するビットを操作します。たとえば、1010110 ^ 0110111 は 1100001 となります。タイプ

double

の検索キーの場合、最初に Double.doubleToLongBits メソッドを使用して long 値に変換し、次に次のように折りたたみを実行します。以下: ロングビット = Double.doubleToLongBits(key);

int hashCode = (int)(ビット ^ (ビット >> 32));

文字列のハッシュコード

検索キーは文字列であることが多いため、文字列に対して適切なハッシュ関数を設計することが重要です。直観的なアプローチは、すべての文字の Unicode を文字列のハッシュコードとして合計することです。このアプローチは、アプリケーション内の 2 つの検索キーに同じ文字が含まれていない場合には機能する可能性がありますが、

tod

や dot など、検索キーに同じ文字が含まれている場合は、多くの衝突が発生します。 . より良いアプローチは、文字の位置を考慮してハッシュコードを生成することです。具体的には、ハッシュコードを

とします。

s0*b(n - 1) + s1*b(n - 2) + c + sn-1

ここで、si は

s.charAt(i)

です。この式は、ある正の b の多項式であるため、多項式ハッシュコード と呼ばれます。多項式評価のホーナー規則を使用すると (ケーススタディ: 16 進数を 10 進数に変換するを参照)、ハッシュコードは次のように効率的に計算できます。 (...((s0*b + s1)b + s2)b + ... + sn-2)b + sn-1

この計算により、長い文字列ではオーバーフローが発生する可能性がありますが、Java では算術オーバーフローは無視されます。衝突を最小限に抑えるために、適切な値 b を選択する必要があります。実験によると、b の適切な選択は 31、33、37、39、および 41 です。

String

クラスでは、hashCode は、b が 31. ハッシュコードの圧縮

キーのハッシュコードは、ハッシュテーブルインデックスの範囲外の大きな整数になる可能性があるため、インデックスの範囲に収まるようにスケールダウンする必要があります。ハッシュテーブルのインデックスが

0

から

N-1 までであると仮定します。整数を 0 と N-1 の間でスケーリングする最も一般的な方法は、を使用することです。 h(ハッシュコード) = ハッシュコード % N

インデックスが均等に分散されるようにするには、2 より大きい素数となる N を選択します。

理想的には、N には素数を選択する必要があります。ただし、大きな素数を見つけるのは時間がかかります。 java.util.HashMap の Java API 実装では、N は 2 のべき乗の値に設定されます。この選択には十分な理由があります。 N が 2 のべき乗の値の場合、

h(ハッシュコード) = ハッシュコード % N

は

と同じです

h(ハッシュコード) = ハッシュコード & (N – 1)

アンパサンド & は、ビット単位の AND 演算子です。両方のビットが 1 の場合、2 つの対応するビットの AND は 1 を生成します。たとえば、N = 4 および hashCode = 11、11 % 4 = 3 と仮定します。これは 01011 & 00011 = 11。 & 演算子は、% 演算子よりもはるかに高速に実行できます。

ハッシュが均等に分散されることを保証するために、

java.util.HashMap の実装では、主要なハッシュ関数とともに補助ハッシュ関数も使用されます。この関数は次のように定義されます:

private static intSupplementalHash(int h) {

h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

^ および >>> は、ビット単位の排他的論理和および符号なし右シフト演算です。ビット単位の演算は、乗算、除算、剰余演算よりもはるかに高速です。可能な限り、これらの演算をビット単位の演算に置き換える必要があります。

完全なハッシュ関数は次のように定義されます:

h(ハッシュコード) = 補足ハッシュ(ハッシュコード) % N

これは

と同じです

h(ハッシュコード) = 補足ハッシュ(ハッシュコード) & (N – 1)

N は 2 のべき乗の値であるため、

以上がハッシュ関数とハッシュコードの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。