使用 Dictionary 和 HashSet 的 GetHashCode 方法

Question

我有一个关于 Dictionary 和 HashSet 在 C# 中如何工作的问题。根据我的理解，GetHashCode用于哈希表中来确定键的唯一性。

在以下 MSDN 页面上，它指出：

A hash code is a numeric value that is used to insert and identify an object in a hash-based collection such as the Dictionary class, the Hashtable class, or a type derived from the DictionaryBase class.

Link: MSDN Object.GetHashCode

如果是这样，为什么当 car2 与 car1 具有相同的哈希码时，ContainsKey 和 Contains return 为 false？如果我的理解是正确的，如果 MSDN 所说的是正确的，那么这两个 return 不应该是真的吗？

class Program
{
    static void Main(string[] args)
    {            
        // Create a Dictionary and HashSet
        Dictionary<Car, int> carDictionary = new Dictionary<Car, int>();
        HashSet<Car> carSet = new HashSet<Car>();

        // Create 3 Cars (2 generic and 1 Civic)
        Car car1 = new Car();
        Car car2 = new Car();
        Car car3 = new Civic();

        // Test hash values
        int test1 = car1.GetHashCode(); // 22008501
        int test2 = car2.GetHashCode(); // 22008501
        int test3 = car3.GetHashCode(); // 12048305


        // Add 1 generic car and 1 Civic to both Dictionary and HashSet
        carDictionary.Add(car1, 1);
        carDictionary.Add(car3, 1);
        carSet.Add(car1);
        carSet.Add(car3);

        // Why are both of these false?
        bool dictTest1 = carDictionary.ContainsKey(car2);  // false
        bool setTest1 = carSet.Contains(car2); // false

        // Testing equality makes sense
        bool testA = car1.Equals(car2); // false
        bool testB = car1.Equals(car3); // false
    }
}

class Car
{
    public override int GetHashCode()
    {
        return 22008501;
    }
}

class Civic : Car
{
    public override int GetHashCode()
    {
        return 12048305;
    }
}

Answer 1

不必保证哈希码是唯一的，如果键相等则它们必须相等。

现在发生的是项目存储在桶中。如果您查询 Dictionary<TK,TV> 是否包含给定键或 HashSet<T> 给定项目，它将首先计算哈希码以获取正确的存储桶。

接下来它将迭代存储桶中的所有项目并对它执行.Equals测试。只有在其中一个匹配的情况下，它才会 return true.

换句话说，允许 到 return 每个实例的 相同哈希码 尽管实例不同。它只会使散列效率低下。

C# 因此存储了一个 Dictionary<TK,TV> 比如：

+----------+ | 22008501 |---<car1,1>----<car3,1>----| +----------+ | 11155414 | (other bucket) +----------+

左边有（可能是bucket labels），虽然对于小的Dictionary来说，bucket的数量会非常少，会对hash进行一个操作（比如取模), 以减少结果的数量。

现在查询car2是否在Dictionary中，会计算hash，取第一个bucket。然后它会迭代，并在 car1 vs car2，下一个 car3 vs car2 上执行相等性检查，它会到达桶的末尾和 return false。这是因为默认的 Equals 操作是引用相等。只有你override也是，（比如所有的车都一样，你可以returntrue）。

Answer 2

如您所见，car1.Equals(car2) 并非如此。 Dictionary 和 Hashset 成员资格仅适用于相等的对象。这意味着 .Equals() returns 正确。这仅在首次发现它们的哈希码相等时才进行测试。

Answer 3

因为ContainsKey的逻辑与此类似。

//This is a simplified model for answering the OP's question, the real one is more complex.
private List<List<KeyValuePair<TKey,TValue>>> _buckets = //....

public bool ContainsKey(TKey key)
{
    List<KeyValuePair<TKey,TValue>> bucket = _buckets[key.GetHashCode() % _buckets.Length];
    foreach(var item in bucket)
    {
        if(key.Equals(item.Key))
            return true;
    }
    return false;
}

GetHashCode 所做的只是获取您的密钥将放入的存储桶，它仍然必须遍历该存储桶的每个成员并通过 Equals 方法找到精确匹配。这就是为什么拥有良好的哈希码很重要的原因，桶中的项目越少，foreach 部分就会越快。最好的哈希码每个桶只有一个项目。

这里是 actual code 用于 HashSet 上的 Contains（Dictionary 的 ContainsKey 非常相似但更复杂）

private int[] m_buckets;
private Slot[] m_slots;

public bool Contains(T item) {
    if (m_buckets != null) {
        int hashCode = InternalGetHashCode(item);
        // see note at "HashSet" level describing why "- 1" appears in for loop
        for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
            if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) {
                return true;
            }
        }
    }
    // either m_buckets is null or wasn't found
    return false;
}

private int InternalGetHashCode(T item) {
    if (item == null) {
        return 0;
    } 
    return m_comparer.GetHashCode(item) & Lower31BitMask;
}

internal struct Slot {
    internal int hashCode;      // Lower 31 bits of hash code, -1 if unused
    internal T value;
    internal int next;          // Index of next entry, -1 if last
}

使用 Dictionary 和 HashSet 的 GetHashCode 方法

GetHashCode method with Dictionary and HashSet

.net

c#

dictionary

hashset