Ist es möglich, Hash-Codes für private Mitglieder zu kombinieren, um einen neuen Hash-Code zu generieren?

Question

Ich habe ein Objekt, für das ich einen eindeutigen Hash generiert werden soll (außer Kraft setzen GetHashCode ()), aber ich mag unberechenbar überläuft oder etwas vermeiden.

Der Code sollte das Ergebnis der Kombination den Hash-Codes von einer kleinen Sammlung von Strings sein.

Die Hash-Codes wird ein Teil der Erzeugung eines Cache-Schlüssel sein, so im Idealfall sollten sie jedoch die Anzahl der möglichen Werte eindeutig sein, die kleine gehasht werden, ist, so denke ich Wahrscheinlichkeit zu meinen Gunsten ist hier.

wäre so etwas wie dies ausreichend sein, um und gibt es einen besseren Weg, dies zu tun?

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

EDIT: Danke für Antworten so weit. @ Jon Skeet: Nein, um nicht wichtig ist,

Ich denke, das ist fast ein andere Frage, aber da ich das Ergebnis ist mit einem Cache-Schlüssel (string) zu erzeugen, wäre es sinnvoll, eine Cryptographic Hash-Funktion wie MD5 zu verwenden oder einfach nur die Stringdarstellung dieses int verwenden?

Answer 1

Die Grundlagen von Marc und Jon wiesen darauf hin, sind nicht schlecht, aber sie sind bei weitem nicht optimal hinsichtlich ihrer Gleichmäßigkeit der Verteilung der Ergebnisse. Leider ist das Konzept ‚von Primzahlen multiplizieren‘ von so vielen Menschen aus Knuth kopiert ist nicht die beste Wahl in viele Fälle bessere Verteilung können durch billigere erreicht werden Funktionen zu berechnen (obwohl dies sehr leichte auf moderne Hardware). In der Tat Primzahlen in viele Aspekte des Hashing werfen kein Allheilmittel .

Wenn diese Daten für deutlich Größe Hash-Tabellen verwendet wird, empfehle ich das Lesen von Bret Mulveys ausgezeichnete Studie und Erklärung von verschiedenen modernen (und nicht so modern) Hashing-Techniken handlich mit c # getan.

Hinweis

, dass das Verhalten von Strings unterschiedlichen Hash-Funktionen ist stark voreingenommen gegenüber wehther die Saiten sind kurz (grob gesagt, wie viele Zeichen gehasht werden, bevor die Bits über Flüsse beginnen) oder lang.

Eine der einfachsten und leichtesten einer der besten ist auch, die Jenkins One zu einem Zeitpunkt Hash zu implementieren.

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);
}

Sie können dann diese verwenden etwa so:

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

Sie können wie so mehrere verschiedene Arten zusammen:

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);
}

Wenn Sie nur Zugriff auf das Feld ohne Kenntnis der Interna als Objekt haben, können Sie einfach GetHashCode () auf jeder anrufen und diesen Wert kombinieren etwa so:

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

Leider kann man nicht tun sizeof (T), so dass Sie müssen jeweils einzeln tun Struktur.

Wenn Sie Reflektion verwenden Sie auf einer Pro-Typ-Basis eine Funktion konstruieren kann, die strukturelle Identität hat und auf allen Gebieten Hashing.

Wenn Sie möchten, unsicheren Code vermeiden, dann können Sie Bit Maskierungstechniken verwenden, um einzelne Bits aus Ints herausziehen (und Zeichen, wenn mit die Behandlung von Strings) mit nicht zu viel zusätzlichen Aufwand.

Answer 2

Hashes sind nicht bedeutet , einzigartig zu sein - sie sind nur gut gemeint in den meisten Situationen zu verteilen. Sie sind einfach konsequent sein soll. Beachten Sie, dass Überlauf sollte kein Problem sein.

Nur ist das Hinzufügen nicht generell eine gute Idee, und Dividieren ist sicherlich nicht. Hier ist der Ansatz, den ich in der Regel verwenden:

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

Wenn Sie sonst in einem geprüften Kontext sind, möchten Sie vielleicht absichtlich diese Funktion nicht aktiviert werden.

Beachten Sie, dass dies setzt voraus, dass wichtig ist, um, das heißt, dass { "a", "b"} sollte anders sein { "b", "a"}. Bitte lassen Sie uns wissen, wenn das nicht der Fall ist.

Answer 3

Es ist nichts falsch mit diesem Ansatz, solange die Mitglieder, deren Hashcodes Sie kombinieren die Regeln der Hash-Codes folgen. Kurz gesagt ...

1. Der Hash-Code der privaten Mitglieder sollten nicht für die gesamte Lebensdauer des Objekts
ändern
2. Der Behälter muss das Objekt nicht ändern die privaten Mitglieder, damit sie wiederum weisen den Hash-Code des Behälters ändern

Answer 4

Wenn die Reihenfolge der Elemente nicht wichtig ist (dh { „a“, „b“} ist die gleiche wie { „b“, „a“}), dann können Sie exklusiv verwenden oder den Hash-Codes zu kombinieren:

hash ^= item.GetHashCode();

[Edit: Als Mark in eine andere Antwort in einem Kommentar darauf hingewiesen, hat dies den Nachteil, auch geben Sammlungen wie { "a"} und { "a", "b", "b"} der gleichen Hash-Code .]

Wenn die Reihenfolge wichtig ist, können Sie stattdessen durch eine Primzahl multiplizieren und fügen Sie:

hash *= 11;
hash += item.GetHashCode();

(Wenn Sie multiplizieren Sie manchmal einen Überlauf bekommen, die ignoriert wird, aber mit einer Primzahl multipliziert man ein Minimum an Informationen verlieren. Wenn Sie stattdessen mit einer Zahl wie 16 multipliziert, werden Sie vier Bits an Informationen verlieren jedes Mal , so dass nach acht Elementen der Hash-Code aus dem ersten Punkt wäre völlig verschwunden sein.)