Сравнение объектов в C#.NET

C#.NET предлагает множество способов сравнить объекты, как экземпляры классов, так и структур. Способов так много, что без упорядочения этих способов и понимания их грамотного использования и имплементации (при наличии возможности переопределения), в голове, неминуемо, образуется каша.

Итак, класс System.Object предлагает следующие методы:
  • public static bool ReferenceEquals(object objA, object objB)
    {
        return objA == objB;
    }
             

  • public static bool Equals(object objA, object objB)
    {
        return objA == objB || (objA != null && objB != null && objA.Equals(objB));
    }
             

  • public virtual bool Equals(object obj)
    {
        return RuntimeHelpers.Equals(this, obj);
    }
             


Ну и, конечно:
public static bool operator == (Foo left, Foo right);

Также имеется возможность наследования IEquatable, IStructuralEquatable.

ReferenceEquals

Метод ReferenceEquals сравнивает две ссылки. Если ссылки на объекты идентичны, то возвращает true. Это значит, что данный метод проверяет экземпляры не на равенство, а на тождество. В случае передачи этому методу экземпляров значимого типа (даже если передать один и тот же экземпляр) всегда будет возвращать false. Так произойдёт потому, что при передаче произойдёт упаковка значимых типов и ссылки на них будут разные.
Здесь также хотелось бы упомянуть о сравнение двух строк этим методом. Например:
class Program
    {
        static void Main(string[] args)
        {
            string a = "Hello";
            string b = "Hello";

            if(object.ReferenceEquals(a,b))
                Console.WriteLine("Same objects");
            else
                Console.WriteLine("Not the same objects");

            Console.ReadLine();
        }
    }

Такая программа, запросто может вывести «Same objects». Не стоит переживать, это связано с интернированием строк. Но это совсем другая история и здесь об этом речи идти не будет.

public static bool Equals(object objA, object objB)

Сначала этот метод проверяет экземпляры на тождество и если объекты не тождественны, то проверяет их на null и делегирует ответственность за компарацию переопределяемому экземплярному методу Equals.

public virtual bool Equals(object obj)

По умолчанию, этот метод ведёт себя точно также как ReferenceEquals. Однако для значимых типов он переопределён и в System.ValueType выглядит следующим образом:
public override bool Equals(object obj)
		{
			if (obj == null)
			{
				return false;
			}
			RuntimeType runtimeType = (RuntimeType)base.GetType();
			RuntimeType left = (RuntimeType)obj.GetType();
			if (left != runtimeType)
			{
				return false;
			}
			if (ValueType.CanCompareBits(this))
			{
				return ValueType.FastEqualsCheck(this, obj);
			}
			FieldInfo[] fields = runtimeType.GetFields(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);
			for (int i = 0; i < fields.Length; i++)
			{
				object obj2 = ((RtFieldInfo)fields[i]).InternalGetValue(this, false);
				object obj3 = ((RtFieldInfo)fields[i]).InternalGetValue(obj, false);
				if (obj2 == null)
				{
					if (obj3 != null)
					{
						return false;
					}
				}
				else
				{
					if (!obj2.Equals(obj3))
					{
						return false;
					}
				}
			}
			return true;
		}

