Если хэш-код нулевого значения всегда равен нулю, в .NET

Учитывая, что такие коллекции, как System.Collections.Generic.HashSet<> accept null как член набора, можно спросить, каков должен быть хэш-код null. Похоже, что в структуре используется 0:

// nullable struct type
int? i = null;
i.GetHashCode();  // gives 0
EqualityComparer<int?>.Default.GetHashCode(i);  // gives 0

// class type
CultureInfo c = null;
EqualityComparer<CultureInfo>.Default.GetHashCode(c);  // gives 0

Это может быть (немного) проблематично с нулевыми перечислениями. Если мы определим

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

то Nullable<Season> (также называемый Season?) может принимать только пять значений, но два из них, а именно null и Season.Spring, имеют одинаковый хэш-код.

Возникает соблазн написать "лучшее" сравнительное равенство:

class NewNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? Default.GetHashCode(x) : -1;
  }
}

Но есть ли причина, по которой хэш-код null должен быть 0?

EDIT/Сложение:

Некоторые люди, похоже, думают, что это касается переопределения Object.GetHashCode(). На самом деле это не так. (Авторы .NET сделали переопределение GetHashCode() в структуре Nullable<>, которая имеет .) Пользовательская реализация без параметров GetHashCode() никогда не сможет справиться с ситуацией где объект, чей хэш-код мы ищем, null.

Речь идет об использовании абстрактного метода EqualityComparer<T>.GetHashCode(T) или иным способом реализации метода интерфейса IEqualityComparer<T>.GetHashCode(T), Теперь, создавая эти ссылки на MSDN, я вижу, что там говорится, что эти методы бросают ArgumentNullException, если их единственным аргументом является null. Это, безусловно, ошибка в MSDN? Ни одна из собственных реализаций .NET не выдает исключений. Бросание в этом случае эффективно нарушит любую попытку добавить null к HashSet<>. Если HashSet<> делает что-то необычное при работе с элементом null (мне нужно будет это проверить).

NEW EDIT/ADDITION:

Теперь я попробовал отладку. С помощью HashSet<> я могу подтвердить, что с помощью сопоставителя равенства по умолчанию значения Season.Spring и null будут заканчиваться в том же ведре. Это можно определить, тщательно проверив частные элементы массива m_buckets и m_slots. Обратите внимание, что индексы всегда, по дизайну, смещены на один.

Однако приведенный выше код не исправляет это. Как оказалось, HashSet<> никогда не спросит о равенстве, когда значение null. Это из исходного кода HashSet<>:

    // Workaround Comparers that throw ArgumentNullException for GetHashCode(null).
    private int InternalGetHashCode(T item) {
        if (item == null) { 
            return 0;
        } 
        return m_comparer.GetHashCode(item) & Lower31BitMask; 
    }

Это означает, что , по крайней мере, для HashSet<>, даже не возможно изменить хэш null. Вместо этого решение должно изменить хэш всех других значений, например:

class NewerNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? 1 + Default.GetHashCode(x) : /* not seen by HashSet: */ 0;
  }
}

Ответы

Ответ 1

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

Возврат 0 или -1 для нулевого значения, если вы выберете один и вернете его все время, будет работать. Очевидно, что ненулевые хэш-коды не должны возвращать значение, которое вы используете для null.

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

GetHashCode в нулевых полях?

Что должен вернуть GetHashCode, когда идентификатор объекта равен нулю?

"Замечания" этой записи MSDN подробно описываются вокруг хеш-кода. По-видимому, документация не предусматривает никакого освещения или обсуждения нулевых значений вообще - даже в содержании сообщества.

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

Интересная находка, кстати.

Другая проблема, с которой я вижу в общем, состоит в том, что хеш-код не может представлять 4-байтовый или более большой тип, который может быть обнулен без по крайней мере одного столкновения (больше как тип размер увеличивается). Например, хеш-код int - это просто int, поэтому он использует полный диапазон int. Какое значение в этом диапазоне вы выберете для null? Независимо от того, что вы выбрали, столкнется с самим хэш-кодом значения.

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

Ответ 2

Имейте в виду, что хеш-код используется в качестве первого шага при определении только равенства, а [должен/должен] никогда (быть) использоваться как де-факто определение того, равны ли два объекта.

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

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

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

