Вопрос по c#, internals, hash – Как C # выяснить хеш-код для объекта?

12

Этот вопрос выходит из обсуждениякортежи.

Я начал думать о хэш-коде, который должен иметь кортеж. Что если мы примем класс KeyValuePair в качестве кортежа? Он не переопределяет метод GetHashCode (), поэтому, вероятно, он не будет знать о хэш-кодах его 'children' ... Таким образом, во время выполнения будет вызываться Object.GetHashCode (), который не является знать о реальной структуре объекта.

Затем мы можем сделать два экземпляра некоторого ссылочного типа, которые на самом деле равны, из-за перегруженных GetHashCode () и Equals (). И использовать их как «детей» в кортежах для «обмана» словарь.

Но это не работает! Во время выполнения каким-то образом выясняется структура нашего кортежа и вызывается перегруженный GetHashCode нашего класса!

Как это работает? Что такое анализ, выполненный Object.GetHashCode ()?

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

Рассмотрим этот код в качестве примера:

<code>namespace csharp_tricks
{
    class Program
    {
        class MyClass
        {
            int keyValue;
            int someInfo;

            public MyClass(int key, int info)
            {
                keyValue = key;
                someInfo = info;
            }

            public override bool Equals(object obj)
            {
                MyClass other = obj as MyClass;
                if (other == null) return false;

                return keyValue.Equals(other.keyValue);
            }

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

        static void Main(string[] args)
        {
            Dictionary<object, object> dict = new Dictionary<object, object>();

            dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 1), 1), 1);

            //here we get the exception -- an item with the same key was already added
            //but how did it figure out the hash code?
            dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 2), 1), 1); 

            return;
        }
    }
}
</code>

Update Я думаю, что нашел объяснение этому, как указано ниже в моем ответе. Основными результатами этого являются:

Be careful with your keys and their hash codes :-) For complicated dictionary keys you must override Equals() and GetHashCode() correctly.
Это отличная статья о GetHashCode из Effective C #:awprofessional.com/content/images/0321245660/items/… torial

Ваш Ответ

6   ответов
1

Я думал, что KeyValuePair является ссылочным типом, но это не так, это структура. И поэтому он использует метод ValueType.GetHashCode (). В MSDN указано: «Одно или несколько полей производного типа используются для вычисления возвращаемого значения».

Если вы возьмете реальный ссылочный тип в качестве «провайдера кортежей» Вы будете обманывать словарь (или себя ...).

using System.Collections.Generic;

namespace csharp_tricks
{
    class Program
    {
        class MyClass
        {
            int keyValue;
            int someInfo;

            public MyClass(int key, int info)
            {
                keyValue = key;
                someInfo = info;
            }

            public override bool Equals(object obj)
            {
                MyClass other = obj as MyClass;
                if (other == null) return false;

                return keyValue.Equals(other.keyValue);
            }

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

        class Pair<T, R>
        {
            public T First { get; set; }
            public R Second { get; set; }
        }

        static void Main(string[] args)
        {
            var dict = new Dictionary<Pair<int, MyClass>, object>();

            dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 2) }, 1);

            //this is a pair of the same values as previous! but... no exception this time...
            dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 3) }, 1);

            return;
        }
    }
}
2

сообщение Брэд Абрамс, а также комментарий Брайана Грюнкемейера для получения дополнительной информации о том, как работает object.GetHashCode. Кроме того, взгляните на первый комментарий в блоге Аянде.сообщение, Я не знаю, соответствуют ли текущие версии Framework этим правилам или они действительно изменили его, как подразумевал Брэд.

Эти объяснения также противоречат приведенному коду. Каким-то образом время выполнения попадает внутрь MyClass.GetHashCode () и использует его для получения хеш-кода KeyValuePair. Но что именно делает время выполнения? Max Galkin
-1

t be aware of the hash codes of it's "children".

Ваш пример, кажется, доказывает обратное :-) Хеш-код для ключаMyClass и значение1 одинаково для обоихKeyValuePair's. Реализация KeyValuePair должна использовать обаKey а такжеValue для своего собственного хэш-кода

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

Рассмотрим более сложный случай:

public class HappyClass
{

    enum TheUnit
    {
        Points,
        Picas,
        Inches
    }

    class MyDistanceClass
    {
        int distance;
        TheUnit units;

        public MyDistanceClass(int theDistance, TheUnit unit)
        {
            distance = theDistance;

            units = unit;
        }
        public static int ConvertDistance(int oldDistance, TheUnit oldUnit, TheUnit newUnit)
        {
            // insert real unit conversion code here :-)
            return oldDistance * 100;
        }

