确定 HashTable 平均链长

Question

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

public Double bucketUsagePercentage(){

}
public Double avgChainLength(){

}

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

Answer 1

如前所述，您实际上可以包装哈希表，然后跟踪插入的对象哈希码 + 动态计算可用桶的数量。但是，假设您知道负载因子（默认值 0.75），您可以为 "measure" 任何现有的 Hashtable 创建静态工具（您也可以轻松地将其更改为适用于 HashSets）。

*只是强调一下，由于初始容量要求，结果在一开始可能不是 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;
    }
}

确定 HashTable 平均链长

Determining HashTable average chain length

java

hashtable

hashmap

bucket