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.