Question

INSERT STRING INTO SEPARATE CHAIN HASHTABLE & ITERATE THROUGH HASHTABLE: JAVA

_________________________________________________________________________________________________________________

import java.util.*;

public class HashTable implements IHash {
// Method of hashing
private HashFunction hasher;
// Hash table : an ArrayList of "buckets", which store the actual strings
private ArrayList<List<String>> hashTable;
/**
* Number of Elements
*/
private int numberOfElements;
private int numberOfBuckets;

/**
* Initializes a new instance of HashTable.
* <p>
* Initialize the instance variables. <br>
* Note: when initializing the hashTable, make sure to allocate each entry in the HashTable
* to a new a HashBucket or null, your choice.
* @param numberOfBuckets the size of the hashTable
* @param hasher the type of hashing function
*/
public HashTable(int numberOfBuckets, HashFunction hasher) {
   this.hasher = hasher;
   this.numberOfBuckets = numberOfBuckets;
   this.hashTable = new ArrayList<>();
   for (int i = 0; i < numberOfBuckets; i++) {
       hashTable.add(null);
   }
   this.numberOfElements = 0;
}

public boolean insert(String key) { // THIS METHOD NEEDS HELP
   int bucketToPlaceIn = hasher.hash(key) % numberOfBuckets;
   List<String> bucketContents = hashTable.get(bucketToPlaceIn);
   // if bucketToPlaceIn is null
       // initialize bucketContents
       // set hashTable at bucketToPlaceIn equal to bucketContents
   // if bucketContents doesn't contain the key
       // add it
       // return true
   return false;
}

public boolean remove(String key) {
   for (int i = 0; i < hashTable.size(); i++) {
       for (int j = 0; j < hashTable.get(i).size(); j++) {
           if (hashTable.get(i).get(j) == key) {
               hashTable.get(i).remove(j);
               return true;
           }
       }
   }
return false;
}

public String search(String key) {
   for (int i = 0; i < hashTable.size(); i++) {
       for (int j = 0; j < hashTable.get(i).size(); j++) {
           if (hashTable.get(i).get(j) == key) {
               return key;
           }
       }
   }
   return null;
}

public int size() {
   int returnSize = 0;
   for (int i = 0; i < hashTable.size(); i++) {
       returnSize += hashTable.get(i).size();
   }
   return returnSize;
}

public int size(int index) {
   int returnSize = hashTable.get(index).size();
return returnSize;
}

// Return iterator for the entire hashTable,
// must iterate all hashBuckets that are not empty
public class HashIterator implements Iterator<String> {
// The current index into the hashTable
private int currentIndex;
// The current iterator for that hashBucket
private Iterator<String> currentIterator = null;

HashIterator() { // THIS METHOD NEEDS HELP
// YOUR CODE HERE
}

public String next() { // THIS METHOD NEEDS HELP
// YOUR CODE HERE
return null;
}

public boolean hasNext() { // THIS METHOD NEEDS HELP
// YOUR CODE HERE
return false;
}
}

// Return an iterator for the hash table
public Iterator<String> iterator() { // THIS METHOD NEEDS HELP
// 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<String> iterator(int index) {
List<String> 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<String> 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);
}
}
}
}

FOR REFERENCE

// 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<String> 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<String> iterator(int i);
  
/** Print the entire hash table.
*/
public abstract void print();
}

@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":
   return (String key) -> {
       return Math.abs(key.charAt(0));
   };
          
case "SUM":
   return (String key) -> {
   int sumReturn = 0;
       for (int i = 0; i < key.length(); i++) {
       sumReturn += Math.abs(key.charAt(i));
   }
               return sumReturn;
   };

case "PRIME":
   return (String key) -> {
   int sumReturn = 7;
       for (int i = 0; i < key.length(); i++) {
       sumReturn = (31*sumReturn) + Math.abs(key.charAt(i));
   }
               return sumReturn;
   };

case "JAVA":
   return (String key) -> {
       return key.hashCode();
   };

default:
usage();
}
return null;
}

