Словарь поврежден или GetHashCode () должен основываться только на неизменяемых членах? - PullRequest
Новая
       13

Словарь поврежден или GetHashCode () должен основываться только на неизменяемых членах?

12 голосов
/ 02 февраля 2011

Когда объект добавляется в класс .NET System.Collections.Generic.Dictionary , хэш-код ключа сохраняется внутри и используется для последующих сравнений.Когда хэш-код изменяется после его первоначальной вставки в словарь, он часто становится «недоступным» и может удивить своих пользователей, когда проверка существования, даже используя ту же ссылку, возвращает false (пример кода ниже).

* GetHashCode документация гласит:

Метод GetHashCode для объекта должен последовательно возвращать один и тот же хэш-код, если нет изменения состояния объекта, определяющего возвращаемое значение объекта Equalsmethod.

Итак, согласно документам GetHashCode, хеш-код может изменяться всякий раз, когда изменяется состояние, определяющее равенство равенства , однако реализация Dictionary не поддерживает это.

Не нарушена ли текущая реализация словаря .NET из-за неправильного игнорирования разрешений хэш-кода?Должен ли GetHashCode() быть основан только на неизменных членах?Или есть что-то еще, чтобы нарушить возможную ложную дихотомию? 

class Hashable
{
    public int PK { get; set; }

    public override int GetHashCode()
    {
        if (PK != 0) return PK.GetHashCode();
        return base.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return Equals(obj as Hashable);
    }

    public virtual bool Equals(Hashable other)
    {
        if (other == null) return false;
        else if (ReferenceEquals(this, other)) return true;
        else if (PK != 0 && other.PK != 0) return Equals(PK, other.PK);
        return false;
    }

    public override string ToString()
    {
        return string.Format("Hashable {0}", PK);
    }
}

class Test
{
    static void Main(string[] args)
    {
        var dict = new Dictionary<Hashable, bool>();
        var h = new Hashable();
        dict.Add(h, true);

        h.PK = 42;
        if (!dict.ContainsKey(h)) // returns false, despite same reference
            dict.Add(h, false);
    }
}

Ответы [ 2 ]

27 голосов
/ 02 февраля 2011

Нет, вы просто не должны изменять ключ (материальным способом) после вставки его в словарь.Это сделано специально для каждого хэш-таблицы, который я когда-либо использовал.Документы даже указывают это:

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

Так что это только удивит пользователей, которые не читают документацию:)

9 голосов
/ 02 февраля 2011

Чтобы добавить к ответу Джона, я бы просто добавил акцент на определенную часть документов, которые вы цитировали:

Метод GetHashCode для объекта должен последовательно возвращать тот же хеш-код, поканет никакого изменения в состоянии объекта , которое определяет возвращаемое значение метода Equals объекта .

Теперь, прямо здесь вы нарушили правила.Вы изменили PK, что не влияет на результат Equals (потому что у вас там есть ReferenceEquals проверка), но результат вашего GetHashCode влияет менять.Так что это простой ответ.

Используя более концептуальный подход, я думаю, вы можете посмотреть на это так: если у вас есть переопределенное поведение Equals и GetHashCode для вашего типазатем вы взяли на себя ответственность за понятие , что означает, что один экземпляр этого типа равен другому .И на самом деле вы определили его таким образом, что объект Hashable можно заменить на что-то совершенно другое ;то есть что-то, что больше нельзя использовать таким же образом, как это было раньше (потому что его хеш-код изменился).

Рассматривается с этой точки зрения после того, как вы выполните dict.Add(h, true), а затем измените h.PK,словарь больше не содержит объект, на который ссылается h.Он содержит что-то иначе (которого на самом деле нигде нет).Это похоже на тип, который вы определили как змея, которая сбросила свою кожу.

...