C# Dictionary <> и изменяемые ключи

Question

Мне сказали, что одна из многих причин, когда строки были неизменными в спецификации C#, заключалась в том, чтобы избежать проблемы с хэш-таблицами с ключами, измененными, когда ссылки на строковые ключи изменили их содержимое.

Тип словаря <> позволяет использовать ссылочные типы в качестве ключа. Как словарь избегает проблемы с измененными ключами, которые приводят к «неуместным» значениям? Есть ли клонированный по отношению к объекту объект, когда он используется в качестве ключа?

Answer 1

Тип Dictionary<TKey,TValue> не пытается защитить пользователя от изменения ключа. Это чисто обязанность разработчику нести ответственность за то, чтобы не мутировать ключ.

Если вы думаете об этом немного, это действительно единственный разумный маршрут, который может принять Dictionary<TKey,TValue>. Рассмотрите возможность выполнения операции подобно клонированному члену на объекте. Чтобы быть тщательным, вам нужно сделать глубокий клон, потому что объект, на который делается ссылка в ключе, также может быть мутирован и, следовательно, влияет на хэш-код. Итак, теперь каждый ключ, используемый в таблице, имеет полный клонированный объект, клонированный для защиты от мутации. Это было бы ошибкой и, возможно, очень дорогостоящей операцией.

Answer 2

Класс Dictionary<> не делает ничего, чтобы защитить себя от изменяемого изменяемого объекта ключа. Вы должны знать, является ли класс, который вы используете в качестве ключа, изменчивым, и избегать его, если это возможно.

Answer 3

Это не избежать этой ситуации. Это до вызывающего кода для обеспечения соблюдения этого:

До тех пор, как объект используется в качестве ключа в Dictionary<TKey, TValue>, он не должен изменить каким-либо образом, что влияет на его хэш-значение. Каждый ключ в Dictionary<TKey, TValue> должен быть уникальным в соответствии с соглашением о равенстве словаря. Ключ не может быть null, но может быть значение, если тип значения TValue является ссылочным типом.

(От MSDN)

Answer 4

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

Answer 5

Если ссылочный тип не переопределяет Equals/GetHashCode, словарь с использованием компаратора по умолчанию не будет интересоваться ни одним из полей или свойств ключевых объектов, и, таким образом, они не заметят и не позаботятся, если они изменятся. Проще всего думать о методе GetHashCode по умолчанию, возвращая число, связанное с «идентификатором объекта», и по умолчанию метод Equals сравнивает «id объекта». Действительно, в системе, ограниченной двумя миллиардами или менее объектами, GetHashCode может просто вернуть идентификатор объекта, но по разным причинам он может делать и другие вещи.

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