Object.GetHashCode
Мой вопрос может дублировать реализацию по умолчанию для Object.GetHashCode(), но я снова спрашиваю, потому что я не понял принятого ответа на этот вопрос.
Для начала у меня есть три вопроса о принятом ответе на предыдущий вопрос, который цитирует некоторые документы:
"Однако, поскольку этот индекс можно повторно использовать после восстановления объекта во время сбора мусора, можно получить тот же хэш-код для двух разных объектов."
Это правда? Мне кажется, что два объекта не будут иметь один и тот же хэш-код, потому что объектный код не используется повторно, пока объект не будет собран мусором (т.е. Больше не существует).
"Кроме того, два объекта, которые представляют одно и то же значение, имеют один и тот же хэш-код, только если они являются одним и тем же объектом."
Это проблема? Например, я хочу связать некоторые данные с каждым из экземпляров node в дереве 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;
}
}
Edit
FYI Я протестировал его, используя следующий код:
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).
Моя реализация и реализация по умолчанию масштабируются линейно.
В сравнении и как проверка здравомыслия, глупая реализация начинает плохо и ухудшается.
Ответы
Ответ 1
Самое важное свойство, которое должно иметь реализация хэш-кода, следующее:
Если два объекта сравниваются как равные, то они должны иметь одинаковые хэш-коды.
Если у вас есть класс, где экземпляры класса сравниваются по ссылочному равенству, тогда вам не нужно переопределять GetHashCode; реализация по умолчанию гарантирует, что два объекта, которые являются одной и той же ссылкой, имеют один и тот же хэш-код. (Вы дважды вызываете один и тот же метод на одном и том же объекте, поэтому, конечно, результат тот же.)
Если вы написали класс, который реализует свое собственное равенство, отличное от ссылочного равенства, вы НЕОБХОДИМО переопределить GetHashCode таким образом, чтобы два объекта, которые сравниваются как равные, имеют одинаковые хэш-коды.
Теперь вы можете сделать это, просто возвращая нуль каждый раз. Это будет паршивая хеш-функция, но это будет законно.
Другими свойствами хороших хэш-функций являются:
-
GetHashCode никогда не должен генерировать исключение
-
Переменные объекты, которые сравниваются для равенства в их изменяемом состоянии и, следовательно, хэш в их изменяемом состоянии, опасно подвержены ошибкам. Вы можете поместить объект в хеш-таблицу, изменить ее и не получить ее снова. Старайтесь никогда не хешировать или сравнивать для равенства в изменяемом состоянии.
-
GetHashCode должен быть очень быстрым - помните, что цель хорошего хеш-алгоритма - улучшить производительность поисковых запросов. Если хеш медленный, поиск не может быть выполнен быстро.
-
Объекты, которые не сравниваются как равные, должны иметь разные хэш-коды, хорошо распределенные по всему диапазону 32-битного целого числа
Ответ 2
Два объекта, которые сосуществуют во времени в одном и том же AppDomain, могут не иметь одного и того же хеш-кода, но объект, который создается, распечатывает хеш-код, а затем получает собранный мусор, может делиться хэш-кодом с другим объектом который создается позже.
На самом деле, я не уверен, откуда идет эта документация - документы для object.GetHashCode показывают это:
Стандартная реализация Метод GetHashCode не гарантирует уникальные возвращаемые значения для разных объекты. Кроме того,.NET Рамочная основа не гарантирует внедрение по умолчанию Метод GetHashCode и значение it возвращения будут одинаковыми между разные версии .NET. Фреймворк. Следовательно, значение по умолчанию реализация этого метода не должна использоваться как уникальный идентификатор объекта для целей хэширования.
Обратите внимание на первую часть о том, что она не является гарантией того, что она уникальна для разных значений.
Что касается бит о том, что он не является хорошим хеш-кодом - это не особенно важно для меня. Если вы хотите только ссылочного равенства, я думаю, что вы не можете переопределить GetHashCode/Equals.
Вы можете получить некоторые хеш-коллизии, но ИМО вряд ли будет значительным. Документы могут быть более четкими (я подозреваю, что часть о методе, который не используется как уникальный идентификатор объекта для целей хеширования, говорит о хэшировании для обеспечения безопасности), но я думаю, что все должно быть в порядке.
Ответ 3
Вопрос:
Это правда? Мне кажется, что у двух объектов не будет одинакового хеш-кода, потому что объектный код не используется повторно до тех пор, пока объект не будет собран мусором (т.е. больше не существует).
Два объекта могут совместно использовать один и тот же хэш-код, если он генерируется по умолчанию GetHashCode, потому что:
- Результат GetHashCode по умолчанию не должен изменяться во время жизни объекта, и реализация по умолчанию обеспечивает это. Если это может измениться, такие типы, как Hashtable, не могут справиться с этой реализацией. Это потому, что он ожидал, что хэш-код по умолчанию является хеш-кодом уникального идентификатора экземпляра (даже несмотря на отсутствие такого идентификатора:)).
- Диапазон значений GetHashCode - это диапазон целых чисел (2 ^ 32).
Вывод:
Этого достаточно, чтобы выделить 2 ^ 32 сильно привязанных объекта к (должно быть легко на Win64), чтобы достигнуть предела.
Наконец, есть явный оператор в object.GetHashCode ссылка в MSDN: реализация метода GetHashCode по умолчанию не гарантирует уникального возврата значения для разных объектов. Кроме того,.NET Framework не гарантирует стандартную реализацию метода GetHashCode, и возвращаемое значение будет одинаковым для разных версий .NET Framework. Следовательно, реализация этого метода по умолчанию не должна использоваться как уникальный идентификатор объекта для целей хэширования.
Ответ 4
На самом деле вам не нужно ничего изменять над классом, для которого требуется только ссылочное равенство.
Кроме того, формально это не является хорошей реализацией, поскольку имеет плохое распространение. Хэш-функция должна иметь разумное распределение, поскольку она улучшает распределение хеш-ковша и, косвенно, производительность в коллекциях, которые используют хеш-таблицы. Как я уже сказал, это формальный ответ, один из рекомендаций при разработке хэш-функции.