Не дай бог никому пользоваться такой имплементацией на больших множествах. Разработчики BCL не могут знать какие значимые типы мы будем определять и проводят сравнение экземпляров значимых типов по их полям, используя рефлексию, заранее ничего не зная об этих полях. Разумеется, это не очень производительный способ сравнения. Поэтому, при использовании значимых типов, известных на этапе компиляции, необходимо переопределить этот метод, ибо кто лучше вас может знать как сравнить два разработанных вами объекта? Для ссылочных типов, без нужды сравнения двух экземпляров на манер значимых типов, переопределять этот метод необязательно.
Посмотрим на пример грамотного переопределения этого метода и сразу реализуем IEquatable:
class Vehicle:IEquatable<Vehicle>
    {
        protected int speed;
        public int Speed
        {
            get { return this.speed; }
            set { this.speed = value; }
        }

        protected string name;
        public string Name
        {
            get { return this.name; }
            set { this.name = value; }
        }

        public Vehicle(){}
        public Vehicle(int speed, string name)
        {
            this.speed = speed;
            this.name = name;
        }

        public override bool Equals(object other)
        {
            //Последовательность проверки должна быть именно такой.
            //Если не проверить на null объект other, то other.GetType() может выбросить //NullReferenceException.            
            if (other == null)
                return false;

            //Если ссылки указывают на один и тот же адрес, то их идентичность гарантирована.
            if (object.ReferenceEquals(this, other))
                return true;

            //Если класс находится на вершине иерархии или просто не имеет наследников, то можно просто
            //сделать Vehicle tmp = other as Vehicle; if(tmp==null) return false; 
            //Затем вызвать экземплярный метод, сразу передав ему объект tmp.
            if (this.GetType() != other.GetType()) 
                return false;                                                                        

            return this.Equals(other as Vehicle);
        }
        public bool Equals(Vehicle other)
        {
            if (other == null)
                return false;

            //Здесь сравнение по ссылкам необязательно.
            //Если вы уверены, что многие проверки на идентичность будут отсекаться на проверке по ссылке - //можно имплементировать.
            if (object.ReferenceEquals(this, other))
                return true;

            //Если по логике проверки, экземпляры родительского класса и класса потомка могут считаться равными,
            //то проверять на идентичность необязательно и можно переходить сразу к сравниванию полей.
            if (this.GetType() != other.GetType())
                return false;

            if (string.Compare(this.Name, other.Name, StringComparison.CurrentCulture) == 0 && this.speed.Equals(other.speed))
                return true;
            else
                return false;
        }        
    }

Комментарий про вершину иерархии в переопределении виртуального метода сделан не просто так. Если создать наследник класса Vehicle (например, Bike), который также будет иметь переопределённый виртуальный метод Equals, в котором не будет сравнения типов по GetType, а будет попытка приведения типа Bike tmp = other as Bike; if(tmp!=null) this.Equals(tmp); то в таком случае, следующий код может вызывать проблемы:
Vehicle vehicle = new Vehicle();
Bike bike = new Bike();

object vehicleObj = vehicle;
object bikeObject = bike;

bike.Equals(vehicleObj); //Базовый тип не сможет привестись к наследнику. Таким образом, может быть //нарушено свойство симметричности сравнения объектов


public static bool operator == (Foo left, Foo right)

Для значимых типов всегда следует переопределять, как и виртуальный Equals(). Для ссылочных типов лучше не переопределять, ибо, по умолчанию, от == на ссылочных типах ожидается поведение как у метода ReferenceEquals(). Так что, здесь всё просто.

IStructuralEquatable

IStructuralEquatable идёт рука об руку с интерфейсом IEqualityComparer. Интерфейс IStructuralEquatable реализуют такие классы как System.Array или System.Tuple. Как пишет Билл Вагнер, IStructuralEquality декларирует то, что тип может составлять более крупные объекты, которые имплементируют семантику значимых типов и вряд ли когда-либо нам потребуется его самостоятельно реализовывать. Хотя, что сложного в его реализации? Достаточно посмотреть на его реализацию в System.Array:
bool IStructuralEquatable.Equals(object other, IEqualityComparer comparer)
		{
			if (other == null)
			{
				return false;
			}
			if (object.ReferenceEquals(this, other))
			{
				return true;
			}
			Array array = other as Array;
			if (array == null || array.Length != this.Length)
			{
				return false;
			}
			for (int i = 0; i < array.Length; i++)
			{
				object value = this.GetValue(i);
				object value2 = array.GetValue(i);
				if (!comparer.Equals(value, value2))
				{
					return false;
				}
			}
			return true;
		}

Собственно, сначала проверяется тождественность объектов, затем производится приведение к одному типу и сравнение по длине. Если длинна равна, то тогда начинается поэлементное сравнение через делегирование ответственности за это сравнение интерфейсному (IEqualityComparer) методу Equals.

