我试图更好地理解散列集的内部结构,例如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 是如何运作的?
最佳答案
一个 Contains
检查基本上:
- 获取项目的哈希码。
- 找到相应的桶 - 这是基于项目哈希码的直接数组查找。
- 如果存储桶存在,则尝试在存储桶中查找项目 - 这将遍历存储桶中的所有项目。
通过限制桶的数量,您增加了每个桶中的项目数量,因此哈希集必须迭代的项目数量,检查是否相等,以便查看项目是否存在。因此,查看给定项目是否存在需要更长的时间。
您可能已经减少了哈希集的内存占用;你可能甚至减少了插入时间,尽管我对此表示怀疑。您没有减少存在检查时间。
关于c# - GetHashCode 和桶,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13837774/