Почему ValueType.GetHashCode() реализован так, как есть?

Ответ 1

ОБНОВЛЕНИЕ: Этот ответ был (частично) основой статьи в блоге, которую я написал, в которой более подробно рассматриваются характеристики дизайна GetHashcode. Спасибо за интересный вопрос!

Я не реализовал это, и я не говорил с людьми, которые сделали. Но я могу указать на несколько вещей.

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

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

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

1) Быстро. Очень быстро! Помните, весь смысл хеш-кода в первую очередь заключается в том, чтобы быстро найти относительно пустой слот в хеш-таблице. Если вычисление O (1) хеш-кода на практике медленнее, чем время O (n), затрачиваемое на наивный поиск, то решение с использованием хеш-кода является чистым убытком.

2) Хорошо распределено по пространству 32-битных целых для заданного распределения входов. Чем хуже распределение по целым, тем больше будет наивного линейного поиска хеш-таблицы.

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

Распространенным предложением является "хэширование всех полей и затем XOR вместе полученных хеш-кодов". Но это напрашивается на вопрос; XORing двух 32-битных целых дает хорошее распределение, только если сами входы очень хорошо распределены и не связаны друг с другом, и это маловероятный сценарий:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

Какова вероятность того, что x и y хорошо распределены по всему диапазону 32-битных целых чисел? Очень низкий. Шансы намного лучше, потому что они малы и близки друг к другу, и в этом случае кеширование их хэш-кодов вместе делает вещи хуже, а не лучше. xoring вместе целые числа, которые близки друг к другу, обнуляют большинство битов.

Кроме того, это O (n) в количестве полей! Тип значения с большим количеством маленьких полей может занять сравнительно много времени для вычисления хеш-кода.

По сути, мы имеем дело с тем, что пользователь сам не предоставил реализацию хеш-кода; либо им все равно, либо они не ожидают, что этот тип когда-либо будет использоваться в качестве ключа в хэш-таблице. Учитывая, что у вас нет семантической информации о типе, что лучше всего делать? Лучшее, что можно сделать, это то, что быстро и дает хорошие результаты в большинстве случаев.

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

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

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

Ответ 2

Фактическая реализация ValueType.GetHashCode() не совсем соответствует комментарию. Он имеет две версии алгоритма, быстрые и медленные. Сначала он проверяет, содержит ли структура какие-либо элементы ссылочного типа, и есть ли какие-либо дополнения между полями. Заполнение пустого пространства в структурном значении, создаваемом, когда компилятор JIT выравнивает поля. Там заполнение в структуре, которая содержит bool и int (3 байта), но не имеет отступов, когда она содержит int и int, они плотно прилегают друг к другу.

Без ссылки и без заполнения, он может выполнять быструю версию, так как каждый бит в структурном значении является битом, который принадлежит значению поля. Он просто xors по 4 байта за раз. Вы получите "хороший" хэш-код, который учитывает всех членов. Таким образом, многие простые типы структуры в платформе .NET ведут себя так же, как Point и Size.

В противном случае это медленная версия, моральный эквивалент отражения. Что вы получаете, ваш KeyValuePair < > содержит ссылки. И этот только проверяет первое поле кандидата, как говорится в комментарии. Это, безусловно, первоочередная оптимизация, избегая горения слишком много времени.

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

Еще одна мучительная деталь: у быстрой версии есть ошибка, которая байт, когда структура содержит поле типа decimal. Значения 12m и 12.0m логически равны, но у них нет одинакового битового шаблона. GetHashCode() скажет, что они не равны. Уч.

Ответ 3

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

В частности:

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

Теперь я не говорю, что реализация ValueType - отличная идея - это приведет к зависанию производительности различными способами... но я не думаю, что это действительно сломалось.

Ответ 4

Ну, есть плюсы и минусы для любой реализации GetHashCode(). Это, конечно, то, что мы взвешиваем при реализации наших собственных, но в случае ValueType.GetHashCode() существует особая трудность в том, что у них нет большой информации о том, каковы будут фактические данные конкретного типа. Конечно, это часто случается с нами, когда мы создаем абстрактный класс или планируем быть базой классов, которые добавят намного больше с точки зрения состояния, но в этих случаях у нас есть очевидное решение, просто использующее реализацию по умолчанию object.GetHashCode(), если производный класс не хочет его переопределять.

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

Итак, для метода Equals() реализация очевидна; проверьте, что два объекта одного типа, и если он затем проверяет также, что все поля равны (на самом деле есть оптимизация, которая в некоторых случаях выполняет побитовое сравнение, но оптимизацию по одной и той же базовой идее).

Что делать для GetHashCode()? Просто нет идеального решения. Одна вещь, которую они могут сделать, - это что-то вроде mult-then-add или shift-then-xor для каждого поля. Вероятно, это даст довольно хороший хэш-код, но может быть дорогостоящим, если бы было много полей (неважно, что не рекомендуется иметь типы значений, у которых много полей, разработчик должен учитывать, что они все еще могут и действительно могут быть даже времена, когда это имеет смысл, хотя я честно не могу представить себе время, когда это имеет смысл, и имеет смысл также хешировать его). Если бы они знали, что некоторые поля редко отличались между экземплярами, они могли игнорировать эти поля и все еще иметь довольно хороший хэш-код, а также довольно быстро. Наконец, они могут игнорировать большинство полей и надеются, что те, которые они не игнорируют, часто меняются по значению. Они пошли на самую экстремальную версию последнего.

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

Итак, это реализация, которая засасывает, если вы хешируете множество значений, где первое поле является одинаковым (или иным образом возвращает один и тот же хэш-код), но другие реализации будут сосать в других случаях (Mono отправляется на xoring все поля " хэш-коды вместе, лучше в вашем случае, хуже в других).

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

Итак, не здорово, но ничего не было бы идеально. Это показывает, что всегда нужно учитывать обе стороны того, что означает "равенство" при использовании объекта в качестве ключа. Он легко устанавливается в вашем случае с помощью:

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

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

Ответ 5

Спасибо всем, очень, очень информативные ответы. Я знал, что в этом решении должно быть какое-то обоснование, но я бы хотел, чтобы это было документировано лучше. Я не могу использовать v4 структуры, поэтому нет Tuple<>, и это была основная причина, по которой я решил контрейлеризовать структуру KeyValuePair. Но я думаю, что нет режущих углов, и мне придется сворачивать самостоятельно. Еще раз спасибо всем.