c# - GetHashCode 和桶

Question

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

据我对这篇文章的理解(我之前也这么认为)，桶列表本身将一定数量的元素分组到每个桶中。一个桶用hashcode表示，即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 个桶。但恰恰相反，我想我只是产生了所谓的碰撞音调，而不是改进任何东西。但话又说回来，遗愿 list 是如何运作的？

Answer 1

一个 Contains 检查基本上:

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

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

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