public class HashTable {
    int tableSize = 137; // 137 is a prime
    private Integer [] elements = new Integer[tableSize]; 
    // modes of open addressing: 'L' - linear probing
    // 'Q' - quadratic probing, 'D' - double hashing
    private char mode = 'L'; 
    private int secondPrime = 13; // second prime for double hashing
                                  // default value is 13
    // public int i = 0; // a global variable used for quadratic probing

    public HashTable(char mode, int tableSize) {
	this.mode = mode;
	this.tableSize = tableSize;
    }

     public HashTable(char mode, int tableSize, int secondPrime) {
	this.mode = mode;
	this.tableSize = tableSize;
	this.secondPrime = secondPrime;
    }
    
    // returns true if the element has been successfully inserted,
    // false otherwise
    public boolean insert(int n) {
	int index = hash(n);
	for (int i = 0; i < tableSize; ++i) {
	    if (elements[index] == null) {
		elements[index] = new Integer(n);
		return true;
	    }
	    index = secondHash(n,i);
	}
	return false; // couldn't find a space for the element
    }

    // searches for n, returns its position
    // returns -1 if n is not found 
    public int search(int n) {
	int index = hash(n);
	
	for (int i = 0; i < tableSize; ++i) {
	    if (elements[index] == null) {
		return -1;
	    } else if (elements[index].intValue() == n) {
		return index;
	    }
	    index = secondHash(n,i);
	}
	return -1; // the table is full, the element not found
    }

    public void print() {
	for (int i = 0; i < tableSize; ++i) {
	    System.out.println("Position = " + i + " Element = " 
			       + elements[i]);
	}
    }

    private int hash(int k) {
	return k % tableSize;
    }

    // secondary hashing: to resolve collisions
    private int secondHash(int k, int i) {
	if (mode == 'L') return linear(k,i);
	if (mode == 'Q') return quadratic(k,i);
	if (mode == 'D') return doubleH(k,i);
	else {
	    System.out.println("Unknown mode");
	    System.exit(1);
	}
	return -1;
    }

    // finds the next index for an element 
    // using linear probing
    // i is the probe number
    private int linear(int k, int i) {
	return (hash(k) + i) % tableSize;
    }

    // finds the next index for an element
    // using quadratic probing
    // i is the probe number
    private int quadratic(int k, int i) {
	return (hash(k) +  i * (i + 1) / 2 ) % tableSize;
    }

    // finds the next index for an element
    // using double hashing
    // i is the probe number
    private int doubleH(int k, int i) {
	return (hash(k) + i * (k % secondPrime + 1)) % tableSize;
    }

    // straightforward search, used for debugging
    public int search2(int n) {
	for (int i = 0; i < tableSize; ++i) {
	    if (elements[i] != null && elements[i].intValue() == n) return i;
	}
	return -1;
    }
}

import java.util.*;

public class TestHashTable2 {
    public static void main(String [] args) {
	int tableSize = 67;
	int tableSizeQuadratic = 64;
	int secondPrime = 13;
	if (!isPrime(tableSize)) {
	    System.out.println("WARNING: " + tableSize + " is not a prime, "
			       + "bad choice for table size");
	}
	if (!isPrime(secondPrime)) {
	    System.out.println("WARNING: " + secondPrime + " is not a prime, "
			       + "bad choice for double hashing");
	}
	HashTable table1 = new HashTable('L',tableSize);
	HashTable table2 = new HashTable('Q',tableSizeQuadratic);
	HashTable table3 = new HashTable('D',tableSize,secondPrime);
	Random r = new Random();
	for (int i = 0; i < 63; ++i) {
	    int n = r.nextInt(1000);
	    if (!table1.insert(n)) {
		System.out.println("Can't insert " + n + " with linear probing");
		//table1.print();
	    }
	    if (!table2.insert(n)) {
		System.out.println("Can't insert " + n + " with quadratic probing");
		//table2.print();
	    }
	    if (!table3.insert(n)) {
		System.out.println("Can't insert " + n + " with double hashing");
		//table3.print();
	    }
	}
	
	System.out.println("Linear probing:");
	table1.print();
	System.out.println("Quadratic probing");
	table2.print();
	System.out.println("Double hashing");
	table3.print();

	
	// Testing search
	for (int i = 0; i < 1000; ++i) {
	    int count1 = 0; 
	    int count2 = 0;
	    int count3 = 0;
	    int n = r.nextInt(1000);
	    int ind = table1.search(n);
	    if (ind != -1) {
		System.out.println("Found " + n + " in table1 at index " 
				   + ind);
		count1++;
	    }
	    ind = table2.search(n);
	    if (ind != -1) {
		System.out.println("Found " + n + " in table2 at index " 
				   + ind);
		count2++;
	    }
	    ind = table3.search(n);
	    if (ind != -1) {
		System.out.println("Found " + n + " in table3 at index " 
				   + ind);
		count3++;
	    }
	    if (count1 != count2 || count2 != count3) {
		// the element was found in some tables but not all
		System.out.println("**** Houston, we have a problem! ****");
		System.out.println("table1: " + count1 + " table2: " + count2 +
				   " table3: " + count3);
		// System.out.println("Direct search for " + n + ": " 
		// + table2.search2(n));
	    }
	} 
    }

    public static boolean isPrime(int n) {
	int m = (int) Math.sqrt(n) + 1;
	for (int i = 2; i <= m; ++i) {
	    if (n % m == 0) return false;
	}
	return true;
    }
}