C # Функция хеширования для поиска словаря [дубликат]

Просто добавьте следующие ответы:

Если вы не переопределяете Equals, то по умолчанию используется сравнение ссылок объектов. То же самое относится к hashcode - приведение по умолчанию обычно основано на адресе памяти ссылки. Поскольку вы переопределили Equals, это означает, что правильное поведение заключается в сравнении того, что вы внедрили в Equals, а не в ссылках, поэтому вы должны сделать то же самое для hashcode.

Клиенты вашего класса ожидают, что хэш-код будет иметь схожую логику с методом equals, например, методы linq, которые используют IEqualityComparer, сначала сравнивают хэш-коды и только если они равны, они будут сравнивать Equals ( ), который может быть более дорогим для запуска, если бы мы не реализовали hashcode, у равного объекта, вероятно, будут разные хэш-коды (потому что они имеют другой адрес памяти) и будут ошибочно определены как не равные (Equals () даже не попадут ).

Кроме того, кроме проблемы, что вы не сможете найти свой объект, если вы использовали его в словаре (потому что он был вставлен одним хэш-кодом, и когда вы его ищете, хэш-код по умолчанию будет вероятно, будет отличаться, и снова Equals () даже не будет вызван, как объясняет Марк Гравелл в своем ответе, вы также вводите нарушение концепции словаря или хешета, которая не должна допускать идентичные ключи - вы уже заявили, что эти объекты по существу то же самое, когда вы переопределяете Equa поэтому вы не хотите, чтобы оба они были разными ключами в структуре данных, которые предполагают наличие уникального ключа. Но поскольку у них есть другой хэш-код, «тот же» ключ будет вставлен как другой.

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

    public int getHashCode()
    {
        PropertyInfo[] theProperties = this.GetType().GetProperties();
        int hash = 31;
        foreach (PropertyInfo info in theProperties)
        {
            if (info != null)
            {
                var value = info.GetValue(this,null);
                if(value != null)
                unchecked
                {
                    hash = 29 * hash ^ value.GetHashCode();
                }
            }
        }
        return hash;  
    }

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

   public override int GetHashCode()
   {
      return base.GetHashCode();
   }

(Конечно, я мог бы использовать #pragma, чтобы выключить предупреждение, но я предпочитаю этот способ.)

Если вы находитесь в том положении, в котором вы делаете , то, конечно, требования к производительности, чем все проблемы, упомянутые другими, применяются здесь. Самое главное - иначе вы получите неправильные результаты при извлечении элементов из хеш-набора или словаря: хеш-код не должен меняться в зависимости от времени жизни объекта (точнее, в течение времени, когда требуется хэш-код, например, ключ в словаре): например, следующее неверно, поскольку значение является общедоступным и поэтому может быть изменено извне в класс во время жизни экземпляра, поэтому вы не должны использовать его в качестве основы для хеш-кода:

   class A
   {
      public int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //WRONG! Value is not constant during the instance's life time
      }
   }    

С другой стороны, если значение не может быть изменено, это нормально использовать:

   class A
   {
      public readonly int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //OK  Value is read-only and can't be changed during the instance's life time
      }
   }

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

Наконец-то я нашел решение этой проблемы, когда я работал с NHibernate. Мой подход заключается в вычислении хеш-кода из идентификатора объекта. Идентификатор может быть установлен только с помощью конструктора, поэтому, если вы хотите изменить ID, что очень маловероятно, вам нужно создать новый объект с новым идентификатором и, следовательно, новый хэш-код. Этот подход лучше всего работает с GUID, потому что вы можете предоставить конструктор без параметров, который произвольно генерирует ID.

Это связано с тем, что фреймворк требует, чтобы два объекта, которые одинаковы, должны иметь один и тот же хэш-код. Если вы переопределите метод equals, чтобы выполнить специальное сравнение двух объектов, и оба объекта считаются одинаковыми с помощью метода, то хэш-код двух объектов также должен быть одинаковым. (Словари и Hashtables полагаются на этот принцип).

Хэш-код используется для коллекций на основе хэша, таких как Dictionary, Hashtable, HashSet и т. д. Цель этого кода - очень быстро предварительно сортировать конкретный объект, помещая его в определенную группу (ведро). Эта предварительная сортировка очень помогает в поиске этого объекта, когда вам нужно вернуть его из коллекции хешей, потому что код должен искать ваш объект только в одном ведро, а не во всех его объектах. Лучшее распределение хэш-кодов (лучшая уникальность) - более быстрое извлечение. В идеальной ситуации, когда каждый объект имеет уникальный хеш-код, поиск его является операцией O (1). В большинстве случаев он приближается к O (1).

У нас есть две проблемы, с которыми можно справиться.

1. Вы не можете предоставить разумный GetHashCode(), если любое поле в объекте может быть изменено. Также часто объект никогда не будет использоваться в коллекции, которая зависит от GetHashCode(). Таким образом, стоимость реализации GetHashCode() часто не стоит того, или это невозможно.
2. Если кто-то помещает ваш объект в коллекцию, которая вызывает GetHashCode(), и вы переопределили Equals(), не делая GetHashCode() ведут себя корректно, этот человек может потратить дни на отслеживание проблемы.

Поэтому по умолчанию я делаю.

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Some comment to explain if there is a real problem with providing GetHashCode() 
        // or if I just don't see a need for it for the given class
        throw new Exception("Sorry I don't know what GetHashCode should do for this class");
    }
}

Пожалуйста, не забудьте проверить параметр obj против null при переопределении Equals(). А также сравните тип.

public override bool Equals(object obj)
{
    if (obj == null || GetType() != obj.GetType())
        return false;

    Foo fooItem = obj as Foo;

    return fooItem.FooId == this.FooId;
}

Причиной этого является: Equals должен возвращать false при сравнении с null. См. Также http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx

Завершая Equals, вы в основном заявляете, что именно тот, кто лучше знает, как сравнивать два экземпляра данного типа, так что вы, вероятно, будете лучшим кандидатом для предоставления лучшего хеш-кода.

Это пример того, как ReSharper пишет для вас функцию GetHashCode ():

public override int GetHashCode()
{
    unchecked
    {
        var result = 0;
        result = (result * 397) ^ m_someVar1;
        result = (result * 397) ^ m_someVar2;
        result = (result * 397) ^ m_someVar3;
        result = (result * 397) ^ m_someVar4;
        return result;
    }
}

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

Как насчет:

public override int GetHashCode()
{
    return string.Format("{0}_{1}_{2}", prop1, prop2, prop3).GetHashCode();
}

Предполагая, что производительность не является проблемой:)

Я понимаю, что исходный GetHashCode () возвращает адрес памяти объекта, поэтому необходимо переопределить его, если вы хотите сравнить два разных объекта.

EDITED: это неверно, исходный метод GetHashCode () не может гарантировать равенство двух значений. Хотя объекты, которые равны, возвращают один и тот же хэш-код.