        /// <summary>
        /// Figure out if we are equal distance, converting into the same units of measurement if we have to
        /// </summary>
        /// <param name="obj">the other guy</param>
        /// <returns>true if we are the same distance</returns>
        public override bool Equals(object obj)
        {
            MyDistanceClass other = obj as MyDistanceClass;
            if (other == null) return false;

            if (other.units != this.units)
            {
                int newDistance = MyDistanceClass.ConvertDistance(other.distance, other.units, this.units);
                return distance.Equals(newDistance);
            }
            else
            {
                return distance.Equals(other.distance);
            }


        }

        public override int GetHashCode()
        {
            // even if the distance is equal in spite of the different units, the objects are not
            return distance.GetHashCode() * units.GetHashCode();
        }
    }
    static void Main(string[] args)
    {

        // these are the same distance... 72 points = 1 inch
        MyDistanceClass distPoint = new MyDistanceClass(72, TheUnit.Points);
        MyDistanceClass distInch = new MyDistanceClass(1, TheUnit.Inch);

        Debug.Assert(distPoint.Equals(distInch), "these should be true!");
        Debug.Assert(distPoint.GetHashCode() != distInch.GetHashCode(), "But yet they are fundimentally different values");

        Dictionary<object, object> dict = new Dictionary<object, object>();

        dict.Add(new KeyValuePair<MyDistanceClass, object>(distPoint, 1), 1);

        //this should not barf
        dict.Add(new KeyValuePair<MyDistanceClass, object>(distInch, 1), 1);

        return;
    }

}

В основном ... в моем примере вы хотели бы, чтобы два объекта с одинакового расстояния возвращали "true" для Равных, но все же вернуть разные хэш-коды.

KeyValuePair не реализует GetHashCode. Ваш пример совершенно неверен. Откройте MSDN: если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одинаковое значение. Max Galkin
3

4 компонента кортежа внутри). Этот код обеспечивает правильное использование этого конкретного кортежа в HashSets и словарях.

Подробнее по теме (включая исходный код)Вот.

Note использованиеunchecked ключевое слово (чтобы избежать переполнения) и выбрасывание NullReferenceException, если obj имеет значение null (как требуется базовым методом)

public override bool Equals(object obj)
{
    if (ReferenceEquals(null, obj))
        throw new NullReferenceException("obj is null");
    if (ReferenceEquals(this, obj)) return true;
    if (obj.GetType() != typeof (Quad<T1, T2, T3, T4>)) return false;
    return Equals((Quad<T1, T2, T3, T4>) obj);
}

public bool Equals(Quad<T1, T2, T3, T4> obj)
{
    if (ReferenceEquals(null, obj)) return false;
    if (ReferenceEquals(this, obj)) return true;
    return Equals(obj.Item1, Item1)
        && Equals(obj.Item2, Item2)
            && Equals(obj.Item3, Item3)
                && Equals(obj.Item4, Item4);
}

public override int GetHashCode()
{
    unchecked
    {
        int result = Item1.GetHashCode();
        result = (result*397) ^ Item2.GetHashCode();
        result = (result*397) ^ Item3.GetHashCode();
        result = (result*397) ^ Item4.GetHashCode();
        return result;
    }
}
public static bool operator ==(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
    return Equals(left, right);
}


public static bool operator !=(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right)
{
    return !Equals(left, right);
}
+1 для правильной реализации GetHashCode, однако я считаю, что вы не должны вызывать исключение из Equals (объект) - эта реализация также несовместима: quad.Equals (null) генерирует исключение NullReferenceException, а quad.Equals ((Quad) null) возвращает ложный :-).
14

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

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

Хорошо, но это не ответ. Max Galkin
Но как они могли идентифицировать объект, не генерируя хеш? Разве не в этом смысл GetHashCode?
... (если ключ равен ключу из этого сегмента), то возвращается значение, в противном случае позиция перефразируется и проверяется другое местоположение. Алгоритм завершается, когда исследуемый сегмент пуст или проверяются все сегменты.
Таким образом, хеш-код указывает не значение, а первую позицию в хеш-таблице, в которой следует искать ключ.
Кори, хеш-код ключа - это число, используемое для быстрого вычисления местоположения сегмента в хэш-таблице (сегмент представляет собой пару ключ-значение или несколько пар kv) после вычисления местоположения, если блок содержит ключ ( проверка на равенство) ...
0

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

Это полностью из памяти чего-то, что я кратко прочитал, так что принимайте это как хотите.

Edit: Книга былаInside C# из MS Press. Тот, с лезвием пилы на обложке. Автор потратил много времени на объяснение того, как все было реализовано в CLR, как язык перешел на MSIL и т. Д. ЭСТ. Если вы можете найти книгу, это не плохое чтение.

Edit: Форма ссылки при условии, что это выглядит

Object.GetHashCode() uses an internal field in the System.Object class to generate the hash value. Each object created is assigned a unique object key, stored as an integer,when it is created. These keys start at 1 and increment every time a new object of any type gets created.

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

Это объяснение противоречит примеру кода в вопросе. Max Galkin

Похожие вопросы