Finish the methods in the Hashtable class. (third class posted below)

THIS PROVIDES THE DESCRIPTION OF WHAT NEEDS TO BE DONE IN EACH METHOD

// HashInterface.java - interface for hashing assignment

import java.util.Iterator;

public interface IHash {

/** Add a key to the hash table, if it is not currently in the table * @param key - the key to add * @return true on success, false on failure (duplicate) */ public abstract boolean insert(String key);

/** Remove a key from the hash table * @param key - the key to remove * @return true on success, false on failure (not in table) */ public abstract boolean remove(String key);

/** Search for a key in the hash table * @param key - the key to search for * @return the key on success, null on failure (not in table) */ public abstract String search(String key);

/** Get the number of elements in the hash table * @return the number of elements in the table */ public abstract int size();

/** Get the number of elements in the hash table at the given index * @param i the index in the hash table (0 to size-1) * @return the size of the list in the i^th bucket */ public abstract int size(int i);

/** Get an iterator that return the Strings stored in * the hash table one at a time. The order should be in order of entries in * the hash table itself and for a given bucket, the order in that list. * @return an Interator */ public abstract Iterator iterator();

/** Get an iterator for the i^th bucket * @param i the index in the hash table (0 to size-1) * @return null if the bucket is empty, otherwise an iterator for the bucket */ public abstract Iterator iterator(int i); /** Print the entire hash table. */ public abstract void print(); }

------------------------------------------------------------------------

This is the hash functions

@FunctionalInterface

interface HashFunction {

int hash(String key);

}

public class Hasher {

// Hashing algorithms, see specification

/**

* Hashing algorithms, see provided documentation in assignment

* @param hashFunction FIRST, SUM, PRIME, OR JAVA

* @return the corresponding HashFunction

*/

public static HashFunction make(String hashFunction) {

switch (hashFunction) {

case "FIRST":

// YOUR CODE HERE

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

return key.charAt(0);

}

};

case "SUM":

// YOUR CODE HERE

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

int sum = 0;

for(int i = 0;i < key.length(); i++){

sum += key.charAt(i);

}

return Math.abs(sum);

}

};

case "PRIME":

// YOUR CODE HERE

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

int hashCode = 7;

for(int i = 0;i < key.length(); i++){

hashCode*=31;

hashCode+=key.charAt(i);

}

return Math.abs(hashCode);

}

};

case "JAVA":

// YOUR CODE HERE

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

return key.hashCode();

}

};

default:

usage();

}

return null;

}

// Usage message

private static void usage() {

System.err.println("Usage: java Hasher ");

System.exit(1);

}

// Test code for hasher

public static void main(String[] args) {

args = Debug.init(args);

if (args.length != 2)

usage();

HashFunction sh = make(args[0]);

int hashCode = sh != null ? sh.hash(args[1]) : 0;

System.out.printf("'%s' hashes to %d using %s ", args[1], hashCode, args[0]);

}

}

------------------------------------------------------------------

Finish the methods in the HashTable class

// HashTable.java - code for hashing assignment

import java.util.*;

public class HashTable implements IHash {

// Method of hashing

HashFunction hasher;

// Hash table : an ArrayList of "buckets", which store the actual strings

ArrayList> hashTable;

/**

* Number of Elements

*/

int numberOfElements;

int size;

/**

* Initializes a new instance of HashTable.

*

* Initialize the instance variables.

* Note: when initializing the hashTable, make sure to allocate each entry in the HashTable

* to a new a HashBucket or null, your choice.

* @param size the size of the hashTable

* @param hasher the type of hashing function

*/

public HashTable(int size, HashFunction hasher) {

// YOUR CODE HERE

this.hasher = hasher;

this.size = size;

this.numberOfElements = 0;

for(int i = 0; i < size; i++) {

//hashTable.add(new LinkedList());

hashTable.add(new ArrayList());

}

}

public boolean insert(String key) {

// YOUR CODE HERE

int i = hasher.hash(key) % size;

if(hashTable.get(i).contains(key)) {

return false;

}

else{

hashTable.get(i).add(key);

numberOfElements++;

return true;

}

}

public boolean remove(String key) {

// YOUR CODE HERE

int i = hasher.hash(key) % size;

if(hashTable.get(i).contains(key)) {

hashTable.get(i).remove(key);

return true;

}

else {

return false;

}

}

public String search(String key) {

// YOUR CODE HERE

int i = hasher.hash(key) % size;

if(hashTable.get(i).contains(key)) {

return hashTable.get(i).toString();

}

else {

return null;

}

}

public int size() {

// YOUR CODE HERE

return size;

}

public int size(int index) {

// YOUR CODE HERE

for(int i = 0; i < index; i++) {

size = i;

}

return size;

}

// Return iterator for the entire hashTable,

// must iterate all hashBuckets that are not empty

public class HashIterator implements Iterator {

// The current index into the hashTable

private int currentIndex;

// The current iterator for that hashBucket

private Iterator currentIterator = null;

HashIterator() {

// YOUR CODE HERE

for(currentIndex = 0; currentIndex < size; currentIndex++) {

if(!hashTable.get(currentIndex).isEmpty()) {

}

}

}

public String next() {

// YOUR CODE HERE

return null;

}

public boolean hasNext() {

// YOUR CODE HERE

return false;

}

}

// Return an iterator for the hash table

public Iterator iterator() {

// YOUR CODE HERE

return null;

}

/**

* Does not use the iterator above. Iterates over one bucket.

*

* @param index the index of bucket to iterate over

* @return an iterator for that bucket

*/

public Iterator iterator(int index) {

List bucket = hashTable.get(index);

return bucket != null ? bucket.iterator() : null;

}

// Prints entire hash table.

// NOTE: This method is used extensively for testing.

public void print() {

Debug.printf("HashTable size: " + size());

for (int index = 0; index < hashTable.size(); index++) {

List list = hashTable.get(index);

if (list != null) {

Debug.printf("HashTable[%d]: %d entries", index, list.size());

for (String word : list) {

Debug.printf("String: %s (hash code %d)", word, hasher.hash(word));

}

}else {

Debug.printf("HashTable[%d]: %d entries", index, 0);

}

}

}

}