Hash Tables and Open Addressing In this lab you are given an implementation of an open addressing hash table. Download the files MyHashTable.java and CSCI225Lab7Driver.java and add them to a new project in Eclipse. Build and run the program it should make several failed attempts to insert items into three hash tables using the three different open addressing collision resolution schemes discussed in class. Complete the implementation of the three insertion methods lInsert (insert with linear probing), qInsert (insert with quadratic probing), and dInsert (insert with double hashing). dInsert should include a second hash function of your own design. You can refer to the lecture slides for guidelines on how to choose the second hash function. Use the CSCI225Lab7Driver to run experiments with different table sizes and different load factors. Note that the MyHashTable constructor has some commented code which forces the table size to a prime number. Document your experiments in a Word document or in a text file. Note at what table sizes and load factors each open addressing scheme does perform better than the others, or if they perform about the same. Submit your document and your modified MyHashTable.java to C4 for a lab credit.

// File: CSCI225Lab6Driver.java // Author: Geoffrey Tien/ Rita Ester // (your name here) // Date: June 25, 2017 // Description: Driver file for CSCI 225 lab 7

import java.util.Random;

public class CSCI225Lab7Driver { static Random r = new Random(System.nanoTime()); // The following constants can be changed static final int maxkey = 10000; // size of largest key value static final int tablesize = 503; // prime number. Can use non-prime and uncomment prime code from constructor static final int numkeys = 350;

public static void main(String[] args) { hashTestLinear(); hashTestQuadratic(); hashTestDouble(); }

public static void hashTestLinear() { MyHashTable htA = new MyHashTable(tablesize); for (int i = 0; i < numkeys; i++) { htA.lInsert(r.nextInt(maxkey)); // print result System.out.print("Linear probing: "); System.out.print(htA.printStats()); } }

public static void hashTestQuadratic() { MyHashTable htA = new MyHashTable(tablesize); for (int i = 0; i < numkeys; i++) { htA.qInsert(r.nextInt(maxkey)); // print result System.out.print("Quadratic probing: "); System.out.print(htA.printStats()); } }

public static void hashTestDouble() { MyHashTable htA = new MyHashTable(tablesize); for (int i = 0; i < numkeys; i++) { htA.dInsert(r.nextInt(maxkey)); // print result System.out.print("Double hashing: "); System.out.print(htA.printStats()); } } }

// File: MyHashTable.java

// Author: Geoffrey Tien/ Rita Ester

// (your name here)

// Date: Mar. 08, 2018

// Description: Hash table class for CSCI 225 lab 6

public class MyHashTable{

// constants

private static final int EMPTY = -1; // reserved, do not hash -1

// member attributes

private int[] table; // array of (integer) keys

private int capacity; // array size

private int count; // number of stored keys

// private double maxloadfactor; // load factor threshold before table grows

// statistics

private int totalprobes;

private int numinserts;

private int numfailures;

// private methods

// Return the next prime number larger than n

// If n is less than 100, return next prime larger than 100

private int nextPrime(int n)

{

int result = n;

if (result < 100) result = 100;

while (!isPrime(result))

{

result += 1;

}

return result;

}

private boolean isPrime(int n)

{

if (n < 2) return false;

if (n == 2) return true;

if (n % 2 == 0) return false;

return isPrime( n, 3 );

}

private boolean isPrime(int n, int divisor)

{

if ((divisor * divisor) > n) return true;

if ((n % divisor) == 0) return false;

return isPrime( n, divisor + 2 );

}

// public methods

// constructor

// make a Hash table with capacity at least size

public MyHashTable(int size)

{

int someprime = nextPrime(size);

capacity = size;

if (someprime != size)

{

System.out.println("Warning: capacity = " + size + " is not a prime number.");

// The following lines may be uncommented

// System.out.println("Using " + someprime + " instead.");

// capacity = someprime;

}

table = new int[capacity];

count = 0;

for (int i = 0; i < capacity; i++)

{

table[i] = EMPTY;

}

totalprobes = 0;

numinserts = 0;

numfailures = 0;

}

// clears / initializes the hash table

public void clear()

{

count = 0;

for (int i = 0; i < capacity; i++)

{

table[i] = EMPTY;

}

totalprobes = 0;

numinserts = 0;

numfailures = 0;

}

public String printStats()

{

String str = "";

str += "\tAvg. probes/insert = ";

str += probeRate() + "\t = ";

str += totalprobes + "/" + numinserts;

str += ", \tcap. = " + capacity;

str += ", \tfailed = " + numfailures + " ";

return str;

}

public double probeRate()

{

return (double) totalprobes / (double) numinserts;

}

public int hash(int key)

{

// this is not a very good hash function - similar key values

// will be mapped to similar array indices

return key % capacity;

}

// Insert key into the hash table.

// Use open addressing with linear probing

public void lInsert(int key)

{

int index = hash(key); //the index where to insert the key.

// ******* Your code to be completed here:

// the linear probing collision strategy, count the number of probes used.

// You need to prevent against infinite loops. You should limit the number

// of times you probe and print an error message when exceeding this limit.

if (table[index] == EMPTY){

table[index] = key;

totalprobes += probes;

numinserts += 1;

}

else {

numfailures += 1;

System.out.println("Warning: lInsert(" + key + ") found no EMPTY slot, insert failed.");

}

}

// Insert key into the hash table.

// Use open addressing with quadratic probing

public void qInsert(int key)

{

int index = hash(key); //the index where to insert the key.

int probes = 0;

// ******* Your code to be completed here:

// the quadratic probing collision strategy, count the number of probes used.

// You need to prevent against infinite loops. You should limit the number

// of times you probe and print an error message when exceeding this limit.

if (table[index] == EMPTY){

table[index] = key;

totalprobes += probes;

numinserts += 1;

}

else {

numfailures += 1;

System.out.println("Warning: lInsert(" + key + ") found no EMPTY slot, insert failed.");

}

}

// Insert key in the hash table.

// Use open addressing with double hashing. Use the existing hash function

// and also implement a second hash function of your own design.

public void dInsert(int key)

{

int index = hash(key); //the index where to insert the key.

int probes = 0;

// ******* Your code to be completed here:

// the double hashing collision strategy, count the number of probes used.

// You need to prevent against infinite loops. You should limit the number

// of times you probe and print an error message when exceeding this limit.

if (table[index] == EMPTY){

table[index] = key;

totalprobes += probes;

numinserts += 1;

}

else {

numfailures += 1;

System.out.println("Warning: lInsert(" + key + ") found no EMPTY slot, insert failed.");

}

}

// Print the contents of the hash table

public void print()

{

for (int i = 0; i < capacity; i++)

{

System.out.print("[" + i + "] ");

if (table[i] != EMPTY)

System.out.print("table[i]");

System.out.print(" ");

}

}

// Check if the value k is at index i. Use this to help you with testing

public boolean checkValue(int k, int i)

{

return table[i] == k;

}

}