如何可靠地测试/基准测试.Net HashSet对象的大小(包括空存储桶)

本文关键字：对象 包括空 存储 测试 何可 基准测试 HashSet Net | 更新日期: 2023-09-27 18:31:47

作为个人教育和实验的练习，我想创建自己的HashTable课。 具体来说，我想编写这个对象，除了映射到现有接口进行测试之外，不使用任何现有代码（即此对象不会从另一个类继承）。

由于我计划用 C# 编写本文，因此我的"基准测试"将是 .Net HashSet<T> 类。 我可以轻松地测试添加、删除和查找请求的执行时间，但我不知道如何测试HashSet基准对象的大小，包括所有空的存储桶以供将来添加请求。

如何跟踪HashSet<t>对象动态增长的大小，以便为将来的插入腾出空间？

需要明确的是，我不需要知道确切的字节数（我知道 .Net 框架使得获取许多类型对象的确切大小有点困难），而是我更愿意知道有多少桶正在使用中，有多少是空的，等待使用， 因为我执行各种类型的测试。

如何可靠地测试/基准测试.Net HashSet<T>对象的大小(包括空存储桶)

获取存储桶数量和大小的最佳方法是使用反射。唯一的麻烦是您需要首先了解集合的行为。在稍微阅读了代码并做了一些反复试验之后，似乎您需要计算私有m_buckets数组的大小才能获得存储桶的数量，并计算大于 0 的值的数量才能获得使用的存储桶数量。该方法如下所示：

static void CountBuckets<T>(HashSet<T> hashSet)
{
    var field = typeof(HashSet<T>).GetField("m_buckets", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic);
    var buckets = (int[])field.GetValue(hashSet);
    int numberOfBuckets = 0;
    int numberOfBucketsUsed = 0;
    if (buckets != null)
    {
        numberOfBuckets = buckets.Length;
        numberOfBucketsUsed = buckets.Where(i => i != 0).Count();
    }
    Console.WriteLine("Number of buckets: {0} / Used: {1}", numberOfBuckets, numberOfBucketsUsed);
}

为了测试它，我首先创建了一个自定义类，我可以在其中手动设置哈希代码：

public class Hash
{
    private readonly int hashCode;
    public Hash(int hashCode)
    {
        this.hashCode = hashCode;
    }
    public override int GetHashCode()
    {
        return this.hashCode;
    }
}

从那里，我做了一些测试：

    var hashSet = new HashSet<Hash>();
    CountBuckets(hashSet);
    // Number of buckets: 0 / Used: 0
    var firstHash = new Hash(0);
    hashSet.Add(firstHash);
    CountBuckets(hashSet);
    // Number of buckets: 3 / Used: 1
    hashSet.Add(new Hash(1));
    hashSet.Add(new Hash(2));
    CountBuckets(hashSet);
    // Number of buckets: 3 / Used: 3
    hashSet.Add(new Hash(3));
    CountBuckets(hashSet);
    // Number of buckets: 7 / Used: 4
    hashSet.Add(new Hash(1));
    CountBuckets(hashSet);
    // Number of buckets: 7 / Used: 4
    hashSet.Remove(firstHash);
    CountBuckets(hashSet);
    // Number of buckets: 7 / Used: 3

这听起来与直觉行为一致。首先，存储桶数为 0。添加元素后，它将扩展到 3。在添加第四个元素之前，存储桶的数量保持稳定，从而将计数扩展到 7。模拟哈希冲突时，已用存储桶的数量保持稳定，正如预期的那样。删除元素会减少已用存储桶的数量。

我对HashSet的内部不是很熟悉，但您可以看到它的源代码并使用反射来获取其内部值：

HashSet<int> hashSet = new HashSet<int>();
var countField = typeof(HashSet<int>).GetField("m_count", BindingFlags.NonPublic | BindingFlags.Instance);
var freeListField = typeof(HashSet<int>).GetField("m_freeList", BindingFlags.NonPublic | BindingFlags.Instance);
var count = countField.GetValue(hashSet);
var freeList = freeListField.GetValue(hashSet);

注意：这种侵犯私有会员访问权限的行为当然是非常丑陋的，但我相信在您的开发/测试阶段是可以接受的。

这是

有趣的问题强文本...我有一个激进的建议给你：

启动应用程序并在初始化 HashSet 之前获取内存大小。您可以使用 Process.GetCurrentProcess（） 执行此操作。WorkingSet64 （on msdn： http://msdn.microsoft.com/en-us/library/system.diagnostics.process.workingset64（v=vs.110）.aspx）

然后填充您的 HashSet 并打印 Process.GetCurrentProcess（）。再次工作集64。区别在于您寻找的大小。

相关文章：