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

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
// 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 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 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();
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.