Dictionary ключем которого является объект

402

04 февраля 2017, 07:02

Допустим, имеется объект с переопределенным GetHashCode, который я хочу сделать ключем. GetHashCode вычисляется, как совокупность GetHashCode всех полей.

Я правильно понимаю, что HashCode вычисляется только 1 раз при добавлении в словарь?

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

Судя по исходникам это так.

Получается, что для таких случаев нужно делать свою реализацию словаря или есть что-то готовое, что HashCode на ходу пересчитывает?

Answer 1

Хэшкод объекта не должен меняться на протяжении жизни объекта. Эта рекомендация превращается в строгое правило, если объект служит ключом в Dictionary<K, V> или лежит в HashSet<T>.

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

Имеет смысл либо считать хэшкод только по неизменяемым полям, либо фиксировать хэшкод и запоминать его в поле объекта. Ну или просто гарантировать в коде, что пока объект в словаре, его хэшкод не меняется.

Хорошее дополнительное чтение по теме: Эрик Липперт, Правила и рекомендации по переопределению GetHashCode. И ещё: MSDN: Remarks on Object.GetHashCode Method (особенно секция «Notes to Inheritors»).

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