オブジェクトのハッシュコード
System.Collections.Hashtableは、キーとするオブジェクトのGetHashCode()の戻り値で一意性を保証しているとする。
GetHashCode()は32bit整数型を返すので、個以上のオブジェクトをHashtableに格納しようとすると必ず衝突が起きる?
ということは、64bit整数型の乱数を放り込むと50%の確率で衝突する?
したがって個以上のオブジェクトを識別する必要があるときは自前で実装する必要がある?
System.Collections.Hashtableは、キーとするオブジェクトのGetHashCode()の戻り値で一意性を保証しているのか
とりあえず
Hashtable ht = new Hashtable(); long a = 321; long b = 654; long c = a << 32 | b; long d = a ^ b; ht.Add(c, "c"); ht.Add(d, "d");
でArgumentExceptionがスローされないのでGetHashCode()で一意性を保証しているわけではないということはわかった。
64bit整数型に対してGetHashCode()は何を返すか
「longのハッシュコード - u_1rohのカタチ」によると上位32bitと下位32bitの排他的論理和を返すらしい。
実際
long a = 321; long b = 654; long c = a << 32 | b; long d = a ^ b; Console.WriteLine("Hashcode: {0}", c.GetHashCode()); Console.WriteLine("XOR: {0}", d); Console.WriteLine("XORHash: {0}", d.GetHashCode());
とすると、いずれも975を返す。
ついでにSSCLIのソースコード追いかけてみたらInt64型のGetHashCode()はXORをとっていた。
// The value of the lower 32 bits XORed with the uppper 32 bits. public override int GetHashCode() { return (unchecked((int)((long)m_value)) ^ (int)(m_value >> 32)); }