Object.GetHashCode
Мой вопрос может дублировать реализацию по умолчанию для Object.GetHashCode(), но я спрашиваю снова, потому что я не понял принятого ответа на этот вопрос.
Для начала у меня есть три вопроса о принятом ответе на предыдущий вопрос, который цитирует некоторые документы следующим образом:
"Однако, поскольку этот индекс можно использовать повторно после восстановления объекта во время сборки мусора, можно получить один и тот же хэш-код для двух разных объектов".
Это правда? Мне кажется, что два объекта не будут иметь одинаковый хэш-код, потому что код объекта не используется повторно до тех пор, пока объект не будет собран (т.е. больше не существует).
"Кроме того, два объекта, представляющих одно и то же значение, имеют одинаковый хэш-код, только если они являются точно одинаковыми объектами".
Это проблема? Например, я хочу связать некоторые данные с каждым из экземпляров узла в дереве DOM. Для этого "узлы" должны иметь идентификатор или хеш-код, чтобы я мог использовать их в качестве ключей в словаре данных. Разве хеш-код, который определяет, является ли он "точно таким же объектом", то есть "ссылочным равенством, а не" равенством значений ", чего я хочу?
"Эта реализация не особенно полезна для хеширования, поэтому производные классы должны переопределять GetHashCode"
Это правда? Если это не хорошо для хеширования, то что, если что-то хорошо для этого, и почему это даже определяется как метод Object?
Мой последний (и, возможно, самый важный для меня) вопрос: если я должен изобрести / переопределить реализацию GetHashCode () для произвольного типа, который имеет семантику "ссылочного равенства", это следующая разумная и хорошая реализация:
class SomeType
{
//create a new value for each instance
static int s_allocated = 0;
//value associated with this instance
int m_allocated;
//more instance data
... plus other data members ...
//constructor
SomeType()
{
allocated = ++s_allocated;
}
//override GetHashCode
public override int GetHashCode()
{
return m_allocated;
}
}
редактировать
К вашему сведению, я проверил это, используя следующий код:
class TestGetHash
{
//default implementation
class First
{
int m_x;
}
//my implementation
class Second
{
static int s_allocated = 0;
int m_allocated;
int m_x;
public Second()
{
m_allocated = ++s_allocated;
}
public override int GetHashCode()
{
return m_allocated;
}
}
//stupid worst-case implementation
class Third
{
int m_x;
public override int GetHashCode()
{
return 0;
}
}
internal static void test()
{
testT<First>(100, 1000);
testT<First>(1000, 100);
testT<Second>(100, 1000);
testT<Second>(1000, 100);
testT<Third>(100, 100);
testT<Third>(1000, 10);
}
static void testT<T>(int objects, int iterations)
where T : new()
{
System.Diagnostics.Stopwatch stopWatch =
System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < iterations; ++i)
{
Dictionary<T, object> dictionary = new Dictionary<T, object>();
for (int j = 0; j < objects; ++j)
{
T t = new T();
dictionary.Add(t, null);
}
for (int k = 0; k < 100; ++k)
{
foreach (T t in dictionary.Keys)
{
object o = dictionary[t];
}
}
}
stopWatch.Stop();
string stopwatchMessage = string.Format(
"Stopwatch: {0} type, {1} objects, {2} iterations, {3} msec",
typeof(T).Name, objects, iterations,
stopWatch.ElapsedMilliseconds);
System.Console.WriteLine(stopwatchMessage);
}
}
На моей машине результаты / вывод следующие:
First type, 100 objects, 1000 iterations, 2072 msec
First type, 1000 objects, 100 iterations, 2098 msec
Second type, 100 objects, 1000 iterations, 1300 msec
Second type, 1000 objects, 100 iterations, 1319 msec
Third type, 100 objects, 100 iterations, 1487 msec
Third type, 1000 objects, 10 iterations, 13754 msec
Моя реализация занимает половину времени по умолчанию (но мой тип больше на размер моего члена данных m_allocated).
Моя реализация и реализация по умолчанию масштабируются линейно.
Для сравнения и проверки работоспособности глупая реализация начинается плохо и масштабируется хуже.
3 ответа
Самое важное свойство, которое должна иметь реализация хеш-кода, это:
Если два объекта сравниваются как равные, то они должны иметь идентичные хэш-коды.
Если у вас есть класс, в котором экземпляры этого класса сравниваются по ссылочному равенству, вам не нужно переопределять GetHashCode; реализация по умолчанию гарантирует, что два объекта с одинаковыми ссылками имеют одинаковый хеш-код. (Вы вызываете один и тот же метод дважды для одного и того же объекта, поэтому, конечно, результат один и тот же.)
Если вы написали класс, который реализует свое собственное равенство, отличное от ссылочного равенства, тогда вам НЕОБХОДИМО переопределить GetHashCode так, чтобы два объекта, которые сравнивались как равные, имели равные хеш-коды.
Теперь вы можете сделать это, просто возвращая ноль каждый раз. Это было бы паршивой хэш-функцией, но это было бы законно.
Другие свойства хороших хеш-функций:
GetHashCode никогда не должен выдавать исключение
Изменяемые объекты, которые сравниваются на равенство в своем изменяемом состоянии, и, следовательно, хэш в своем изменяемом состоянии, опасно подвержены ошибкам. Вы можете поместить объект в хеш-таблицу, изменить его и не сможете снова его получить. Старайтесь никогда не хэшировать или сравнивать на равенство в изменчивом состоянии.
GetHashCode должен быть очень быстрым - помните, цель хорошего алгоритма хеширования - повысить производительность поиска. Если хеш медленный, то поиск не может быть сделан быстро.
Объекты, которые не сравниваются как равные, должны иметь разные хеш-коды, хорошо распределенные по всему диапазону 32-битного целого
Вопрос:
Это правда? Мне кажется, что два объекта не будут иметь одинаковый хэш-код, потому что код объекта не используется повторно до тех пор, пока объект не будет собран (т.е. больше не существует).
Два объекта могут совместно использовать один и тот же хэш-код, если он генерируется реализацией GetHashCode по умолчанию, потому что:
- Результат GetHashCode по умолчанию не должен изменяться при жизни объекта, и реализация по умолчанию гарантирует это. Если бы это могло измениться, такие типы как Hashtable не могли бы иметь дело с этой реализацией. Это потому, что ожидается, что хеш-код по умолчанию является хеш-кодом уникального идентификатора экземпляра (даже если такого идентификатора нет:)).
- Диапазон значений GetHashCode - диапазон целых чисел (2^32).
Вывод: достаточно выделить 2 ^ 32 объектов с сильными ссылками (должно быть легко в Win64), чтобы достичь предела.
Наконец, в object.GetHashCode имеется явный оператор : ссылка на MSDN: реализация по умолчанию метода GetHashCode не гарантирует уникальные возвращаемые значения для разных объектов. Кроме того,.NET Framework не гарантирует реализацию по умолчанию метода GetHashCode, и возвращаемое значение будет одинаковым для разных версий.NET Framework. Следовательно, реализация по умолчанию этого метода не должна использоваться в качестве уникального идентификатора объекта для целей хеширования.
На самом деле вам не нужно ничего менять в классе, который требует только ссылочного равенства.
Кроме того, формально, это не очень хорошая реализация, поскольку она имеет плохое распространение. Хеш-функция должна иметь разумное распределение, поскольку она улучшает распределение хеш-сегментов и, косвенно, производительность в коллекциях, которые используют хеш-таблицы. Как я уже сказал, это формальный ответ, одно из руководящих принципов при разработке хэш-функции.