Что происходит, когда хэш-коллизия происходит в ключе Словаря?
Я кодировал в C++ и полноте Java моей жизни, но на C#, я чувствую, что это - полностью другое животное.
В случае хэш-коллизии в контейнере Словаря в c#, что это делает? или это даже обнаруживает коллизию?
В случае коллизий в подобных контейнерах в SDL некоторые сделали бы данные ссылки раздела значения ключа к разделу значения ключа как связанный список, или некоторые попытаются найти другой метод хеша.
[Обновление 10:56 04.06.2010]
Я пытаюсь сделать счетчик на пользователя. И пользователь аппарата # не определяется, это может оба увеличиться или уменьшиться. И я ожидаю, что размер данных будет более чем 1 000.
Так, я хочу:
- быстрый доступ предпочтительно не O (n), Это важный, что я имею близко к O (1) из-за требования, я должен удостовериться, что могу вынудить людей выхода, прежде чем они смогут выполнить что-то глупое.
- Динамический рост и уменьшение.
- уникальные данные.
Hashmap был моим решением, и кажется, что Словарь - то, что подобно hashmap в c#...
3 ответа
Коллизии хэшей правильно обрабатываются Dictionary <> - если объект правильно реализует GetHashCode () и Equals () , соответствующие экземпляр будет возвращен из словаря.
Во-первых, вы не должны делать никаких предположений о том, как Dictionary <> работает внутри - это деталь реализации, которая, вероятно, изменится со временем. Сказав это ....
Вам следует задуматься о том, правильно ли типы, которые вы используете для ключей, реализуют GetHashCode () и Equals () . Основные правила заключаются в том, что GetHashCode () должен возвращать одно и то же значение на время существования объекта, а Equals () должен возвращать истину, если два экземпляра представляют один и тот же объект. . Если вы не переопределите его, Equals () использует ссылочное равенство - это означает, что он возвращает истину только в том случае, если два объекта фактически являются одним и тем же экземпляром. Вы можете переопределить способ работы Equals () , но тогда вы должны убедиться, что два «равных» объекта также производят один и тот же хэш-код.
С точки зрения производительности вы также можете предоставить реализацию GetHashCode () , которая генерирует хороший разброс значений для уменьшения частоты конфликтов хэш-кода. Основным недостатком коллизий хэш-кода является то, что он сокращает словарь до списка с точки зрения производительности. Всякий раз, когда два разных экземпляра объекта дают один и тот же хэш-код, они сохраняются в одной и той же внутренней корзине словаря.В результате необходимо выполнить линейное сканирование, вызывая Equals () для каждого экземпляра, пока не будет найдено совпадение.
Согласно этой статье в MSDN , в случае хеш-коллизии класс Dictionary преобразует сегмент в связанный список. С другой стороны, более старый класс HashTable использует повторное хеширование.
Проверьте эту ссылку, чтобы получить хорошее объяснение: Расширенное исследование структур данных с использованием C # 2.0
По сути, общий словарь .NET объединяет элементы с одинаковым значением хеш-функции.