Вставка дважды того же ключа в HashTable, как это возможно?

Question

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

В моем тесте, у меня 2 HashTables, какие клавиши заполняются: 1- Целые 2- объект, который я переопределен метод GetHashCode для возврата всегда 1.

Мой вопрос здесь: в то время как первый тест ломается при добавлении одного и того же ключа int, второй тест - нет! Как так? Все хэш-коды, которые должны быть проверены при вставке, все возвращаются. 1.

Спасибо заранее!

---

Мой код:

class Collections 
{ 
    public Collections() 
    { 
     // Testing a hashtable with integer keys 
     Dictionary<int, string> d1 = new Dictionary<int, string>(); 
     d1.Add(1, "one"); 
     d1.Add(2, "two"); 
     d1.Add(3, "three"); 
     // d1.Add(3, "three"); // Cannot add the same key, i.e. same hashcode 
     foreach (int key in d1.Keys) 
      Console.WriteLine(key); 

     // Testing a hashtable with objects returning only 1 as hashcode for its keys 
     Dictionary<Hashkey, string> d2 = new Dictionary<Hashkey, string>(); 
     d2.Add(new Hashkey(1), "one"); 
     d2.Add(new Hashkey(2), "two"); 
     d2.Add(new Hashkey(3), "three"); 
     d2.Add(new Hashkey(3), "three"); 
     for (int i = 0; i < d2.Count; i++) 
      Console.WriteLine(d2.Keys.ElementAt(i).ToString()); 

    } 


} 

/// <summary> 
/// Creating a class that is serving as a key of a hasf table, overring the GetHashcode() of System.Object 
/// </summary> 
class Hashkey 
{ 
    public int Key { get; set; } 

    public Hashkey(int key) 
    { 
     this.Key = key; 
    } 

    // Overriding the Hashcode to return always 1 
    public override int GetHashCode() 
    { 
     return 1; 
     // return base.GetHashCode(); 
    } 

    // No override 
    public override bool Equals(object obj) 
    { 
     return base.Equals(obj); 
    } 

    // returning the name of the object 
    public override string ToString() 
    { 
     return this.Key.ToString(); 
    }   
} 

}

Answer 1

Dictionary будет проверять хэш-кода и объекта равенства. Хэш просто используется, чтобы придумать «первое приближение», чтобы найти возможно равных ключей очень эффективно.

Ваше переопределение Equals просто делегирует основную реализацию, которая использует ссылочное равенство. Это означает, что любые два разных экземпляра HashKey не равны, даже если они имеют одинаковое значение для свойства Key.

Что вы на самом деле пытаетесь достичь? Или вы просто пытаетесь понять, как GetHashCode и Equals связаны друг с другом?

Answer 2

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

Answer 3

Equals сравнивает ссылку HashKey.

Потому что это разные экземпляры, они не равны.

Ваш Equals должен выглядеть следующим образом:

public override bool Equals(object obj) 
    { 
     if (ReferenceEquals(this, obj)) 
      return true; 

     var other = obj as Hashkey; 

     return 
      other != null && 
      Key.Equals(other.Key); 
    }