QuestionQuestion

Problem 1
In this problem, you will implement a generic array-based hashtable data structure by writing code in the file ArrayHashTable.java. The hashtable will store key-value pairs. Before you start, review the Hashtable lectures to remind yourself of the important concepts, algorithms, and implementation details. You are allowed to use code you’ve written for previous assignments.
Requirements. For all two problems in this project, you may NOT use any Java class that implements the Collection interface (e.g. ArrayList, Vector etc.).
What to do. Complete the ArrayHashTable (defined in ArrayHashTable.java) by correctly implementing the 15 methods (including constructor) marked by //TODO. You need to implement the hashtable using an array.
However, you can define multiple non-public classes (or nested classes) in the same Java file, keeping in mind that such classes are not visible (public) to outside classes. The array must be expandable so that its size is unbounded.
Please carefully read the comments in ArrayHashTable.java to understand what each method does, what type of
Exception each method is expected to throw, and importantly, several operations that must be O(1) without collision.
For resolving collisions when a new key is put in the hashtable, we have provided the searchIndex and resolveCollision methods. searchIndex returns index of the key if it is exist in the table. If the new key is not exist in the table, you can call resolveCollision method to get next available index for the new key. These two methods depend upon correct implementation of other methods that you need to implement, namely: doLinearProbe, doQuadraticProbe, doDoubleHash, doLinearSearch, doQuadraticSearch, and doSecondHashSearch. Test these methods to make sure your implementations are correct before you continue to work on other methods.
To implement remove method we use lazy deletion, which need a boolean array as flags to indicate whether the key is gone. This boolean array should be initialized by False, and the flag will be set to True when a new key is put in the hashtable.
Why are there so few tests? When you take upper-level CS classes (get a job in the future), it’s unlikely that comprehensive and ready-made test suites will be given to you to start with. Instead, you’ll need to develop your own tests, including reasoning about what are the necessary test cases, what are the edge cases that must be covered etc.
Since you’ve already implemented several ADTs similar to a hashtable, we’re letting you write most of your own test suite for your Hash Table. It’s your responsibility to write your own tests for the other methods. If you are experienced with programming, you can eye-ball possible errors and bugs in your programs. But in general you must write some test cases to ensure your programs work correctly under all specified conditions. Note that writing test cases is not a required part of this assignment and is purely optional.

Problem 2
Besides the implementation of a hashtable, the overall goal of this project is to complete the implementation of a program that performs a simple text processing task that is commonly used in text analysis. In particular, the program extracts words from a text file and maintains counts of the individual words found in the provided text file. Each individual word is associated with the number of times it occurred in the text. Word counts are often referred to as word frequencies. For Problem 2, you will complete the code in WordFrequencyCounter.java, where you will use your HashTable to implement the algorithm for maintaining words and their frequencies of occurrance. The hashtable will store a unique word (a String) as a Key and its frequency (count) as an Integer Value.
For this problem, you will complete the code in src/wordfrequencycounter/WordFrequencyCounter.java, where you will use your HashTable to implement the algorithm.
What to do.
WordFrequencyCounter contains several methods that you must correctly implement. You need to initialize a new HashTable in the constructor for saving each word and its frequency. The addWord method takes in a word represented as a String. It adds the word to the hash table if the word is not already in the hash table. If the word exists in the hash table, it should increase the frequency of that word stored in the hashtable. The countWord method takes a word and returns the frequency of the word in the hash table.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

package structures;

// this class demonstrates using an object's hash code to calculate the
// index into the array

public class ArrayHashTable<K, V> implements HashTable<K, V> {

protected static final int defaultCapacity = 10;
protected static final double defaultLoadFactor = 0.7;
protected static final String defaultCollisionHandler = "linear";

protected K[] keyTable;
protected V[] valueTable;
protected int capacity;
protected boolean[] flag;
protected String collisionHandler;
protected double loadFactorLimit;
protected int count;

/**
   * Default Constructor.
   */
public ArrayHashTable() {
    this(defaultCapacity, defaultLoadFactor, defaultCollisionHandler);
}

/**
   * Default Constructor.
   */
public ArrayHashTable(String collisionHandler) {
      this(defaultCapacity, defaultLoadFactor, collisionHandler);
}

/**
   * Default Constructor.
   */
public ArrayHashTable(int capacity, String collisionHandler){
      this(capacity, defaultLoadFactor, collisionHandler);
}


/**
   * Constructor.
   */
public ArrayHashTable(int capacity, double loadFactor, String collisionHandler){
    // TODO 1: complete the constructors
this.capacity = capacity;
this.loadFactorLimit = loadFactor;
this.collisionHandler = collisionHandler;

      keyTable = (K[]) new Object[capacity];
      valueTable = (V[]) new Object[capacity];
      flag = new boolean[capacity];
}

/**
* This method ensures that the inputNum maps to
* a return value that is in the current array.
*/
private int getBoundedHash(int inputNum) {
    return Math.abs(inputNum) % this.capacity;
}

private int getHash(K key) {
    int index = getBoundedHash(key.hashCode());
    return index;
}

public K[] getKeyTable() {
    return this.keyTable;
}

public V[] getValueTable() {
    return this.valueTable;
}

public boolean[] getFlag() {
    return this.flag...
$50.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats