プライベートメンバーのハッシュコードを組み合わせて新しいハッシュコードを生成することはできますか?
-
21-08-2019 - |
質問
一意のハッシュを生成したい (GetHashCode() をオーバーライドする) オブジェクトがありますが、オーバーフローや予測不可能な事態は避けたいと考えています。
コードは、文字列の小さなコレクションのハッシュ コードを組み合わせた結果である必要があります。
ハッシュ コードはキャッシュ キーの生成の一部であるため、理想的には一意である必要がありますが、ハッシュされる可能性のある値の数は少ないため、ここでは確率が有利だと思います。
このようなもので十分でしょうか?また、これを行うより良い方法はありますか?
int hash = 0;
foreach(string item in collection){
hash += (item.GetHashCode() / collection.Count)
}
return hash;
編集:これまでの回答ありがとうございます。@ジョン・スキート:いいえ、順序は重要ではありません
これはほぼ別の質問だと思いますが、結果を使用してキャッシュキー(文字列)を生成しているので、MD5のような暗号ハッシュ関数を使用するのが理にかなっているのでしょうか、それともこのintの文字列表現を使用するだけでしょうか?
解決
マルクとジョンが指摘ファンダメンタルズは悪くないですが、彼らは結果の分布の彼らの均一性の観点で最適からは程遠いです。悲しいことにクヌースから非常に多くの人々によってコピーされたアプローチ「素数を掛け」でない最良の選択であります(これは最新のハードウェア上のの非常にのわずかであるが)より良い分布の多くの例は、関数を計算するために安くすることにより達成することができます。ハッシュの多くの側面に素数を投げる実際には万能薬 。
このデータは大幅にサイズのハッシュテーブルのために使用されている場合は、私はブレットMulveyの優れた研究と説明rel="noreferrer">のの技術をハッシングます。
様々なハッシュ関数の文字列との動作は、文字列が(おおよそのビットは、フロー上に始める前に、ハッシュ化されているどのように多くの文字を話す)、短いまたは長いですwehtherに向け大きくバイアスされていることに注意してください。
実装する最も簡単かつ最も簡単なの一つは、また、最高の一つ、時間ハッシュでジェンキンスの一つである。
private static unsafe void Hash(byte* d, int len, ref uint h)
{
for (int i = 0; i < len; i++)
{
h += d[i];
h += (h << 10);
h ^= (h >> 6);
}
}
public unsafe static void Hash(ref uint h, string s)
{
fixed (char* c = s)
{
byte* b = (byte*)(void*)c;
Hash(b, s.Length * 2, ref h);
}
}
public unsafe static int Avalanche(uint h)
{
h += (h<< 3);
h ^= (h>> 11);
h += (h<< 15);
return *((int*)(void*)&h);
}
あなたがそうのようにこれを使用することができます:
uint h = 0;
foreach(string item in collection)
{
Hash(ref h, item);
}
return Avalanche(h);
あなたがそうのような複数の異なる種類をマージすることができます:
public unsafe static void Hash(ref uint h, int data)
{
byte* d = (byte*)(void*)&data;
AddToHash(d, sizeof(int), ref h);
}
public unsafe static void Hash(ref uint h, long data)
{
byte* d= (byte*)(void*)&data;
Hash(d, sizeof(long), ref h);
}
あなたが唯一の内部の知識を持つオブジェクトとしてフィールドへのアクセス権を持っている場合は、あなたは、単にそれぞれにGetHashCodeメソッド()を呼び出し、そのようにその値を組み合わせることができます:
uint h = 0;
foreach(var item in collection)
{
Hash(ref h, item.GetHashCode());
}
return Avalanche(h);
悲しいことに、あなたがのsizeof(T)を行うことはできませんので、あなたは、それぞれが個別のstruct行う必要があります。
あなたはリフレクションを使用したい場合は、あなたはタイプごとにすべてのフィールドに構造的同一とハッシュを行う機能を構築することができます。
あなたは危険なコードを避けたい場合は、あなたはあまりにも多くの余分な手間と(文字列を扱う場合や文字)int型から個々のビットを引き出すためにビットマスキング技術を使用することができます。
他のヒント
ハッシュされていないののユニークであることを意味しました。彼らはただ一貫であることを意味しています。オーバーフローが問題になることはありませんので注意してください。
ただ、追加は、一般的に良いアイデアではない、と確かに分割することはできません。ここで私は通常使用のアプローチがあります:
int result = 17;
foreach (string item in collection)
{
result = result * 31 + item.GetHashCode();
}
return result;
あなたがチェック文脈でそうでないなら、あなたは意図的にそれをチェックしないようにしたいかもしれません。
{ "A"、 "B" が} { "B"、 "A"}異なるされるべきであること、すなわち、この順序が重要であると仮定することに注意してください。それはケースはない場合はお知らせください。
結合するハッシュコードのメンバーがハッシュ コードの規則に従っている限り、このアプローチに問題はありません。要するに ...
- プライベートメンバーのハッシュコードは、オブジェクトの存続期間中変更されるべきではありません。
- コンテナーは、コンテナーのハッシュ コードを変更しないように、プライベート メンバーが指すオブジェクトを変更してはなりません。
の項目の順序が重要でない場合は、あなたが排他的に使用できるか、ハッシュコードを組み合わせること(すなわち{「A」、「B」}、{「B」、「A」}と同じです)。
hash ^= item.GetHashCode();
[編集:マークが異なる回答にコメントで指摘したように、これはまた、{「A」}と{「A」、「B」、「B」}同じハッシュコードのようなコレクションを与えるという欠点を有しています。]
の順序が重要な場合は、あなたの代わりに素数で乗算し、追加することができます:
hash *= 11;
hash += item.GetHashCode();
(あなたが掛けたとき、あなたは時々無視されますが、素数を乗算することにより、あなたは最小限の情報を失うされてオーバーフローを取得します。あなたの代わりに16のような数で乗算した場合は、4ビットの情報たびに失うことになりますので、8つの項目の後の最初の項目からハッシュコードが完全になくなってしまう。)