Если да, тогда определите свой собственный сопоставитель для случая nullable для вашего конкретного типа и убедитесь, что нулевое значение всегда дает хеш-код, который всегда один и тот же (конечно!) и значение, которое не может быть получено по алгоритму собственного хэш-кода базового типа. Для ваших собственных типов это возможно. Для других - удачи:)

Ответ 3

Он не должен быть нулем - вы могли бы сделать это 42, если хотите.

Все, что имеет значение, это согласованность во время выполнения программы.

Это просто самое очевидное представление, потому что null часто представляется как ноль внутри. Это означает, что при отладке, если вы видите хэш-код нуля, это может побудить вас подумать: "Хм.. это была пустая проблема?"

Обратите внимание, что если вы используете число, подобное 0xDEADBEEF, тогда кто-то может сказать, что вы используете магическое число... и вы вроде бы. (Вы могли бы сказать, что ноль тоже волшебное число, и вы были бы правы... кроме того, что он настолько широко используется, чтобы быть чем-то вроде исключения из правила.)

Ответ 4

Хороший вопрос.

Я просто попытался закодировать это:

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

и выполните это следующим образом:

Season? v = null;
Console.WriteLine(v);

он возвращает null

если я это сделаю, вместо этого обычный

Season? v = Season.Spring;
Console.WriteLine((int)v);

он возвращает 0, как и ожидалось, или просто Spring, если мы избежим нажатия на int.

Итак, если вы выполните следующее:

Season? v = Season.Spring;  
Season? vnull = null;   
if(vnull == v) // never TRUE

EDIT

От MSDN

Если два объекта сравниваются как равные, метод GetHashCode для каждого объекта должен возвращать одно и то же значение. Однако, если два объекта не сравниваются как равные, методы GetHashCode для двух объектов не должны возвращать разные значения

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

С MSDN снова:

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

Ответ 5

Но есть ли причина, по которой хэш-код нулевого значения должен быть 0?

Это могло быть что угодно. Я склонен согласиться с тем, что 0 не обязательно является лучшим выбором, но это, вероятно, приводит к наименьшим ошибкам.

Хэш-функция абсолютно должна возвращать один и тот же хеш для одного и того же значения. Как только существует компонент, который делает это, это действительно единственное допустимое значение для хэша null. Если для этого была константа, например, hm, object.HashOfNull, то кто-то, использующий IEqualityComparer, должен был знать, использовать это значение. Я думаю, что если они не подумают об этом, вероятность того, что они будут использовать 0, немного выше любого другого значения.

по крайней мере, для HashSet < > , даже невозможно изменить хэш нулевого

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

Ответ 6

Это просто для простоты. Такого жесткого требования нет. Вам нужно только обеспечить общие требования хэш-кодирования.

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

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

Ответ 7

Таким образом, этого можно избежать, используя значение Unknown enum (хотя кажется немного странным, если Season будет неизвестным). Итак, что-то вроде этого отрицает эту проблему:

public enum Season
{
   Unknown = 0,
   Spring,
   Summer,
   Autumn,
   Winter
}

Season some_season = Season.Unknown;
int code = some_season.GetHashCode(); // 0
some_season = Season.Autumn;
code = some_season.GetHashCode(); // 3

Тогда у вас будут уникальные значения хеш-кода для каждого сезона.

Ответ 8

Лично я нахожу использование значений с нулевым значением немного неудобным и стараюсь избегать их всякий раз, когда могу. Ваша проблема - еще одна причина. Иногда они очень удобны, но мое эмпирическое правило состоит в том, чтобы не смешивать типы значений с нулевым, если это возможно, просто потому, что они из двух разных миров. В среде .NET они, похоже, делают то же самое - многие типы значений предоставляют метод TryParse, который является способом разделения значений без значения (null).

В вашем конкретном случае легко избавиться от проблемы, потому что вы обрабатываете свой собственный тип Season.

(Season?)null для меня означает, что "сезон не указан", например, когда у вас есть веб-форма, где некоторые поля не требуются. По моему мнению, лучше указать это особое значение в enum, а не использовать немного неуклюжие Nullable<T>. Это будет быстрее (без бокса) легче читать (Season.NotSpecified vs null) и решит вашу проблему с хэш-кодами.

Конечно, для других типов, таких как int, вы не можете расширять область значений и обозначать одно из значений, поскольку это не всегда возможно. Но с int? хеш-кодом коллизия намного меньше, если вообще.