2) Implement a procedure in your favorite computer language that generates 100,0

Question

2) Implement a procedure in your favorite computer language that generates 100,000 random integer numbers between 0 and 1000, and stores these numbers to 4 hash tables. The hash tables should have collision resolution by chaining based on (i) the multiplication hashing method with (a) A=0.2 and m=100, (b) A=0.5 and m=100, and (c) A=0.8 and m=100; and (ii) the division hashing method with (d) m=100. Run your procedure 5 times, and calculate the average number of keys per slot (from the 5 runs). Plot 4 histograms with the results (one for each hash table). Post your code, your results, and a deep analysis of your findings?
*Tip: Make sure to seed the random function so the drawn numbers are different each time.

Explanation / Answer

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Random;

public class HashAnalysis {

   public Map<Integer,List<Integer>> hashTableOne;
   public Map<Integer,List<Integer>> hashTableTwo;
   public Map<Integer,List<Integer>> hashTableThree;
   public Map<Integer,List<Integer>> hashTableFour;
  
   public HashAnalysis() {
       hashTableOne = new HashMap<Integer,List<Integer>>();
       hashTableTwo = new HashMap<Integer,List<Integer>>();
       hashTableThree = new HashMap<Integer,List<Integer>>();
       hashTableFour = new HashMap<Integer,List<Integer>>();
       startTest();
       calculateAverageChainLengths();
   }
  
   public void startTest() {
       Random random = new Random();
       for (int i=0; i<100000; i++) {
           int value = random.nextInt(1000);
           fillUpByMultiplicationHash(hashTableOne, 0.2, 100, value);
           fillUpByMultiplicationHash(hashTableTwo, 0.5, 100, value);
           fillUpByMultiplicationHash(hashTableThree, 0.8, 100, value);
           fillUpByDivisionHash(hashTableFour, 100, value);
       }
   }
  
   public void fillUpByMultiplicationHash(Map<Integer,List<Integer>> hashTable, double A, int m, int value) {
       int hashKey = (int) Math.floor(m * (value*A % 1));
       List<Integer> chain = hashTable.get(hashKey);
       if (chain == null) {
           chain = new ArrayList<Integer>();
           hashTable.put(hashKey, chain);
       }
       chain.add(value);
   }
  
   public void fillUpByDivisionHash(Map<Integer,List<Integer>> hashTable, int m, int value) {
       int hashKey = value%m;
       List<Integer> chain = hashTable.get(hashKey);
       if (chain == null) {
           chain = new ArrayList<Integer>();
           hashTable.put(hashKey, chain);
       }
       chain.add(value);
   }
  
   public void calculateAverageChainLengths() {
       double loadFactorOne = getAverageChainLength(hashTableOne, 100);
       double loadFactorTwo = getAverageChainLength(hashTableTwo, 100);
       double loadFactorThree = getAverageChainLength(hashTableThree, 100);
       double loadFactorFour = getAverageChainLength(hashTableFour, 100);
       System.out.println("LoadFactor-1 = " + loadFactorOne + ", LoadFactor-2 = " + loadFactorTwo + ", LoadFactor-3 = "+loadFactorThree+", LoadFactor-4 = "+loadFactorFour);
   }
  
   public double getAverageChainLength(Map<Integer,List<Integer>> hashTable, int m) {
       double loadFactor = 0;
       for (Entry<Integer, List<Integer>> entry : hashTable.entrySet()) {
           if (entry.getValue() != null) {
               loadFactor += entry.getValue().size();
           }
       }
       if (m == 0) {
           return -1;
       }
       return loadFactor/m;  
   }
  
   public static void main(String args[]) {
       for (int i=1; i<=5; i++) {
           System.out.println("Trail - " + i);
           new HashAnalysis();
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.