This is the code for hash tables.


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);
	int count = 0;
	while (elements[index] != null && count < tableSize) {
	    index = secondHash(n,index);
	    count++;
	}
	i = 0; // reset the counter used by quadratic probing
	if (elements[index] != null) {
	    System.out.println("Cannot insert " + n);
	    return false;
	}
	elements[index] = new Integer(n);
	//System.out.println("mode = " + mode + " inserting " + n +
	//	   " at index " + index);
	return true;
    }

    // searches for n, returns its position
    // returns -1 if n is not found 
    public int search(int n) {
	int index = hash(n);
	int count = 0;
	while (elements[index] != null && count <= tableSize) {
	    if (elements[index].intValue() == n) {
		i = 0; // need to reset the index before returning
		return index;
	    }
	    index = secondHash(n,index);
	    count++;
	}
	i = 0; // reset the counter used by quadratic probing
	return -1;
    }

    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 index) {
	if (mode == 'L') return linear(k,index);
	if (mode == 'Q') return quadratic(k,index);
	if (mode == 'D') return doubleH(k,index);
	else {
	    System.out.println("Unknown mode");
	    System.exit(1);
	}
	return -1;
    }

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

    // finds the next index for an element
    // using quadratic probing
    // uses the global variable i which counts the number of calls
    // to quadratic for this element
    private int quadratic(int k, int index) {
	i++;
	return (hash(k) +  i * i) % tableSize;
    }

    // finds the next index for an element
    // using double hashing
    private int doubleH(int k, int index) {
	return (index + secondPrime - k % secondPrime) % 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 TestHashTable {
    public static void main(String [] args) {
	int tableSize = 43;
	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',tableSize);
	HashTable table3 = new HashTable('D',tableSize,secondPrime);
	Random r = new Random();
	for (int i = 0; i < 40; ++i) {
	    int n = r.nextInt(1000);
	    table1.insert(n);
	    table2.insert(n);
	    table3.insert(n);
	}
	System.out.println("Linear probing:");
	table1.print();
	System.out.println("Quadratic probing");
	table2.print();
	System.out.println("Double hashing");
	table3.print();
    }

    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;
    }
}
And another testing program that tests the search method as well as insert. You might notice (if you run it several time) that quadratic probing occasionally doesn't insert an element even though the table is not full. I'll explain this in class on Friday.

import java.util.*;

public class TestHashTable {
    public static void main(String [] args) {
	int tableSize = 43;
	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',tableSize);
	HashTable table3 = new HashTable('D',tableSize,secondPrime);
	Random r = new Random();
	for (int i = 0; i < 40; ++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.