Assignment 2: HashMap

Assignment Timeline

The starter code passes 7 of the 14 required test cases. To pass the assignment, your job is to get the remaining 7 test cases (4 in milestone 2, and 3 in milestone 3) to pass, and to reasonably answer all 10 short answer questions.

To help you stay on track for this assignment, we will require you to submit a checkpoint approximately one week before the deadline. For the checkpoint, please have Milestones 0 and 2 finished.

Only Milestones 0, 2, 3, and 4 are required, but we are happy to support you in the other milestones:

Tips for the Assignment

• Milestone 0 requires knowledge of linked lists, which CS 106B covers in week 7. You should have plenty of time to complete the assignment due in week 9.
• The starter code comments are thorough, more so than this handout. Read them!
• The handout may seem vague as in describing what you are supposed to do. We don't provide even the function prototypes. This is intentional. Designing the class definition itself is a valuable learning activity, and we don't want to constrain you to one particular design. You need to consider how a client might use your HashMap, and the test harness will try every reasonable way of using your class. Ask us if you are ever unsure about how to proceed.

Starter Code

Please download the starter code here. The starter code contains the following files:

• hashmap.h: This file contains the function prototypes for the minimal HashMap, and also contains very thorough comments about each function. The prototype for rehash() is provided here, but you will need to add your function prototypes for any function that you write for milestone 2 and 3.
• hashmap.cpp: This file contains the implementation of the HashMap, and also contains very thorough comments about implementation details. The skeleton for rehash() is provided here, and you will need to declare your own functions for milestones 2 and 3..
• student_main.cpp: When the test harness is turned off (see below), the student_main() function in this file will be run. You can treat this as if you were writing your own main function to test your program.
• test_settings.cpp: This file contains macros which lets you on the test harness. If you turn on the test harness (#define RUN_TEST_HARNESS 1), test cases will be run. If it is turned off (#define RUN_TEST_HARNESS 0), the student_main function will be run. This is analogous to using NO_TESTS vs. ALL_TESTS in CS 106B's SimpleTest.
  The file also lets you turn on or off individual test cases. Test cases that are turned on will result in a PASS or FAIL when run. Test cases turned off always result in a SKIP (which is effectively a FAIL). The reason you will turn off test cases is that the test cases for milestones 2 and 3 may call functions that you have not declared or implemented, so turning them on will generate compiler errors. Only turn on a test case after you have implemented that function, as explained in the test_settings.cpp file. You may get compiler errors as well if your function prototype is incorrect (likely because of const correctness, or parameter/return value type issues).
• tests.cpp: This file contains the code for each test case. You are welcome to look at this, add some map.debug() statements, or even add your own test cases. We will test your code on an unaltered version of this file, so be careful about changing this file.

Milestone 0: Background Reading and Examine Starter Code

You will implement the equivalent of the Stanford HashMap, using a hash table that resolves collisions using external separate chaining. Luckily for us, CS 106B covers hashing and external hash tables with chaining! Before reading further, familiarize yourself with hashing by reading the resources below (if you're in CS 106B or recently took it, feel free to skip the CS 106B resources).

The Map Interface

• Stanford documentation of HashMap.
• STL documentation of std::map and std::unordered_map (based on a hash-table).
• CS 106B (Fall 2020) notes on Maps.

Hashing

Note: some authors insert a node to the end of a bucket's linked list. We will always insert into the front, since order doesn't matter and inserting to the front is faster and easier.

• A YouTube Video
• CS 106B lecture on hashing (Spring 2020) - remember that in a map, we are storing pairs of keys and values.
• OR CS 106B lecture on hashing (Fall 2020) - released on Friday.
• Avery's recorded session on hashing (optional if you're feeling a little shaky on hashing after reading above resources)

Reading the Starter Code Documentation

We could have asked you to implement a HashMap yourself given you knowledge from CS 106B. However, since practicing linked list algorithms is not the main goal of CS106L, we've given you the starter code.

Read through the starter code's interface (.h) and template implementation (.cpp) files to understand what has already been implemented. This handout you are reading is fairly sparse, and the reason is that there is a lot of documentation provided in the starter code. You should be able to identify the standard map interface (constructor, insert(), at(), contains(), etc.) as well as the hash table implementation (_bucket_arrays, node*'s, etc.).

You can call map.debug() inside the test cases to see a visual representation of the map printed to the console. You can call this function in your student_main function without the test harness, or inside the test cases. This will be useful when you begin milestone 1.

There's nothing you need to turn in after completing this milestone, but please do make sure that you're comfortable with the above content before moving on.

Optional Milestone 1: Implement rehash()

