Определение средней длины цепи HashTable

Question

Я пытаюсь написать некоторые функции для отображения среднего количества используемых ведер и средней длины цепи в моей хэш-таблице. Я не знаю, как измерить эти вещи.

public Double bucketUsagePercentage(){ 

} 
public Double avgChainLength(){ 

} 

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

Answer 1

Как уже упоминались, вы могли бы на самом деле обернуть Hashtable, а затем следить за вставленный hashcodes Object + динамически рассчитать количество доступных ведер. Но, если вы знаете loadfactor (по умолчанию 0.75), вы можете создавать статические инструменты для «измерения» любой существующей 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; 
    } 
}