Как хорошо словарь.NET разрешает коллизии?
У меня есть проблема с пользовательским объектом, который должен быть включен для таблицы. Я должен генерировать уникальный числовой ключ. У меня есть проблемы коллизии, и я задаюсь вопросом, могу ли я усилить словарь для помощи мне. Предположите, что у меня есть объект как это:
class Thingy
{
public string Foo;
public string Bar;
public string Others;
}
и так далее с большим количеством полей. Позволяет говорят, что Foo и Панель являются моими полями ключа - если они равны между двумя 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 и использую последовательное значение, выходящее из словаря как мой фактический ключ? Я задаюсь вопросом, будет ли Словарь, при обнаружении редкой коллизии хэш-кода, звонить, мой Равняется методу, решите, что объекты на самом деле отличаются, и хранят их по-другому. Я отображающий затем при поиске его, он видел бы блок для того хеша и искал бы корректную Штуку, снова использование Равняется для сравнения.
Имеет место это со словарем, или он только разрешает коллизии, где хэш-код отличается, но (размер % хеша) то же? Если это не будет работать, что могло бы?
3 ответа
Коллизии хэша влияют только на производительность, но не на целостность.
Простым тестом будет изменение GetHashCode() на простое возвращение 1;. Вы заметите, что словарь по-прежнему ведет себя правильно, но с любым разумным набором данных он будет работать ужасно.
Каждое приложение может использовать одно и то же имя входа, если оно совпадает и указывает на одну и ту же базу данных.
См. ответ здесь: http://forums.asp.net/t/1322863.aspx для получения более подробной информации.
Edit - added
Здесь также рассматривается:
http://msdn.microsoft.com/en-us/library/ms998347.aspx
-121--4028670-Хеш-конфликты влияют только на производительность, а не на целостность.
Простой тест состоит в том, чтобы изменить GetHashCode (), чтобы просто вернуть 1;. Вы заметите, что словарь все еще ведет себя правильно, но с любым разумным набором данных, он будет работать ужасно.
-121--2595355- Хеш-коллизии в первую очередь влияют на производительность - неверно. При условии, что функция Equals () работает правильно.
Словарь использует хэш-код как способ упорядочить предметы в отдельные «сегменты». Если слишком много предметы имеют один и тот же хэш-код, могут возникнуть проблемы с производительностью. Однако если Равно () может правильно различать экземпляры, необходимо получить правильные результаты.
Где хэш-коды могут привести к проблемам с изменяемыми объектами . Если класс Thingy позволяет Foo или Bar изменять предмет в словаре, то при последующей попытке доступа его можно не найти. Это происходит потому, что созданный теперь хэш-код отличается от кода, используемого для хранения значения в словаре.
GetHashCode предназначен для использования в хэш-таблицах, где коллизии должны быть минимизированы, но не исключены. Если вам нужно создать действительно уникальный ключ, GetHashCode является разумной отправной точкой (и не такой длинной, как guid), но вам придется хранить ключ как часть объекта и вести список используемых ключей отдельно.
Хотя вы можете получить что-то, что выглядит пригодным для использования из внутреннего содержимого Dictionary, это, вероятно, не будет работать надежно - например, если вы добавите больше элементов, чем изначально было выделено для обработки словаря, базовая структура данных будет перестроена, и отдельные элементы могут оказаться в совершенно другой части словаря.