Lab #7 Hash Tables Solution



### Guidelines

This is an individual lab assignment. You must do the vast majority of the work on your own. It is permissible to consult with classmates to ask general questions about the assignment, to help discover and fix specific bugs, and to talk about high level approaches in general terms. It is not permissible to give or receive answers or solution details from fellow students.

You may research online for additional resources; however, you may not use code that was written specifically *to* solve the problem you have been given, and you may not have anyone else help you write the code or solve the problem. You may use code snippets found online, providing that they are appropriately and clearly cited, within your submitted code.

*By submitting this assignment, you agree that you have followed the above guidelines regarding collaboration and research.*

The goal of Lab 7 is to implement a hash table for retrieving passwords. You must use open addressing for collision resolution.

#### (Parts A must be completed in lab)

## Part A: Hash Table

For Part A you are going to implement a Hash class that will store a key string (username) and value string (password) and uses open addressing for collision resolution. Open addressing sacrifices insertion and lookup performance to save memory by placing the data in the next open space when there is a collision:

Hash Class

* class Hash

* Public Methods

* Hash(unsigned int size)

* Should initialize an array to some static size. You can use a vector for this, but it should still have a static size (meaning you will need to initialize the vector to some start size).

* bool insert(string key, string value)

* returns false is the hash is full

* bool remove(string key)

* removes the entry from the hash

* returns false if the key was not found

* string find(string key)

* returns the correct value based on the key parameter

* If the key is not found, returns an empty string

* bool empty()

* returns true of the hash is empty

* int size()

* returns to max size of the hash (not the current number of items)

* void printHash()

* prints out the index, key, and value of each element in the hash

* int hasher(string key)

* hash function that determines an index based on the key parameter

* You can develop whatever hash function you want, but should try to limit collisions

__Show your TA your code.__


_You may continue to work on the remainder of the lab on your own time or in lab_

## Part B: Password retrieval

Your hash should correctly store and retrieve passwords along with the key. Some rules your hash must follow are:

1. You must use open addressing for collision resolution

2. You may use a vector as your internal collection, and a pair as your storage object, but you may not use any other STL collections.

3. Your hash table must not change size. Empty ‘slots’ are represented with empty strings.

## Part C: Code Organization and Submission

* Required code organization:

* lab7.cpp (driver code – You must include this file in your submission)

* password.txt – (sample text file – You must include this file in your submission)

* Hash.h/.cpp

* makefile

* executable should be called: lab7

* You should have all the same labels in your makefile from the previous lab with minor updates

Below is just a reminder of the commands you should use to submit your code. If you cannot remember the exact process, please review lab 1.

*These commands all presume that your current working directory is within the directory tracked by `git`.*


git add Deck.h

git add Card.cpp

git commit -a -m “first commit”

git push


Lastly we are going to make our final commit. You will need to do this when your submission is ready for grading.


git commit –allow-empty -m “final commit”

git push


:warning: Remember, you __MUST__ make a submission with the comment “final commit” before the deadline to be considered on time.