P1W2.Hash Table

Due Wednesday by 11:59pm

Points 40

Submitting an external tool

Available Jan 31 at 5pm - Feb 9 at 11:59pm

Project Specific Data Structure

Each of our three course projects are designed around different central data structures. Project 1 (P1) is designed around the use of a Hashtable. The work for these projects is generally organized across four weeks as follows:

W1: Groups of 8 students propose a project and design the architecture for that project as a group

W2: Everyone individually implements the central data structure that will be used by the project (same for all cs400 students)

W3: Each team member has a unique role with specific code responsibilities that are developed during this week

W4: The code developed by each team member is integrated together and reviewed by one another, with some extra testing and bug fixing.

For this first project, everyone will be building the same project designed by our course staff, so there is no P1W1. Instead, we'll share the details of this proposal as they become relevant over the next few weeks. Another difference between P1 and later projects is that this first project will be completed individually, rather than in teams. The code that your teammates would typically contribute toward this first project (if you had teammates) will instead be provided to you by the course staff. We hope this adds clarity to everyone's understanding and expectations around an approach and organization for future group projects in this course.

Project Pitch and Description

The first step in the W1. Proposal for future projects will be for everyone to brainstorm, and share pitches for different kinds of projects that you might design and build as a group, and to be clear about how these pitches fulfill any project requirements. The main requirement for this first project is to create an application that appropriately makes uses of a Hashtable implementation of this MapADT interface. After discussing and voting on the best of these options, your group will work together to write and refine a project Title, Description, and List of Four Representative Tasks that can be performed by the users of the proposed application. Here's an example of those elements for the P1 that you will be building.

Title: CHSearch

Description: This application enables its users to quickly search the /r/EatCheapAndHealthy forum Links to an external site.for posts that include specific keywords. This tool makes use of a hashtable to quickly retrieve groups of posts that include specific keywords in their title or body. This application can be used without being connected to the internet, as it retrieves post data from a local text file.

Four Representative Tasks:

Search for some of the cheapest food items by finding posts that contain the word "cents".

Search for discussions of foods without dairy by finding posts with either the word "dairy-free" or "non-dairy".

Find out which sugar alternative is discussed in more posts in this : "stevia" or "aspartame".

Search for posts related to your local area by finding posts that include any of the following words: "Wisconsin" "WI" "Madison" "Midwest"

P1W2: Hashtable

The rest of this write-up is specific to the Week2 work that you must complete for P1 this week: developing a hashtable implementation of the MapADT interface that your proposal is designed to make effective use of.

Work Individually

The data structure that you will individually implement for project 1 is a Hashtable. You must develop the code for this assignment entirely on your own. If you encounter difficulties while working, you are encouraged to discuss general algorithms and debugging strategies with anyone you would like. But you are NOT ALLOWED to view any Hashtable implementations of others, and you are NOT ALLOWED to show or allow access to your implementation to anyone outside of the CS400 course staff.

HashtableMap Specifications

You must define a public class HashtableMap that implements this provided MapADT. Your implementation must:

be left in the default package: ie. do not define it within a named package.

be defined with two generic type parameters in this order: which allow it to be used with different key and value type pairings.

include two constructors with the following signatures:

public HashtableMap(int capacity) public HashtableMap() // with default capacity = 8 

implement open addressing with a simple linear probe to handle hash collisions. It's likely to be helpful to create a helper class of your own to group together key-value pairs within a single object, so that you store these pairs within your hashtable's array.

use exactly one protected single-dimensional array instance field. You can have additional fields of other types, but only one array.

Note: You cannot instantiate an array with an associated generic type in Java. So you should instantiate the array for your hashtable using the raw type (without any generic specifications) and then cast to the complete type (including generics) before storing this reference in a protected instance field. Doing this produces an unchecked cast warning in Java that can either be ignored, or suppressed by adding the @SuppressWarnings("unchecked") annotation in front of the line of code with the cast.

use open addressing with a simple linear probe to handle hash collisions. It's likely to be helpful to create a helper class of your own to group together key-value pairs within a single object, so that you can store these pairs within your hashtable's array. It may also be helpful to create one of these objects to use as a sentinel value to store in locations that old key-value pairs have been removed from.

store new values in your hash table at the index corresponding to { the absolute value of the key's hashCode() } modulus the HashtableMap's current capacity. When the put method is passed a key that is null or is equal to a key that is already stored in your hash table, it should throw an IllegalArgumentException without making any changes to the hashtable.

dynamically grow your hashtable by doubling its capacity and rehashing, whenever its load factor becomes greater than or equal to 70%. Define private helper methods to better organize the code that does this. Note that you can and should get rid of any markers indicating locations that key-value pairs have been removed from when growing this array.

include a remove method that returns a reference to the value associated with the key that is being removed, and maintains the hashtable so that all other key-value pairs stored there can continue to be found.

throw exceptions as indicated within the comments of the MapADT interface. You will make use of both java.lang.IllegalArgumentException and java.util.NoSuchElementException for this. Note that when checking keys for equality, you should check whether their content is the same using the .equals() method, rather than requiring the more strict == equality.

NOT make use of any classes from libraries. The only class from java.util that you can use is the NoSuchElementException class mentioned above.

HashtableMapTests Requirements

In addition to your HashtableMap.java implementation, you must develop and submit tests in a source file named HashtableMapTests.java. These tests must include at least five distinct methods with the following names and signatures. Each should return true when the HashtableMap class that they are run with behaves correctly, and false when any unexpected (or buggy) behavior is detected. Each test should be designed to test a different feature of your HashtableMap implementation. These test methods should NOT throw exceptions, since any expected exceptions should be caught to verify correct expected behavior, and any unexpected exceptions should be caught and reported as faulty behavior (by returning false). These tests should be independent from one another, and should work equally well when run in any order. Be sure to provide descriptive comments for each of these test methods, which describe the high-level functionality that they are designed to check for. Note that these test methods should NOT be JUnit5 tests for this assignment since that is a tool that we'll be covering in a future week.

public static boolean test1() { /* test code here */ } public static boolean test2() { /* test code here */ } public static boolean test3() { /* test code here */ } public static boolean test4() { /* test code here */ } public static boolean test5() { /* test code here */ }

import java.util.NoSuchElementException; /** * This abstract data type represents a collection that maps keys to values, * in which duplicate keys are not allowed (each key maps to exactly one value). */ public interface MapADT { // add a new key-value pair/mapping to this collection // throws exception when key is null or duplicate of one already stored public void put(KeyType key, ValueType value) throws IllegalArgumentException; // check whether a key maps to a value within this collection public boolean containsKey(KeyType key); // retrieve the specific value that a key maps to // throws exception when key is not stored in this collection public ValueType get(KeyType key) throws NoSuchElementException; // remove the mapping for a given key from this collection // throws exception when key is not stored in this collection public ValueType remove(KeyType key) throws NoSuchElementException; // remove all key-value pairs from this collection public void clear(); // retrieve the number of keys stored within this collection public int getSize(); // retrieve this collection's capacity (size of its underlying array) public int getCapacity(); }