Насколько хорошо словарь .NET разрешает коллизии?

Question

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

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

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

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 для сравнения.

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

Answer 1

Хеш-коллизии влияют только на производительность, а не на целостность.

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

Answer 2

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

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

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

Answer 3

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

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