import java.util.LinkedList;
import java.util.List;

public class HashingWSeperateChaining {
private List[] hashTable;
private int tableSize;

public HashingWSeperateChaining(int TableSize)
{
tableSize = TableSize;
hashTable = new List[tableSize];

for (int i = 0; i < tableSize; i++) {
hashTable[i] = new LinkedList<Integer>();
}
}

private int Hash(Integer value)
{
return value % tableSize;
}

public void InsertNewValue(Integer value)
{
List listForKey = hashTable[Hash(value)];
listForKey.add(value);
}
}

public class HashingWLinearProbing {
private Integer[] hashTable;
private int tableSize;
private int totalPrimaryClusterCount;
public HashingWLinearProbing(int TableSize)
{
tableSize = TableSize;
hashTable = new Integer[tableSize];
totalPrimaryClusterCount = 0;
}

private int Hash(Integer value)
{
return value % tableSize;
}


public void InsertNewValue(Integer value)
{
int key = Hash(value);

int iterator = 0;
while (hashTable[(key + iterator) % tableSize]!= null) {
totalPrimaryClusterCount++;
System.out.print("Primary Cluster on Key: " + (key + iterator) % tableSize + " Value: " + value + "\n");
iterator++;
}
hashTable[(key + iterator) % tableSize] = value;

}
}

public class HashingWQuadraticProbing {
private Integer[] hashTable;
private int tableSize;

public HashingWQuadraticProbing(int TableSize)
{
tableSize = TableSize;
hashTable = new Integer[tableSize];

}

private int Hash(Integer value)
{
return value % tableSize;
}


public void InsertNewValue(Integer value)
{
int key = Hash(value);

int iterator = 0;
while (hashTable[(key + ((Integer) Math.pow(iterator,2))) % tableSize]!= null) {
iterator++;
}
hashTable[(key + ((Integer) Math.pow(iterator,2))) % tableSize] = value;
}
}

public class HashingWDoubleHashing {
private Integer[] hashTable;

private int tableSize;
private int tableSize2;

public HashingWDoubleHashing(int TableSize, int TableSize2)
{
tableSize = TableSize;
tableSize2 = TableSize2;
hashTable = new Integer[tableSize];

}

private int Hash(Integer value)
{
return value % tableSize;
}



private int Hash2(Integer value)
{
return tableSize2 - (value % tableSize2);
}

public void InsertNewValue(Integer value)
{
int key = Hash(value);
int key2 = Hash2(value);
int iterator = 0;
while (hashTable[(key + (key2 * iterator)) % tableSize]!= null) {
iterator++;
}
hashTable[(key + (key2 * iterator)) % tableSize] = value;
}
}

public class Main {

private final static int TABLE_SIZE = 1000003;
private final static int TABLE_SIZE2 = 1009;
private final static int NUMBER_SIZE = 500000;
private final static int MAX_NUMBER = 1000000000;

public static void main(String args[])
{
UniqueRandomizer rand = new UniqueRandomizer();

int i;
long start,end;

HashingWSeperateChaining hashingWSeperateChaining = new HashingWSeperateChaining(TABLE_SIZE);

start = System.currentTimeMillis();
for (i = 0; i < NUMBER_SIZE; i++) {
hashingWSeperateChaining.InsertNewValue(rand.RandomNew(MAX_NUMBER));
}
end = System.currentTimeMillis();

System.out.print("Execution time for Hashing With Seperate Chaining in milliseconds: " + (end-start) + "\n");

rand.Reset();

HashingWLinearProbing hashingWLinearProbing = new HashingWLinearProbing(TABLE_SIZE);

start = System.currentTimeMillis();
for (i = 0; i < NUMBER_SIZE; i++) {
hashingWLinearProbing.InsertNewValue(rand.RandomNew(MAX_NUMBER));
}
end = System.currentTimeMillis();

System.out.print("Execution time for Hashing With Linear Probing in milliseconds: " + (end-start) + "\n");

System.out.print("Total Primary Cluster Count: " + hashingWLinearProbing.GetTotalPrimaryClusterCount() + "\n");
rand.Reset();

HashingWQuadraticProbing hashingWQuadraticProbing = new HashingWQuadraticProbing(TABLE_SIZE);

start = System.currentTimeMillis();
for (i = 0; i < NUMBER_SIZE; i++) {
hashingWQuadraticProbing.InsertNewValue(rand.RandomNew(MAX_NUMBER));
}
end = System.currentTimeMillis();

System.out.print("Execution time for Hashing With Quadratic Probing in milliseconds: " + (end-start) + "\n");
System.out.print("Total Secondary Cluster Count: " + hashingWQuadraticProbing.GetTotalSecondaryClusterCount() + "\n");

rand.Reset();

HashingWDoubleHashing hashingWDoubleHashing = new HashingWDoubleHashing(TABLE_SIZE,TABLE_SIZE2);

start = System.currentTimeMillis();
for (i = 0; i < NUMBER_SIZE; i++) {
hashingWDoubleHashing.InsertNewValue(rand.RandomNew(MAX_NUMBER));
}
end = System.currentTimeMillis();System.out.print("Execution time for Hashing With Double Hashing in milliseconds: " + (end-start) + "\n"); }}