CMPSCI 187 / Fall 2018
HashTable
Mark Corner and Joe Chiu
1
CMPSCI 187 / Fall 2018 HashTable
Contents
Overview 3
Learning Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
General Information [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Import Project into Eclipse [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Problem 1 4
Problem 2 5
Export and Submit [Common] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Page 2 of 5
CMPSCI 187 / Fall 2018 HashTable
Overview
In this project, you’ll exercise your understanding of how a hashtable functions to store key-value pairs. You’ll
implement a hashtable with different probing methodologies to resolve collisions. You will use your hashtable implementation to count word frequencies in a text file, a common task in text analysis.
Learning Goals
• Implement a Hashtable interface using generic types for Keys and Values.
• Gain experience coding the main functions of an array-based hashtable.
• Gain experience coding several collision resolution schemes.
• Demonstrate an understanding of how a hashtable can be used to count word frequencies.
• Practice writing unit tests to ensure a program works correctly.
General Information [Common]
Reminder: Copying partial or whole solutions, obtained from other students or elsewhere, is academic dishonesty.
Do not share your code with your classmates, and do not use your classmates’ code. If you are confused about what
constitutes academic dishonesty you should re-read the course policies. We assume you have read the course policies
in detail and by submitting this project you have provided your virtual signature in agreement with these policies.
• For some projects, it may be useful for you to write additional java files. Any java file you write MUST be
placed in the provided src directory of your Eclipse project.
• When submitting your project, be sure to remove all compilation errors. Any compilation errors will cause
the autograder to fail to run, and consequently you will receive a zero for your submission. No Exceptions!
In the test directory, we provide several JUnit tests that we refer to as the public tests. We recommend you run the
tests often and use them as starting points to test your project. In addition, some of the java files come with their own
main functions. You can run them as Java applications to interact with the project.
Be aware that the autograder will use a more comprehensive set of tests (referred to as private tests) to grade your
project. These tests are hidden from you. We recommend that you think about possible test cases and add new @Test
cases to your public test files as part of your programming discipline. In particular, you should consider:
• Do your methods handle edge cases such as integer arguments that may be positive, negative, or zero. Many
methods only accept arguments that are in a particular range.
• Does your code handle cases such as when an array or list is empty, or has reached full capacity?
More complex tests will be project-specific. To build good test cases, think about ways to exercise methods. Work out
the correct result for a call of a method with a given set of parameters by hand, then add it as a test case.
Import Project into Eclipse [Common]
Begin by downloading the starter project and importing it into your workspace. It is very important that you do not
rename this project as its name is used during the autograding process. If the project is renamed, your assignment will
not be graded, and you will receive a zero.
The imported project may have some compilation errors, but these should not prevent you from getting started. Specifically, we may provide JUnit tests for classes that do not yet exist in your code. You can still run the other JUnit tests.
After completing your code, the compilation errors should be gone.
The project should normally contain the following root items:
Page 3 of 5
CMPSCI 187 / Fall 2018 HashTable
src This is the source folder where all code you are submitting must go. You can change anything you want in this
folder (unless otherwise specified), you can add new files, etc.
support This folder contains support code that we encourage you to use (and must be used to pass certain tests). You
must not change or add anything in this folder. To help ensure that, we suggest that you set the support folder
to be read-only. You can do this by right-clicking on it in the package explorer, choosing Properties from the
menu, choosing Resource from the list on the left of the pop-up Properties window, unchecking the Permissions
check-box for Owner-Write, and clicking the OK button. A dialog box will show with the title “Confirm recursive
changes”, and you should click on the “Yes” button.
test The test folder where all of the public unit tests are available. You can feel free to add your own tests here.
JUnit 4 A library that is used to run the test programs.
JRE System Library This is what allows Java to run; it is the location of the Java System Libraries.
If you are missing any of the above or if errors are present in the project (other than as specifically described below),
seek help immediately so you can get started on the project right away.
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.). The list of these classes is included in the API documentation available at:
http://docs.oracle.com/javase/8/docs/api/java/util/Collection.html. Notable, do not
submit code where you import or use any class from java.util package. Doing so will result in a gdrade of 0.
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
Problem 1 continued on next page. . . Page 4 of 5
CMPSCI 187 / Fall 2018 HashTable Problem 1 (continued)
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. Any test cases you write are for your own benefit
and will not be counted as part of your project grade.
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.
Export and Submit [Common]
When you have completed this project, you should export an archive file containing the entire Java project. To do this,
click on the hashTable-student project in the package explorer. Then choose “File → Export” from the menu.
In the window that appears, under “General” choose “Archive File”. Then choose “Next” and enter a destination for the
output file. Be sure that the project is named hashTable-student (otherwise you may be exporting the wrong
project!). Save the exported file with the zip extension.
Once you have the zip file ready, you can submit it to the online autograder (Gradescope). Please see the course
website and/or documentation explaining how to use the online autograder. If you have any questions please be
prompt in asking the course staff before it is too late to submit your solution. If you encounter any errors that look like
the autograder failed and not your project, please let the instructors know.