// Usage message
private static void usage() {
System.err.println("Usage: java Hasher <FIRST|SUM|PRIME|JAVA> <word>");
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\n", args[1], hashCode, args[0]);
}
}

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Attached only HashTable.java since other files are not modified.

// HashTable.java

import java.util.*;

public class HashTable implements IHash {

      // Method of hashing

      private HashFunction hasher;

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

      private ArrayList<List<String>> hashTable;

      private int numberOfBuckets;

      /**

      * Initializes a new instance of HashTable.

      * <p>

      * Initialize the instance variables. <br>

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

      * in the HashTable to a new a HashBucket or null, your choice.

      *

      * @param numberOfBuckets

      *            the size of the hashTable

      * @param hasher

      *            the type of hashing function

      */

      public HashTable(int numberOfBuckets, HashFunction hasher) {

            this.hasher = hasher;

            this.numberOfBuckets = numberOfBuckets;

            this.hashTable = new ArrayList<List<String>>();

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

                  hashTable.add(null);

            }

      }

      public boolean insert(String key) { // THIS METHOD NEEDS HELP

            int bucketToPlaceIn = hasher.hash(key) % numberOfBuckets;

            // if bucketToPlaceIn is null

            // initialize bucketContents

            if (hashTable.get(bucketToPlaceIn) == null) {

                  hashTable.set(bucketToPlaceIn, new ArrayList<String>());

            }

            // set hashTable at bucketToPlaceIn equal to bucketContents

            List<String> bucketContents = hashTable.get(bucketToPlaceIn);

            // if bucketContents doesn't contain the key

            // add it

            // return true

            if (!bucketContents.contains(key)) {

                  bucketContents.add(key);

                  return true;

            }

            return false; // already exist

      }

      public boolean remove(String key) {

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

                  for (int j = 0; j < hashTable.get(i).size(); j++) {

                        if (hashTable.get(i).get(j) == key) {

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

                              return true;

                        }

                  }

            }

            return false;

      }

      public String search(String key) {

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

                  for (int j = 0; j < hashTable.get(i).size(); j++) {

                        if (hashTable.get(i).get(j) == key) {

                              return key;

                        }

                  }

            }

            return null;

      }

      public int size() {

            int returnSize = 0;

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

                  returnSize += hashTable.get(i).size();

            }

            return returnSize;

      }

      public int size(int index) {

            int returnSize = hashTable.get(index).size();

            return returnSize;

      }

      // Return iterator for the entire hashTable,

      // must iterate all hashBuckets that are not empty

      public class HashIterator implements Iterator<String> {

            // The current index into the hashTable

            private int currentIndex;

            // The current iterator for that hashBucket

            private Iterator<String> currentIterator = null;

            HashIterator() { // THIS METHOD NEEDS HELP

                  currentIndex = 0;

                  // finding the first bucket that is not null,

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

                        if (hashTable.get(i) != null) {

                              // found, assigning i to current index

                              currentIndex = i;

                              // getting an iterator for current bucket and assigning to

                              // currentIterator

                              currentIterator = hashTable.get(i).iterator();

                              break; // exiting loop

                        }

                  }

            }

            public String next() {

                  // getting next item

                  String item = currentIterator.next();

                  // if iterator is empty, finding the next bucket that is not null

                  // and assigning index and iterator to currentIndex and

                  // currentIterator respectively

                  if (!currentIterator.hasNext()) {

                        for (int i = currentIndex + 1; i < hashTable.size(); i++) {

                              if (hashTable.get(i) != null) {

                                    // found

                                    currentIndex = i;

                                    currentIterator = hashTable.get(i).iterator();

                                    break;

                              }

                        }

                  }

                  return item;

            }

            public boolean hasNext() {

                  // if currentIterator is not null and currentIterator.hasNext()

                  // method returns true, then there are more element(s) to iterate

                  return currentIterator != null && currentIterator.hasNext();

            }

            @Override

            public void remove() {

            }

      }

      // Return an iterator for the hash table

      public Iterator<String> iterator() { // THIS METHOD NEEDS HELP

            return new HashIterator();

      }

      /**

      * 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<String> iterator(int index) {

            List<String> 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<String> 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);

                  }

            }

      }

}