This milestone is optional. It's a challenging linked list problem that will be great practice for CS 106B assignments and exams.

Implement the public member function rehash(), whose expected behavior is documented in the .h file. Your implementation of rehash() must not allocate or leak memory; instead, it should reuse existing nodes.

The purpose of this milestone is to get you familiarized with the starter code and with working in a template class. It should also serve as a good review of the linked lists algorithms you learned in CS 106B. Our solution is 11 lines of code long. If you are unsure about the hash functions, we recommend looking at the implementations of insert() and erase().

Once you are done, turn on the two tests for Milestone 1:

• Test 1A checks the external correctness of the rehash function, by verifying that your HashMap is still functional even if we rehash to various bucket sizes, including extremely large or small values. We also interweave the calls to rehash() with calls to erase() and insert(). Finally, there is a check to see if you correctly throw an exception when rehash(0) is called (this was done for you in the very first line of rehash()).

• Test 1B roughly checks the internal correctness of the rehash() function. The idea is that buckets with longer linked lists should take longer to search, so we time various calls to contains() to verify that the sizes of the linked lists are roughly correct. This test is fairly rough as it depends on the speed of your computer, but we give it a large enough leeway that you should be able to pass the test. It is fine if this test fails with a small probability.

Milestone 2: Operator Overloading and Const-Correctness

In this section, you will first implement four operators, then make your HashMap const-correct. After implementing an operator, turn on that operator's tests. There is one test for each category of operator, and one for const-correctness.

Indexing ([])

The index operator accepts a key, and returns a reference to its mapped value. The index operator should support auto-insertion—if a key is not found, then a new key/mapped pair is inserted with the given key and a default value of the mapped type.

Stream Insertion (<<)

The stream insertion operator writes the contents of a HashMap into an output stream. The format resembles the format used by the Stanford HashMap, as seen below:

HashMap<string, int> map;
cout << map << endl;		// prints "{}"
map.insert({"Anna", 2});
cout << map << endl;		// prints "{Anna:2}"
map.insert({"Avery", 3});
cout << map << endl;		// prints either "{Avery:3, Anna:2}" 
                            // or "{Anna:2, Avery:3}"

The stream insertion operator will need to support chaining.

Equality (==) and Inequality (!=)

Two HashMaps are considered equal if they have the exact same key/mapped pairs. The internal order that they are stored, or the number of buckets, does not matter.

Const Correctness

Finally, make your HashMap class const-correct. You will need to decide which functions (including those part of the starter code) and operators need to be modified.

Hint

For some parts of this milestone, you may find yourself having to add a friend in hashmap.h. This friend may be a template function, and since it's not a member function of the HashMap, we would need to explicitly write out the template declaration for this function in hashmap.h. Note that we can't reuse the same K, M, and H in this template declaration because these template parameters are already in use in the class declaration. Instead, we can use names other than K, M, and H for our function's template declaration.

Milestone 3: Implement Special Member Functions

Any good STL-compliant class must have correct special member functions.. Recall that there are six major special member functions:

• Default constructor (implemented for you)
• Destructor (implemented for you)
• Copy constructor
• Copy assignment operator
• Move constructor
• Move assignment operator

The first two are implemented for you; your job is to implement the last four. Specifically, the copy operations should create an identical copy of the provided HashMap, while the move operations should move the contents of the provided HashMap to this. Avoid memory leaks and perform your copy/move as efficiently and safely as possible.

Test 3A creates copies of your HashMap using the copy constructor and copy assignment operator, and verifies their correctness. In addition, there are tests for edge cases such as self-assignment. Test 3B tries to move HashMaps from one to another using the move constructor and move assignment, and verifies correctness just like test 3A. Note that Test 3B passes even if you only implemented the copy operations (recall that if no move operations are declared, the compiler defaults to the copy operations). Test 3C times your move operations to verify that you are actually moving the contents of the HashMaps rather than copying the contents.

The tests use some compiler directives (#pragma) to silence compiler warnings about self-assignment. You can safely ignore those.

Milestone 4: Answer Short Answer Questions

Answer the following questions in the file named "short_answers.txt". These questions do not require long answers or even complete sentences. We will grade for reasonable correctness and effort—see an example below:

Example

Consider the test case B_move_ctor_assignment. You should see a line with std::move(map1). Then, in the next line, we move from map1 to create move_constructed. Why is this valid?

Answer: std::move marks map eligible to be moved, but does not actually move. A function taking an r-value (eg. move constructor) does the moving. map1 is not passed to such a function, so we can still move from map1.

1. Templates and Template Classes

2. Operator Overloading and Const Correctness

3. Special Member Functions and Move Semantics

4. RAII