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

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

В моем тесте у меня есть 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();
    }        
}

}


c# hashtable hashcode hash-collision
person Goul    schedule 15.11.2010    source источник

Ответы (3)


arrow_upward
4
arrow_downward

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

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

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

person Jon Skeet    schedule 15.11.2010
comment
Спасибо всем за ответы. - person Goul; 15.11.2010
comment
Спасибо всем за ответы. Я просто пытался узнать, как удалось реализовать уникальную вставку в хеш-таблицу. Я думал, что это основано только на хэш-коде, а не на равенстве объектов. Я обновил свой код, просто возвращая true все время из Equal () для быстрой проверки и получил ошибку, которую я ждал: элемент с таким же ключом уже был добавлен .. Ура - person Goul; 15.11.2010

arrow_upward
3
arrow_downward

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

person spender    schedule 15.11.2010

arrow_upward
1
arrow_downward

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);
    }
person Pieter van Ginkel    schedule 15.11.2010