Вот, по сути, и всё, что можно сказать о сравнении объектов в C#.NET, но осталась ещё одна маленькая, но важная деталь: метод GetHashCode().

public virtual int GetHashCode()

В общем и целом, стандартная реализация этого метода ведёт себя как генератор уникального идентификатора. Минус такого подхода состоит в том, что одинаковые семантически объекты, могут возвращать разные hash-значения. Рихтер жалуется на то, что стандартная реализация ещё и низкопроизводительна. Грамотная реализация этого метода весьма проблематична. Необходимо высчитывать hash быстро и иметь большой разброс в результате, чтобы не случалось повторений на достаточно больших множествах. На самом деле, в большей части случаев, имплементации GetHashCode() донельзя простые. Везде производятся сдвиги, «побитовые или», или «исключающие или». Сам Рихтер приводит пример со структурой, имеющей два поля типа int. GetHashCode() он предлагает имплементировать примерно так:
internal sealed class Point
    {
        private int a;
        private int b;

        public override int  GetHashCode()
        {
            return a ^ b;
        }
    }

А вот как переопределён GetHasCode() в System.Char:
public override int GetHashCode()
		{
			return (int)this | (int)this << 16;
		}

Можно приводить много примеров и практически везде используются эвристические показатели для сдвигов, исключающих или и так далее.

При написании статьи были использованы небезызвестные источники:
J.Richter, CLR via C#
B. Wagner Effective C#
Также использовался свой опыт и источники в интернете, которые приводить особого смысла не имеет.


Перевод здесь
Поделиться публикацией

