1

我试图更好地理解散列集的内部结构，例如HashSet<T>，它们是如何工作的，以及为什么它们是高性能的。我发现了下面的文章，实现了一个带有存储桶列表的简单示例http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/。

据我对这篇文章的理解（我之前也这么认为），桶列表本身对每个桶中的一定数量的元素进行分组。一个桶由哈希码表示，即GetHashCode在元素上调用它。我认为更好的性能是基于桶比元素少的事实。

现在我编写了以下幼稚的测试代码：

    public class CustomHashCode
    {
        public int Id { get; set; }

        public override int GetHashCode()
        {
            //return Id.GetHashCode(); // Way better performance
            return Id % 40; // Bad performance! But why?
        }


        public override bool Equals(object obj)
        {
            return ((CustomHashCode) obj).Id == Id;
        }

    }

这里是探查器：

    public static void TestNoCustomHashCode(int iterations)
    {

        var hashSet = new HashSet<NoCustomHashCode>();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Add(new NoCustomHashCode() { Id = j });
        }

        var chc = hashSet.First();
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        for (int j = 0; j < iterations; j++)
        {
            hashSet.Contains(chc);
        }
        stopwatch.Stop();

        Console.WriteLine(string.Format("Elapsed time (ms): {0}", stopwatch.ElapsedMilliseconds));
    }

我天真的想法是：让我们减少桶的数量（使用简单的模数），这应该会提高性能。但这很糟糕（在我的系统上，50000 次迭代大约需要 4 秒）。我还认为，如果我只是将 Id 作为哈希码返回，性能应该会很差，因为我最终会得到 50000 个桶。但情况恰恰相反，我想我只是产生了所谓的碰撞音，而不是改进任何东西。但话又说回来，遗愿清单是如何工作的？

4

3 回答 3

3

Contains基本上是一张支票：

  1. 获取项目的哈希码。
  2. 找到对应的桶 - 这是基于项目哈希码的直接数组查找。
  3. 如果存储桶存在，则尝试在存储桶中查找项目 - 这将遍历存储桶中的所有项目。

通过限制桶的数量，您增加了每个桶中的项目数，因此哈希集必须遍历的项目数，检查是否相等，以便查看项目是否存在。因此，查看给定项目是否存在需要更长的时间。

您可能已经减少了哈希集的内存占用；您甚至可能减少了插入时间，尽管我对此表示怀疑。你没有减少存在检查时间。

于 2012-12-12T10:39:36.143 回答
1

减少桶的数量不会提高性能。实际上，返回整数值的GetHashCode方法Int32本身，这对于性能来说是理想的，因为它会产生尽可能多的桶。

提供哈希表性能的东西是从键到哈希码的转换，这意味着它可以快速消除集合中的大部分项目。它必须考虑的唯一项目是同一个桶中的项目。如果您的存储桶很少，则意味着它可以消除更少的项目。

最糟糕的可能实现GetHashCode将导致所有项目进入同一个存储桶：

public override int GetHashCode() {
  return 0;
}

这仍然是一个有效的实现，但它意味着哈希表获得与常规列表相同的性能，即它必须遍历集合中的所有项目才能找到匹配项。

于 2012-12-12T10:54:24.803 回答
1

可以像这样实现一个简单HashSet<T>的（只是一个草图，不编译）

class HashSet<T>
{
    struct Element
    {
        int Hash;
        int Next;
        T item;
    }

    int[] buckets=new int[Capacity];
    Element[] data=new Element[Capacity];

    bool Contains(T item)
    {
        int hash=item.GetHashCode();
        // Bucket lookup is a simple array lookup => cheap
        int index=buckets[(uint)hash%Capacity];
        // Search for the actual item is linear in the number of items in the bucket
        while(index>=0)
        {
           if((data[index].Hash==hash) && Equals(data[index].Item, item))
             return true;
           index=data[index].Next;          
        }
        return false;
    }
}

如果您看一下，搜索成本Contains与存储桶中的项目数成正比。所以拥有更多的桶使得搜索成本更低，但是一旦桶的数量超过了项目的数量，额外的桶的收益就会迅速减少。

拥有不同的哈希码也可以尽早比较桶中的对象，避免潜在的昂贵Equals调用。

总之GetHashCode应该尽可能的多样化。工作是HashSet<T>将大空间减少到适当数量的桶，这大约是集合中的项目数（通常在两倍内）。

于 2012-12-12T11:07:20.167 回答