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

Из ValueType.cs

 ** Действие: наш алгоритм для возврата hashcode немного сложнее.  Мы смотрим 
 ** для первого нестатического поля и получить его hashcode.  Если тип не имеет 
 ** нестатические поля, мы возвращаем hash-код типа.  Мы не можем
 ** hashcode статического члена, потому что если этот элемент имеет тот же тип, что и 
 ** оригинальный тип, мы закончим бесконечным циклом.

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

Пример (c / p из Linqpad):

 void Main() { var kvp1 = new KeyValuePair("foo", "bar"); var kvp2 = new KeyValuePair("foo", "baz"); // true (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump(); } 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В частности:

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

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

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

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

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

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

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

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

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

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

 public class KVPCmp : IEqualityComparer>, IEqualityComparer { bool IEqualityComparer.Equals(object x, object y) { if(x == null) return y == null; if(y == null) return false; if(!(x is KeyValuePair) || !(y is KeyValuePair)) throw new ArgumentException("Comparison of KeyValuePairs only."); return Equals((KeyValuePair) x, (KeyValuePair) y); } public bool Equals(KeyValuePair x, KeyValuePair y) { return x.Key.Equals(y.Key) && x.Value.Equals(y.Value); } public int GetHashCode(KeyValuePair 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)) throw new ArgumentException(); return GetHashCode((KeyValuePair)obj); } } 

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

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

Interesting Posts

Что более эффективно? Статические данные, передача данных, общие настройки, firebase database …?

Получить права администраторов в Windows 7, когда нет учетной записи администратора

bootstrap-typeahead.js добавляет слушателя на событие select

Преобразование целых чисел в число написанных чисел

Как преобразовать формат FLV-файла в формат, который распознает Picasa (например, AVI, MPEG, WMV)?

Android ImageView Масштабирование и переводческая проблема

Панель предварительного просмотра Explorer и файлы DOTX

текущее время / продолжительность видео html5?

Что указывают данные SMART?

Создание размытого прозрачного фонового эффекта

Как изменить цвет фона экспорта Inkscape по умолчанию с желтого на белый?

Java-массив с элементами более 4 ГБ

Текстовый редактор в виде блокнота с автосохранением

javascript изменение размера события стрельбы несколько раз, перетаскивая ручку изменения размера

Что такое «объект типа« закрытие »не является подмножеством« ошибка в «Блестящем»?

Давайте будем гением компьютера.