Насколько хорошо .NET-решение разрешает конфликты?

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

class Thingy
{
    public string Foo;
    public string Bar;
    public string Others;
}

и т.д. с большим количеством полей. Допустим, что Foo и Bar являются моими ключевыми полями - если они равны между двумя Thingys, то два объекта должны считаться равными (один может представлять собой обновление для другого, при этом обновляются поля Other). Поэтому у меня есть следующие:

public override bool Equals(object obj)
{
    Thingy thing = (Thingy)obj; // yes I do type check first
    return (this.Foo == thing.Foo && this.Bar == thing.Bar);
}

public override int GetHashCode()
{
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl
}

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

Мой вопрос заключается в следующем: могу ли я использовать словарь <Thingy, int > , где я помещал в Thingys, и использовать последовательное значение, выходящее из словаря, как мой фактический ключ? Мне интересно, будет ли Словарь при обнаружении редкого столкновения кодов хэшей вызовет мой метод Equals, определит, что объекты на самом деле разные, и сохраните их по-разному. Затем я получаю изображение, когда смотрю на него, он видит ведро для этого хеша и ищет правильную Thingy, снова используя Equals для сравнения.

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

Ответы

Ответ 1

Конфликты хэша влияют только на производительность, а не на целостность.

Простым тестом было бы изменение GetHashCode(), чтобы просто вернуть 1;. Вы заметите, что словарь по-прежнему ведет себя правильно, но с любым разумным набором данных он будет работать ужасно.

Ответ 2

Конфликты хэшей будут в первую очередь влиять на производительность - неверность. Пока Equals() ведет себя правильно.

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

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

Ответ 3

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

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