Was passiert, wenn im Dictionary-Schlüssel eine Hash-Kollision auftritt?

Hash-Kollisionen werden nun korrekt behandelt, von Dictionary<> - in, so lange, wie ein Objekt implementiert GetHashCode() und Equals() richtig, die entsprechende Instanz zurückgegeben werden, aus dem Wörterbuch.

Erste, das solltest du nicht machen keine Annahmen darüber, wie Dictionary<> intern arbeitet - das ist eine Implementierung detail, das wahrscheinlich ändern im Laufe der Zeit. Having said that....

Was Sie Bedenken müssen, ist, ob die Typen, die Sie für den Schlüssel implementieren GetHashCode() und Equals() richtig. Die grundlegenden Regeln sind, dass GetHashCode() muss wieder den gleichen Wert für die Lebensdauer des Objekts, und dass Equals() muss true zurückgeben, wenn zwei Instanzen repräsentieren das gleiche Objekt. Es sei denn, Sie überschrieben, Equals() verwendet Referenz-Gleichheit - was bedeutet, es gibt nur true, wenn zwei Objekte sind tatsächlich die gleiche Instanz. Können Sie außer Kraft setzen, wie Equals() geht, aber dann müssen Sie sicherstellen, dass zwei Objekte "gleich" auch erzeugen, die denselben hash-code.

Vom performance-Standpunkt aus, können Sie auch wollen, um eine Umsetzung der GetHashCode() erzeugt, dass eine gute Streuung der Werte zu reduzieren, die Häufigkeit der hashcode Kollision. Der Nachteil vor allem von hashcode Kollisionen, ist, dass es reduziert das Wörterbuch in eine Liste in Bezug auf Leistung. Wenn zwei verschiedene Instanzen ergeben die gleiche hash-code, in dem Sie gespeichert sind, die gleichen internen Eimer Wörterbuch. Das Ergebnis ist, daß ein linear-scan durchgeführt werden müssen, ruft Equals() auf jeden Fall, bis eine übereinstimmung gefunden wird.

InformationsquelleAutor der Antwort LBushkin

Biete ich eine alternative code-orientierte Antwort, die zeigt, ein Wörterbuch zu zeigen-Ausnahme-Kostenlose und funktional korrekt Verhalten, wenn zwei Elemente mit verschiedenen Schlüsseln Hinzugefügt werden, aber die Tasten führen zu den gleichen hashcode.

Auf .Net 4.6 die Saiten "699391" und "1241308" produzieren den gleichen hashcode. Was passiert im folgenden code?

myDictionary.Add( "699391", "abc" );
myDictionary.Add( "1241308", "def" );

Dem folgenden code wird veranschaulicht, dass ein .Net-Wörterbuch akzeptiert verschiedene Schlüssel, die zu einer hash-Kollision. Es wird keine exception geworfen und dictionary-Schlüssel-lookup gibt die erwartete Objekt.

var hashes = new Dictionary<int, string>();
var collisions = new List<string>();

for (int i = 0; ; ++i)
{
    string st = i.ToString();
    int hash = st.GetHashCode();

    if (hashes.TryGetValue( hash, out string collision ))
    {
        //On .Net 4.6 we find "699391" and "1241308".
        collisions.Add( collision );
        collisions.Add( st );
        break;
    }
    else
        hashes.Add( hash, st );
}
Debug.Assert( collisions[0] != collisions[1], "Check we have produced two different strings" );
Debug.Assert( collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode" );

var newDictionary = new Dictionary<string, string>();
newDictionary.Add( collisions[0], "abc" );
newDictionary.Add( collisions[1], "def" );

Console.Write( "If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value." );

Debug.Assert( newDictionary[collisions[0]] == "abc" );
Debug.Assert( newDictionary[collisions[1]] == "def" );

InformationsquelleAutor der Antwort camelCase

Ich glaube, es wird die Größe des zugrunde liegenden array doppelt so groß, dann re-hashes und wird wahrscheinlich ein offener Eimer.

InformationsquelleAutor der Antwort Jesse C. Slicer