java - 确定哈希表平均链长

Question

我正在尝试编写一些函数来显示正在使用的桶的平均数量以及哈希表中的平均链长度。我不知道如何衡量这些东西。

public Double bucketUsagePercentage(){

}
public Double avgChainLength(){

}

public void printStats(){
    System.out.println("LoadFactor: " + getTableLoad());
}

Answer 1

正如已经提到的，您实际上可以包装哈希表，然后跟踪插入的对象哈希码+动态计算可用存储桶的数量。但是，假设您知道负载因子(默认 0.75)，您可以创建静态工具来“测量”任何现有的哈希表(您也可以轻松更改它以适用于哈希集)。

*只是想强调一下，由于初始容量要求，结果一开始可能不是 100% 准确，因为初始存储桶是固定的，直到需要重新哈希为止。

import java.util.Hashtable;

public class HashMetrics {


    public static double bucketUsagePercentage(Hashtable<?,?> a, double loadfactor) {
        int bucketSize = getBucketSize(a, loadfactor);
        int[] bucketFrequency = new int[bucketSize];
        for (Object k : a.keySet()) {
            bucketFrequency[k.hashCode() % bucketSize]++;
        }
        int counter = 0;
        for (int i : bucketFrequency) {
            if (i > 0) counter++;
        }
        return (double)counter / bucketSize;
    }

    //skip empty buckets (very similar to previous function, last line is only changed)
    public static double averageChainLength(Hashtable<?,?> a, double loadfactor) {
        int bucketSize = getBucketSize(a, loadfactor);
        int[] bucketFrequency = new int[bucketSize];
        for (Object k : a.keySet()) {
            bucketFrequency[k.hashCode() % bucketSize]++;
        }
        int counter = 0;
        for (int i : bucketFrequency) {
            if (i > 0) counter++;
        }

        return (double)a.size() / counter;
    }

    public static int log2(int number) {
        if(number == 0)
            return 0;
        return 31 - Integer.numberOfLeadingZeros(number);
    }

    public static int getBucketSize(Hashtable<?,?> a, double loadFactor) {
        int n = a.size();
        int bucketSize = 2 << log2(n);
        if (bucketSize * loadFactor <= n) {
            bucketSize <<= 1;
        }
        return bucketSize;
    }
}