Хеш-код в словаре - PullRequest
Новая
       17

Хеш-код в словаре

2 голосов
/ 28 сентября 2010

Я играл со Словарём и наткнулся на следующий сценарий 

public class MyObject
{
    public string I { get; set; }
    public string J { get; set; }
    public string K { get; set; }

    public override int GetHashCode()
    {
        int hashCode = (I+J+K).GetHashCode();
        Debugger.Log(9, "INFO", hashCode.ToString() + System.Environment.NewLine);
        return hashCode;
    }
}
class Program
{
    static void Main(string[] args)
    {
        MyObject obj1 = new MyObject() { I = "Hello", J = "World" };
        MyObject obj2 = new MyObject() { I = "Hello", J = "World" };

        Dictionary<MyObject, string> collection = new Dictionary<MyObject, string>();
        collection.Add(obj1, "1");
        var result = collection[obj2]; // KeyNotFound exception here.
    }
}

У меня есть класс MyObject, который действует как ключ к словарю, и я переопределяю метод GetHashCode для возврата хэш-кода на основе значений, хранящихся в классе.

Таким образом, когда приведенный выше код выполняется, и obj1, и obj2 возвращают один и тот же хэш-код, но все же словарь выдает исключение KeyNotFound.

Есть причина, почему такое поведение?

Ответы [ 2 ]

7 голосов
/ 28 сентября 2010

В .NET GetHashCode используется совместно с методом Equals для определения равенства объектов в отношении хранения в коллекциях.

Обратите внимание, что хэш-таблица сложнее, чем просто отображение ключав один слот через хэш-код.Из-за природы хэш-кодов могут возникать коллизии, и на практике возникают do (хотя с хорошей хэш-функцией это не должно быть очень часто).Таким образом, большинство реализаций хеш-таблицы имеют дело со случаем двух разных объектов, генерирующих один и тот же хеш-код, и это часто достигается с помощью связанного списка в каждом «слоте» в хеш-таблице.Хеш-код используется для определения слота, а метод Equals используется для определения местонахождения объекта в связанном списке (в большинстве «стандартных» реализаций хеш-таблицы).

Словопредупреждение, однако: очень мало веских причин для переопределения встроенного поведения GetHashCode.Я нашел этот интересный SO-поток, обсуждающий GetHashCode и Equals, который стоит прочитать: Почему важно переопределить GetHashCode, если переопределен метод Equals? .В нем рассматриваются достоинства / недостатки изменения поведения, свойства хороших и плохих хеш-функций, обязательные свойства этих двух методов и другие полезности.

3 голосов
/ 28 сентября 2010

Вам необходимо переопределить Object.Equals.

Dictionary<TKey, TValue> и другие коллекции на основе хеш-функции рассматривают хеш-равенство как необходимое , но недостаточное условие полного равенства из-за возможности хеш-столкновений В вашем примере средство получения ключа находит правильное хеш-поле для поиска и даже рассматривает obj1 в качестве кандидата на полное равенство, но поскольку реализация по умолчанию Equals основана на равенстве ссылок, она отклоняется.

В идеале, внедрить IEquatable<T> в своем классе: 

public class MyObject : IEquatable<MyObject>
{
    public string I { get; set; }
    public string J { get; set; }
    public string K { get; set; }

    public override int GetHashCode()
    {
        // you might want to consider a better hash-function here.
        return (I + J + K).GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return base.Equals(obj as MyObject);
    }

    public bool Equals(MyObject other)
    {
        return other != null && other.I == I && other.J == J && other.K == K;
    }
}

Также имейте в виду, что хэш ключевого объекта не должен изменяться, пока он присутствует в словаре.

...