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

Question

作为个人教育和实验的练习,我想创建自己的HashTable课程.具体来说,我想编写此对象,而不使用任何现有代码(即此对象不会从其他类继承),而不是映射到现有接口以进行测试.

由于我打算用C#写这个,我的"基准"将成为.Net HashSet<T>类.我可以轻松地测试添加,删除和查找请求的执行时间,但我不知道如何测试HashSet基准测试对象的大小,包括所有未来添加请求为空的存储桶.

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

要清楚,我不需要知道确切的字节数(我知道.Net框架使得获得许多类型对象的确切大小有点困难)但我宁愿知道如何当我执行各种类型的测试时,许多桶正在使用,有多少是空的,等待使用.

Answer 1

获取桶的数量和大小的最佳方法是使用反射.唯一的麻烦是你需要先了解集合的行为.稍微阅读代码并进行一些试验和错误后,您似乎需要计算私有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.当模拟哈希冲突时,使用的桶的数量保持不变如预期的那样稳定.删除元素会减少使用的桶数.