6

私はこの興味深いトピック (IMO) についてかなり多くのことを読んできました。しかし、私は1つのことを完全には理解していません:

辞書のサイズは、その容量を増加させています (最も近い素数に倍増) 素数に (再割り当ての場合) : 理由:

int index = hashCode % [Dictionary Capacity];
  • GreatestCommonFactor がで[Dictionary Capacity]あるため、素数がここで使用されていることがわかります。これは衝突を避けるのに役立ちます。1

加えて

私は実装の多くのサンプルを見てきましたGetHashCode():

以下は、Jon Skeet のサンプルです。

public override int GetHashCode()
{
    unchecked 
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

理解できない ：

質問

素数 は :との生成の両方で使用され ますか?Dictionary capacity getHashCode

上記のコードでは、戻り値が素数ではない可能性が高いため [間違っていたら訂正してください]

  • による乗算23
  • GetHashCode()各フィールドの値の追加。

例: (11,17,173 は素数)

        int hash = 17;
        hash = hash * 23 + 11; //402
        hash = hash * 23 + 17; //9263
        hash = hash * 23 + 173 //213222
        return hash;

213222 は素数ではありません。

また、次のような数学規則はありません。

(not a prime number) + (prime number) = (prime number)

または

(not a prime number) * (prime number) = (prime number)

または

(not a prime number) * (not a prime number) = (prime number)

それで、私は何が欠けていますか？

4

1 に答える 1

8

GetHashCode等しいと見なされる 2 つのオブジェクトの結果が同じである限り、isの結果が何であるかは問題ではありません (素数である必要はまったくありません)。ただし、異なると見なされる 2 つのオブジェクトに対して異なる値を返すと便利です(必須ではありません) (ただし、必ずしも素数である必要はありません)。GetHashCode

2 つの数値aとbが与えられた場合、それらを乗算すると、 が得られますc = a * b。通常、同じ結果cを与えるaとbの複数の異なるペアがあります。たとえば、6 * 2 = 12 および 4 * 3 = 12 です。ただし、aが素数の場合、同じ結果をもたらすペアははるかに少なくなります。これは、オブジェクトごとにハッシュ コードが異なる必要があるというプロパティに便利です。

ディクショナリでも同じ原則が適用されます。オブジェクトはハッシュに応じてバケットに入れられます。ほとんどの整数は素数でうまく割り切れないため、バケット内のオブジェクトが適切に分散されます。ディクショナリのパフォーマンスを最適化するには、各バケットに 1 つの項目のみを含めることが理想的です。

少し話が逸れますが、蝉 (昆虫です)は素数を使用して、何年後に交尾し、再び交尾するかを決定します。この交尾周期は素数年であるため、交尾が敵のライフ サイクルと継続的に一致する可能性はわずかです。

于 2013-02-20T16:09:23.147 に答える