Java

HashTables

The constructor and insert method are done. The hash functions are also done.

Details above the abstract methods that are to be coded for in HashTable class in the IHash class (first posted class).

The hasher class is finished (the hash code second posted class).

Code is to be implemented in HashTable class (last posted class).

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 finished Hash code

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":

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

return key.charAt(0);

}

};

case "SUM":

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

int sum = 0;

for(int i=0;i

sum+=key.charAt(i);

}

return sum;

}

};

case "PRIME":

return new HashFunction() {

@Override

public int hash(String key) {

// TODO Auto-generated method stub

int hashCode = 7;

for(int i=0;i

hashCode*=31;

hashCode+=key.charAt(i);

}

return hashCode;

}

};

case "JAVA":

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

}

}

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

Code That needs to be finished is bold

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) {

this.hasher = hasher;

this.size = size;

this.numberOfElements = 0;

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

hashTable.add(new ArrayList());

numberOfElements++;

}

}

public boolean insert(String key) {

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

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

return false;

}

else{

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

return true;

}

}

public boolean remove(String key) {

// YOUR CODE HERE

}

public String search(String key) {

// YOUR CODE HERE

}

public int size() {

// YOUR CODE HERE

}

public int size(int index) {

// YOUR CODE HERE

}

// 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

}

public String next() {

// YOUR CODE HERE

}

public boolean hasNext() {

// YOUR CODE HERE

}

}

// Return an iterator for the hash table

public Iterator iterator() {

// YOUR CODE HERE

}

/**

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

}

}

}

}