Как дважды это вставить в HashTable, как это возможно? - PullRequest
2 голосов
/ 15 ноября 2010

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

В моем тесте у меня есть 2 хеш-таблицы, какие ключизаполнены: 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();
    }        
}

}

Ответы [ 3 ]

4 голосов
/ 15 ноября 2010

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

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

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

3 голосов
/ 15 ноября 2010

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

1 голос
/ 15 ноября 2010

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);
    }
...