Что происходит, когда в ключе словаря происходит столкновение хеша?

Question

Я всю жизнь кодирую на c ++ и java, но на C # я чувствую, что это совершенно другое животное.

В случае коллизии хеша в контейнере Dictionary в c #, что это делает? или это вообще обнаруживает столкновение?

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

[Обновление 10:56 А.М. 6/4/2010]

Я пытаюсь создать счетчик для каждого пользователя. И набор user # не определен, он может как увеличиваться, так и уменьшаться. И я ожидаю, что размер данных будет больше 1000.

Итак, я хочу:

• быстрый доступ желательно не O (n), важно, чтобы у меня было близко к O (1) из-за требования, мне нужно убедиться, что я могу заставить людей выйти из системы, прежде чем они смогут выполнить что-то глупое.
• Динамический рост и сжатие.
• уникальные данные.

Hashmap был моим решением, и кажется, словарь - это то, что похоже на hashmap в c # ...

Answer 1

Хэш-коллизии корректно обрабатываются Dictionary<> - в том случае, если объект правильно реализует GetHashCode() и Equals(), соответствующий экземпляр будет возвращен из словаря.

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

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

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

Answer 2

Согласно этой статье на MSDN , в случае коллизии хеш-классов класс Dictionary преобразует сегмент в связанный список. Более старый класс HashTable, с другой стороны, использует перефразировку.

Answer 3

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

В .Net 4.6 строки "699391" и "1241308" выдают один и тот же хэш-код. Что происходит в следующем коде?

myDictionary.Add( "699391", "abc" );
myDictionary.Add( "1241308", "def" );

Следующий код демонстрирует, что словарь .Net принимает разные ключи, которые вызывают конфликт хэшей. Не выдается исключение, и поиск по словарному ключу возвращает ожидаемый объект.

var hashes = new Dictionary<int, string>();
var collisions = new List<string>();

for (int i = 0; ; ++i)
{
    string st = i.ToString();
    int hash = st.GetHashCode();

    if (hashes.TryGetValue( hash, out string collision ))
    {
        // On .Net 4.6 we find "699391" and "1241308".
        collisions.Add( collision );
        collisions.Add( st );
        break;
    }
    else
        hashes.Add( hash, st );
}
Debug.Assert( collisions[0] != collisions[1], "Check we have produced two different strings" );
Debug.Assert( collisions[0].GetHashCode() == collisions[1].GetHashCode(), "Prove we have different strings producing the same hashcode" );

var newDictionary = new Dictionary<string, string>();
newDictionary.Add( collisions[0], "abc" );
newDictionary.Add( collisions[1], "def" );

Console.Write( "If we get here without an exception being thrown, it demonstrates a dictionary accepts multiple items with different keys that produce the same hash value." );

Debug.Assert( newDictionary[collisions[0]] == "abc" );
Debug.Assert( newDictionary[collisions[1]] == "def" );

Answer 4

Проверьте эту ссылку для хорошего объяснения: Обширный анализ структур данных с использованием C # 2.0

По сути, общий словарь .NET объединяет элементы с одинаковым хеш-значением.