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

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

В случае хеш-столкновения в контейнере Dictionary в С#, что он делает? или он даже обнаруживает столкновение?

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

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

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

Итак, я хочу:

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

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

Ответы

Ответ 1

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

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

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

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

Ответ 2

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

Ответ 3

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

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

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

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

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" );

Ответ 5

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