如何通过键哈希码访问Dictionary

本文关键字：访问 Dictionary 哈希码 何通过 | 更新日期: 2023-09-27 18:18:29

我有一个这样的字典:

 Dictionary<MyCompositeKey, int>

显然，MyCompositeKey是我设计的实现IEqualityComparer的类，因此有GetHashCode方法。

据我所知，字典使用键的哈希值来访问值，所以我的问题是:

虽然我可以很容易地通过dict.TryGetValue(new MyCompositeKey(params))访问该值，但我想在每次访问时摆脱new的开销。

由于这个原因，我想知道是否有一种方法可以直接从key的哈希中访问值(我可以用非常低的开销计算)。

如何通过键哈希码访问Dictionary

没有办法。

注意可能会发生哈希冲突，因此Dictionary<,>中可能有许多键匹配给定的哈希。我们需要Equals来找出哪个(如果有的话)是正确的。

你说的是new开销。你确定这对你来说很重要吗?

如果是，您可以考虑将MyCompositeKey作为不可变的 struct而不是class。在某些情况下，它可能更快，消除了垃圾收集器从内存中删除所有"松散"键的需要。

如果MyCompositeKey是struct，表达式new MyCompositeKey(params)只将所有params加载到调用堆栈(或CPU寄存器或任何运行时数据最好的地方)。

补充:如果你想要struct，考虑实现IEquatable<>。它看起来像这样:

struct MyCompositeKey : IEquatable<MyCompositeKey>
{
  // readonly fields/properties
  public override bool Equals(object obj)
  {
    if (obj is MyCompositeKey)
      return Equals((MyCompositeKey)obj); // unbox and go to below overload
    return false;
  }
  public bool Equals(MyCompositeKey other) // implements interface, can avoid boxing
  {
    // equality logic here
  }
  public override int GetHashCode()
  {
    // hash logic here
  }
}

你不能那样做。

Dictionary<TKey, TValue>使用了一个内部的bucket集合，你不能从类外部访问它——它是private。

在源代码中可以看到，访问方法首先确定桶(根据哈希码)，然后通过索引访问项:

public bool TryGetValue(TKey key, out TValue value) 
{
    int i = FindEntry(key);
    if (i >= 0) 
    {
        value = entries[i].value;
        return true;
    }
    value = default(TValue);
    return false;
}
private int FindEntry(TKey key) 
{
    if (buckets != null) 
    {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) 
        {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) 
                return i;
        }
    }
    return -1;
}
相关文章：