import java.util.ArrayList;
import java.util.Random;
import java.io.FileWriter;

public class Hashing {

int m;
ArrayList<ArrayList<Integer>> table;

public Hashing(int m) {
this.m = m;
this.table = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < m; i++) {
   table.add(new ArrayList<Integer>());
}
}

public void insertMultiplicationHashing(int k, double A) {
int hash = (int)(m*(k*A % 1));
table.get(hash).add(k);
}

public void insertDivisionHashing(int k, double A) {
int hash = k % m;
table.get(hash).add(k);
}

public double exportCSV(String filename) {
int count = 0;
int total = 0;
try {
   FileWriter fw = new FileWriter(filename);
   for (int i = 0; i < m; i++) {
   ArrayList<Integer> row = table.get(i);
   if (row.size() == 0) {
      continue;
   }
   String result = i+","+row.size();
   total += row.size();
   fw.write(result+"\n");
   count++;
   }
   fw.close();
} catch (Exception e) {
   System.err.println(e.getMessage());
}
return total*1.0/count;
}

public static void main(String[] args) {
int total = 100000;
int m = 100;

int seed = 0;

double A;
double avg = 0.0;

A = 0.2;
System.out.println("Multiplication Hashing m="+m+" A="+A);
for (int trial = 0; trial < 4; trial++) {
   Random r = new Random(seed++);
   A = 0.2;
   Hashing h1 = new Hashing(m);
   for (int i = 0; i < total; i++) {
   h1.insertMultiplicationHashing(r.nextInt(1000), A);
   }
   avg = h1.exportCSV("Multiplication Hashing A="+A+" m="+m+" "+trial+".csv");
}
System.out.println("Average number of keys per slot: "+String.format("%.2f",avg)+"\n");

A = 0.5;
System.out.println("Multiplication Hashing m="+m+" A="+A);
for (int trial = 0; trial < 4; trial++) {
   Random r = new Random(seed++);
   Hashing h1 = new Hashing(m);
   for (int i = 0; i < total; i++) {
   h1.insertMultiplicationHashing(r.nextInt(1000), A);
   }
   avg = h1.exportCSV("Multiplication Hashing A="+A+" m="+m+" "+trial+".csv");
}
System.out.println("Average number of keys per slot: "+String.format("%.2f",avg)+"\n");

A = 0.8;

Chapter 5 &amp; 6 Discussion: 1. Discuss the ramification of dro...

Chapter 5 & 6 Discussion: 1. Discuss the ramification of dro...