algorithm
ハッシュ関数

ハッシュ関数の概要

ハッシュ関数h()は任意の大きさのデータy ∈ Yを固定サイズの値x ∈ X写像する任意の関数であるy = h(x) 。良いハッシュ関数には次のような制限があります。

• ハッシュ関数は一様分布を好む

• ハッシュ関数は決定論的です。 h(x)は与えられたxに対して常に同じ値を返さなければならない

• 高速計算（ランタイムO（1）を持つ）

一般的にハッシュ関数のサイズは、入力データのサイズより小さい： |y| < |x| 。ハッシュ関数は可逆的ではなく、言い換えれば、衝突する可能性があります： ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) Xは有限または無限集合であり、 Yは有限集合である。

ハッシュ関数は、ソフトウェア工学、暗号、データベース、ネットワーク、機械学習など、コンピュータサイエンスの多くの部分で使用されています。ハッシュ関数にはさまざまなタイプがあり、ドメイン固有のプロパティが異なります。

しばしば、ハッシュは整数値です。ハッシュ計算のためのプログラミング言語には特別な方法があります。たとえば、すべての型のC# GetHashCode()メソッドはInt32値（32ビット整数）を返します。 Javaすべてのクラスがintを返すhashCode()メソッドを提供しています。各データ型には、独自またはユーザー定義の実装があります。

ハッシュメソッド

ハッシュ関数を決定するにはいくつかの方法があります。一般性を失うことなく、 x ∈ X = {z ∈ ℤ: z ≥ 0}を正の整数とする。多くの場合、 mは素数です（2の正確な累乗にはあまり近似していません）。

ハッシュ表

ハッシュテーブルでハッシュ関数を使用してインデックスをスロットの配列に変換します。ハッシュテーブルは、辞書（キー値構造）を実装するためのデータ構造です。実装された良いハッシュテーブルには、次の操作のためのO（1）時間があります：キーでデータを挿入、検索、および削除します。複数のキーが同じスロットにハッシュされる場合があります。衝突を解決するには2つの方法があります。

1. 連鎖：リンクされたリストは、スロットに同じハッシュ値を持つ要素を格納するために使用されます

2. オープンアドレス指定：各スロットにゼロまたは1つの要素が格納される

次の方法は、オープンアドレッシングに必要なプローブシーケンスを計算するために使用されます

ここで、 i ∈ {0, 1, ..., m-1} 、 h'(x), h1(x), h2(x)補助ハッシュ関数であり、 c1, c2正の補助定数です。

例

x∈U x ∈ U{1, 1000}, h = x mod m 1,1000 x ∈ U{1, 1000}, h = x mod m 。次の表は、プライムとプライムがない場合のハッシュ値を示しています。太字のテキストは同じハッシュ値を示します。

リンク

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズムの紹介。

• ハッシュテーブルの概要

• Wolfram MathWorld - ハッシュ関数

C＃の一般的な型のハッシュコード

GetHashCode()メソッドによって生成された、 System名前空間の組み込み C＃型のハッシュコードを以下に示します。

ブール

値が真の場合は1、それ以外の場合は0

Byte 、 UInt16 、 Int32 、 UInt32 、 Single

値（必要に応じてInt32にキャスト）。

SByte

((int)m_value ^ (int)m_value << 8);

チャー

(int)m_value ^ ((int)m_value << 16);

Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64 、 Double

64ビット数の下位32ビットのXOR

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64 、 DateTime 、 TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

小数

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

オブジェクト

RuntimeHelpers.GetHashCode(this);

デフォルト実装はsyncブロックインデックスを使用します 。

文字列

ハッシュコードの計算は、プラットフォームの種類（Win32またはWin64）、ランダム化された文字列のハッシング、デバッグ/リリースモードの機能に依存します。 Win64プラットフォームの場合：

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
    hash1 = ((hash1 << 5) + hash1) ^ c;
    c = s[1];
    if (c == 0)
        break;
    hash2 = ((hash2 << 5) + hash2) ^ c;
    s += 2;
}
return hash1 + (hash2 * 1566083941);

ValueType

最初の非静的フィールドは、探して、ハッシュコードを取得します。型に非静的フィールドがない場合、型のハッシュコードが返されます。そのメンバが元の型と同じ型である場合、計算は無限ループに終わるので、静的メンバのハッシュコードをとることはできません。

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

アレイ

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++) 
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

参考文献

• GitHub .Net Core CLR