/*  CSI2114 Lab 9 - testHashingFunctions.java
 *  
 *  tests five hashing functions: calculates number of collisions for each one.
 *
 *  Usage: java hash
 *  
 *  by Jeff Souza 
 *
 */

public class testHashingFunctions {

	public static void main(String[] args) {

		final int numHashFunctions = 5;
		final int numAddresses = 997;
		final int numKeys = 800;

		// the hash tables -> keep track of only the number of keys per address
		int[][] hashTable = new int[numHashFunctions][numAddresses];

		// total number of collisions of each function
		int[] totNumCollisions = new int[numHashFunctions];
	
		// creates a random number, calculates its hash value and adds to its address
		for (int i=0; i<numKeys; i++) {
			int rand = randNumber(999999);
			hashTable[0][hashF1(rand)]++;
			hashTable[1][hashF2(rand)]++;		
			hashTable[2][hashF3(rand)]++;		
			hashTable[3][hashF4(rand)]++;		
			hashTable[4][hashF5(rand)]++;		
		}

		// calculates total number of collisions
		for (int j=0; j<numAddresses; j++) {
			for (int k=0; k<numHashFunctions; k++) {
				if (hashTable[k][j]>1) totNumCollisions[k] += (hashTable[k][j]-1);
			}
		}

		// reports the total number of collisions
      	for (int k=0; k<numHashFunctions; k++) {
			System.out.println("Number of Collisions for F" + (k+1) + " = " + totNumCollisions[k]);
		}
	}

	// F1
	static int hashF1(int a) {
		return (a % 997);
	}

	// F2
	static int hashF2(int a) {
		return ((a/100) % 997);
	}

	// F3
	static int hashF3(int a) {
		return (((a%997)*(a%997))%997);
	}

	// F4
	static int hashF4(int a) {
		int m = 256;
		double c =  0.6180339887; 
		return (int)java.lang.Math.floor(m*(a*c - java.lang.Math.floor(a*c)));
	}

	// F5 -> universal hashing (selects between F1, F2, F3 or F4 at random)
	static int hashF5(int a) {
		int rand = (int)(Math.random()*100);
		if (rand<=25) return hashF1(a);
		if (rand<=50) return hashF2(a);
		if (rand<=75) return hashF3(a);
		return hashF4(a);
	}

	// generates a random number between 1 and max
	protected static int randNumber(int max) {
		return (int)(Math.random()*max);
	} 
}