Комментарии 25

    +3
    Это не Рихтер рекомендует, а МСДН. Рихтер писал, почему это плохо.

    В данном случае плохо тем, что если а == b, то хеш-код у всех таких объектов будет 0.

    Рекоменуется теперь использовать какой-то такой алгоритм (на память не помню, каждый раз гуглю его заново):

    int A = простое число;
    int B = другое просто число;
    int hash = A;
    unchecked
    {
    hash = hash * B + field;
    }
      0
      Я уточню. В целях общего познания следует понимать, что строки (как, впрочем, и любые другие упорядоченные структуры данных) очень хорошо получается и рекомендуется хэшировать следующим образом.
      Если строка — S, то хэш должен получаться так. Фиксируем число R, число M и итерируемся по всем элементам строки S:
      hash -> (hash * R + S[i]) % M.
      (Если мы хэшируем строку не из чисел, а из более сложных элементов, то S[i] нужно заменить на S[i].GetHashCode())
      Иными словами, мы рассматриваем значение многочлена P(x) = S[0] * R^(n — 1) + S[1] * R^(n — 2) +… + S[n — 2] * R + S[n — 1] в точке R.
      Чем это хорошо? Тем, что если взять M большим, а R — таким числом, что его порядок по модулю M — велик, то это даст очень хороший расброс степений R^i по модулю R, соответственно хэш будет очень «случайный». Подробнее об этом можно почитать, например, в Кнуте.
      Ну и напоследок — хорошо себя зарекомендовал также полиномиальный хэш по модулю 2^32 (2^64) в точке, равной какому-нибудь большому простому числу — он работает немного быстрее, потому что можно забить на взятие по модулю и просто работать с переполнениями типа Int32 (Int64).
        0
        Нет, так не очень хорошо. Получается, что если у нас есть, например, бинарное дерево (каждый элемент T(a,b) содержит два элемента того же типа), то хэш-коды для деревьев T(T(a,b),T(c,d)) и T(T(a,c),T(b,d)) будут всегда одинаковы. Коммутативность проклятая… Я с этим намучился, когда строил хэш-коды для квадратиков в HashLife.
          0
          Ключевые слова в моём посте: упорядоченные структуры данных. То есть именно в таком виде полиномиальный хэш применим к массивам (векторам), спискам, строкам и т. п.
          А деревья хэшируются обычно так: в вашем случае, когда ровно два сына у каждой вершины — выпишем элементы дерева в ЛКП-обходе (левый сын-корень-правый сын) и захэшируем как массив.
            0
            Это, естественно, в случае, если мы различаем левого и правого сына. Если мы не различаем правого и левого сына, то делаем что-то похожее на полиномиальный хэш: hash[v] = S(hash[v->l], hash[v->r]) * R^d, где d — глубина вершины, а S(a, b) — симметричная нетривиальная функция от a, b. Например, подойдёт какой-нибудь (a + b)^2 + a^3 + b^3.
              0
              То есть, для вычисления хэш-кода только что сформированного дерева из двух поддеревьев, хэш-коды которых известны, вам придется лишний раз обойти левое поддерево, чтобы хотя бы пересчитать его элементы? Сложно будет, особенно, если многие поддеревья в дереве дублируются, и общее число элементов превышает 2^64… Но тоже лечится, если специально предусмотреть.
                0
                Нет, зачем? Видимо, если мы формируем хэш из деревьев l и r, и получаем дерево v, то hash[v] = hash[l] * R^[r->size() + 1] + v->value() * R^[r->size()] + hash[r], если степени числа R мы предподсчитали, то переход вышел за O(1).
                А про деревья, в которых 2^64 элементов. Научите такие целиком хранить с четырьмя гигабайтами оперативки? :-)
                  +1
                  Легко:
                  Tree tr=new Tree(null,null,1);
                  for(int i=0;i<128;i++) tr=new Tree(tr,tr,0);

                  Получите дерево с 2^128 листьев. Правда, во всех записано число 1, но если вы не собираетесь модифицировать деревья, а только строите новые, то оно работать будет. Например, может использоваться, как дерево какой-нибудь игры (каждый узел — своя ситуация, а ситуации, полученные в разных партиях, могут совпадать). И там качественная хэш-функция не помешает.
                    +1
                    Да. Только не забудьте напомнить, что size() вам придется хранить в самом дереве, чтобы не вычислять. Да и предпосчитать степени непросто, тут даже 2^64 элементов не нужно. Но за log(size) работать будет.
                    А еще вместе с hash-функцией можно хранить R^size() — и тогда действительно все решится за O(1). Но кто так в реальности делает?
                      0
                      А, понял что вы имели в виду под такими гигантскими деревьями :-)
                      Да, вы правы, проще всего хранить R^size(), оно пересчитывается за O(1).
                      Кто так делает в реальности? Не могу сказать, не знаю. Могу лишь сказать, что методика, по-видимому, очень эффективная. Могу сказать что в алгоритмическом программировании, например, в олимпиадном — это часто употребимая методика.
            0
            Это Bernstein Hash — простой в реализации, очень быстрый и дает хорошее распределение, правда мы у себя используем его модифицированную версию (описан там же, чуть ниже по ссылке).
            +1
            Решарпер умеет генерировать Equality members, за что ему большое спасибо. Нужно всего лишь отметить поля/свойства, которые вы хотите задействовать. Остается только не забыть обновить реализацию этих методов при добавлении новых полей.
              0
              Точно-точно. Хотел об этом написать. Возможно, добавлю в качестве апдейта.
              +1
              Небольшое дополнение про IEquatable.
              При вызове виртуального метода у типа-значения происходит его боксинг, а при вызове интерфейсного метода — нет. Интерфейс IEquatable был введен именно для возможности сравнения без лишних боксингов.
                +1
                Стоит отметить, что без четкого понимания для чего, и на что это повлияет, лучше не переопределять Equals и GetHashCode — можете добавить пару часов дебага тем, кто ваш класс будет использовать.

                ИМХО, лучшее руководство по GetHashCode:
                –3
                Пожалуйста, перестаньте трогать GetHashCode(). Он предназначается только для одного — генерирования хешей для словарей. Он не гарантирует уникальности и не может использоваться для проверки равенства и тождественности.
                  +3
                  Он может и применяться для проверки равенства в случае, если явное сравнение — дорогая операция, а взятие хэша — дешёвая. И только в случае положительно срабатывания мы в явную сравниваем элементы. Это часто употребимая методика — использовать в качестве компаратора (a.GetHashCode() == b.GetHashCode() && a == b)
                  (Я же правильно считаю, что в C#второй операнд коньюнкции не будет вычисляться, если первый false?)
                    –1
                    1. часто неизвестно кто и как будет использовать ваш класс, а меняя GetHashCode вы меняете поведение стандартных коллекций (HashSet, Dictionary), которые будут хранить инстансы этого класса — кого-то ждет сюрприз.

                    2. GetHashCode в .Net'е заведен только чтобы поддержать хэш таблицы, поэтому использовать его не по назначению ИМХО не очень правильно.

                    3. Если говорить об оптимизации сравнения: я б тогда уж завел отдельный метод что-то типа if(a.EqualsOptimized(b))
                      +3
                      Так я о чём и говорю. Ваш третий пункт я предлагаю реализовать как я указал выше — проверяя сначала равенство хэшей, а потом и самих объектов.
                      А насчёт первых двух. То, что в стандартных библиотеках метод GetHashCode() используется только для хэш-таблиц (в чём я, кстати, не уверен, но спорить не буду), не значит, что его нельзя ни для чего использовать. От хэша что в хэш-таблице, что в целях сравнения объектов требуется редкость коллизий и «случайность» распределения. Если мы гарантируем эти два свойства, то от перегрузки GetHashCode() не пострадают ни стандартный хэш-таблицы, они также будут нормально работать с нашими инстансами, ни предлагаемые мною плюшки от использования хэшей, например, в компараторах.
                      –4
                      Нет не может. Нет абсолютно никаких гарантий, что два различных обьекта будут иметь различные хэши.

                      Кстати, внутренние версии дотнетовских библиотек специально меняют алгоритм генерирования хешей при каждой компиляции, чтобы удостовериться, что хеш обьектов не используется при сравнении.
                        +2
                        Ещё раз. От хэш-функции никто не требует, чтобы разные объекты имели разные хэши. Более того, коллизии гарантированно будут, если пространство объектов имеет размер больше чем 2^32.
                        С другой стороны, если a.GetHashCode() != b.GetHashCode(), то a гарантированно не равно b. И это избавляет нас от необходимости делать дорогую проверку a == b, которую мы обязательно будем делать, но только в случае совпадания хэшей.

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

                        Можно поподробнее про это?
                          0
                          Ссылку на первоисточник уже привели. Я очень рекомендую с ней ознакомиться. Здесь же я приведу переведенное заключение:
                          GetHashCode спроектирован делать лишь одну вещь: балансировать хеш таблицу. Не используйте его в других целях:
                          * Он не представляет собой уникальный ключ обьекта — вероятность коллизии черезвычайно высока.
                          * Он не имеет никакой криптографической защиты, поэтому не пользуйтись им как частью цифровой подписи или пароля.
                          * У него не обязательно присутствуют корректирующие свойства нужные для контрольных сумм.


                          Можно поподробнее про это?

                          Пожалуйста:
                          The internal debug builds of the framework that we use to «eat our own dogfood» change the hash algorithm every day precisely to prevent people from building systems — even test systems — that rely on unreliable implementation details that are documented as subject to change at any time.
                  +2
                  Знаете, вы меня заинтересовали. Надо бы поразбираться, что там в MSDN'е про хэши вообще пишут. Второй и третий пункты мы не затрагиваем — я предлагаю лишь использовать первый пункт в качестве промежуточной проверки при сравнении. И честно — я не понимаю, почему они рекомендуют не использовать хэши ни для чего другого. Тем более, если мы их руками реализуем и гарантируем хорошее распределение — то есть сохраняем работоспособность хэш-таблицы. Да и взятие хэша действительно дешёвая операция, что до перегрузки, что после.

                  А насчёт смены алгоритмов высчитывания хэшей — тут я согласен, никак нельзя опираться на какие-то знания, о том как устроен неперегруженный хэш внутри фреймворка не стоит.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое