This is the code for hash tables. Table size for linear probing and double hashing is assumed to be a prime, table size for quadratic probing is a power of 2.

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;
    }
}

The testing program:

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;
    }
}


This is an example from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.