c# - 我如何可靠地测试/基准测试 .Net HashSet<T> 对象的大小(包括空桶)？

Question

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

因为我打算用 C# 编写这个，所以我的“基准”将是 .Net HashSet<T>类(class)。我可以很容易地测试添加、删除和查找请求的执行时间，但我不知道如何测试 HashSet 的大小。基准对象，包括所有为 future 添加请求而空的桶。

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

明确地说，我不需要知道确切的字节数(我知道 .Net 框架使得获得许多类型对象的确切大小有点困难)但我更愿意在我执行各种类型的测试时，了解有多少桶正在使用中，有多少桶是空的，等待使用。

Answer 1

获取桶的数量和大小的最佳方法是使用反射。唯一的麻烦是您需要先了解集合的行为。在稍微阅读了代码并进行了一些尝试和错误之后，似乎您需要计算私有(private) 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。模拟哈希碰撞时，使用的桶数保持不变稳定，符合预期。删除元素会减少使用的桶数。