Как C# определяет хеш-код объекта?
https://stackoverflow.com/questions/102690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Этот вопрос вытекает из дискуссии кортежи.
Я начал думать о хэш-коде, который должен иметь кортеж.Что, если мы примем класс KeyValuePair как кортеж?Он не переопределяет метод GetHashCode(), поэтому, вероятно, он не будет знать хеш-коды своих «дочерних элементов»...Таким образом, во время выполнения будет вызываться Object.GetHashCode(), который не знает о реальной структуре объекта.
Затем мы можем создать два экземпляра некоторого ссылочного типа, которые на самом деле равны, из-за перегруженных GetHashCode() и Equals().И используйте их как «детей» в кортежах, чтобы «обмануть» словарь.
Но это не работает!Среда выполнения каким-то образом определяет структуру нашего кортежа и вызывает перегруженный GetHashCode нашего класса!
Как это работает?Какой анализ выполняет Object.GetHashCode()?
Может ли это повлиять на производительность в каком-то плохом сценарии, когда мы используем сложные клавиши?(вероятно, невозможный сценарий...но все равно)
Рассмотрим этот код в качестве примера:
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;
}
}
}
Обновлять Я думаю, что нашел этому объяснение, как указано ниже в моем ответе.Основными результатами этого являются:
- Будьте осторожны со своими ключами и их хеш-кодами :-)
- Для сложных ключей словаря необходимо правильно переопределить Equals() и GetHashCode().
Решение 4
Кажется, теперь я имею представление.
Я думал, что 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;
}
}
}
Другие советы
Не переопределяйте GetHashcode() и Equals() для изменяемых классов, переопределяйте их только для неизменяемых классов или структур, иначе, если вы измените объект, используемый в качестве ключа, хеш-таблица больше не будет работать должным образом (вы не сможете получить значение, связанное с ключом, после изменения объекта ключа)
Кроме того, хэш-таблицы не используют хэш-коды для идентификации объектов. Они используют сами ключевые объекты в качестве идентификаторов. Не требуется, чтобы все ключи, которые используются для добавления записей в хеш-таблицу, возвращали разные хеш-коды, но рекомендуется это делать, иначе производительность сильно страдает.
Вот правильные реализации хэша и равенства для кортежа Quad (содержит 4 компонента кортежа внутри).Этот код обеспечивает правильное использование этого конкретного кортежа в HashSets и словарях.
Подробнее по теме (включая исходный код) здесь.
Примечание использование непроверенный ключевое слово (во избежание переполнения) и выдача 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);
}
Проверьте это почта Брэда Абрамса, а также комментарий Брайана Грункемейера для получения дополнительной информации о том, как работает object.GetHashCode.Также взгляните на первый комментарий в блоге Аянде. почта.Я не знаю, следуют ли текущие версии Framework этим правилам или они действительно изменили их, как подразумевал Брэд.
У меня больше нет ссылки на книгу, и мне придется найти ее, чтобы подтвердить, но я думал, что базовый хеш по умолчанию просто хэшировал все члены вашего объекта.Он получил к ним доступ благодаря тому, как работала CLR, поэтому вы не могли писать так же хорошо, как они.
Это полностью по памяти о чем-то, что я кратко прочитал, так что принимайте это как хотите.
Редактировать: Книга была Внутри С# из «МС Пресс».Тот, с пилой на крышке.Автор потратил много времени, объясняя, как все было реализовано в CLR, как язык транслировался в MSIL и т. д.т. д.Если вы сможете найти книгу, то ее можно прочитать неплохо.
Редактировать: Сформируйте ссылку, если она имеет вид
Object.gethashcode () использует внутреннее поле в классе System.Object для генерации значения хэша.Каждому созданному объекту присваивается уникальный ключ объекта, хранящийся как целое число, когда он создается.Эти ключи начинаются с 1 и приращения каждый раз, когда создается новый объект любого типа.
Хм, думаю, мне нужно написать несколько собственных хеш-кодов, если я планирую использовать объекты в качестве хэш-ключей.
так что, вероятно, он не будет знать хеш-коды своих «детей».
Кажется, ваш пример доказывает обратное :-) Хэш-код ключа MyClass и ценность 1 одинаково для обоих KeyValuePairх.Реализация 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;
}
}
По сути...в случае моего примера вы бы хотели, чтобы два объекта, находящиеся на одинаковом расстоянии, возвращали «истину» для Equals, но возвращали разные хэш-коды.
