Description
In this assignment, you will implement a system for maintaining user account login information. The record system will use a (non-template) hash table class to store a set of UserAccounts. Collisions will be dealt with using separate chaining, and will be implemented as an array of templated singly-linked lists. You may find it helpful to refer to the postfix example already posted on the course website if you are not already familiar with linked list implementation by now. Hash Table Class Implement a hash table class called HashTable to store UserAccount objects. The items will be inserted based on a hash function applied to a string attribute. Your Insert, Search, Retrieve, and Remove methods must handle the situation where different items map to the same hash value (i.e. collision), and this should be handled structurally by inserting/finding/removing the value in the linked list at the given index. Please see the provided hashtable.h header file for the functional requirements of the HashTable class. You may add private member functions to hashtableprivate.h. Hash Function Insertions should be mapped to array indices using this hash function: ℎ𝑎𝑠ℎ_𝑣𝑎𝑙𝑢𝑒 modulo 𝑎𝑟𝑟𝑎𝑦_𝑠𝑖𝑧𝑒. To achieve this, your functions must first generate a hash value from a given string. This hash value should be calculated by assigning the values 1 to 26 to the letters ‘a’ to ‘z’ (regardless of letter case) and concatenating the binary values for each letter. The formula given below results in this value: 𝑐ℎ0 ∗ 32𝑛−1 + 𝑐ℎ1 ∗ 32𝑛−2 + ⋯ + 𝑐ℎ𝑛−2 ∗ 321 + 𝑐ℎ𝑛−1 ∗ 320 where ch0 is the left-most character of the string and n is the size of the string. For example, the string “cat” has this value: 3 ∗ 322 + 1 ∗ 32 + 20 = 3124 Note that using the result of this calculation on large strings will cause overflow. You should therefore use Horner’s method as shown in class to perform the calculation, and apply the modulo operator after computing each expression in Horner’s method. To find the “value” of a lower case character in position i in a string str, you can do this: int asc = str[i] – 96; // ASCII a = 97 For the purposes of this assignment, you can assume that all strings will be lower case and will not contain any special characters, numerals, punctuation, or whitespace. i.e. your strings will consist of only the lower case characters ‘a’ to ‘z’. The test driver which the TA uses for grading your submission will also only test using these lower case characters. Geoffrey Tien CMPT 225 – Assignment 5 2 Linked List Class Your hash table should deal with collisions using separate chaining implemented as an array of singlylinked lists. This means you must also implement a singly-linked list class (called SLinkedList). The linked lists’ public methods are driven by the public methods of the HashTable class. You may refer to the postfix sample code posted to the course website earlier in the semester as a starting point for this class. Please refer to the provided slinkedlist.h header file for details about the linked list functional requirements. Collisions Dealing with collisions using separate chaining is straightforward since they are handled by the structure of the hash table (which is more complex than a hash table that implements open addressing since in this case it consists of an array of singly-linked lists). It is important to determine which class is responsible for each part of the process of inserting, finding, or removing values. As an example, when inserting a string into the hash table, these steps should be performed: 1. Calculate which index the string maps to, by running the (private) hash function on the string 2. Determine whether or not the string has already been stored in the linked list at the hashed index 3. Either insert the string and return true, or return false without inserting the string It is the responsibility of the HashTable class to compute the hash index (step 1). Steps 2 and 3 require in-depth knowledge of the contents of a singly-linked list and are therefore the responsibility of the SLinkedList class and should thus be handled by SLinkedList methods. The hash table’s Insert method can therefore call the Contains and Insert method of the linked list at the appropriate index to perform the insertion and determine the result. Vectors A vector is a STL (Standard Template Library) template class that can be found in the header file. Below, you will find pretty much everything you need to know about vectors for the purposes of this assignment. Declaring a Vector Since vectors are a template class, then when a vector is declared, the type to be stored in it should be specified vector v; // creates a new vector of strings called v Geoffrey Tien CMPT 225 – Assignment 5 3 Accessing Vector Elements Individual elements of a vector can be accessed using indices like an array, or by using the vector’s at method. string s1 = v[2]; // assigns the third element of v to s1 string s2 = v.at(3); // assigns the fourth element of v to s2 Inserting Values in a Vector There are numerous methods for inserting values in a vector. The simplest way is to insert a value at the end of a vector by calling its push_back method. Note that vectors increase size automatically as necessary. v.push_back(“ape”); // inserts the string ape at the end of v Warning: inserting a value into a given position in a vector using its insert method is less efficient than using push_back. Finding the Size of a Vector The number of items stored in a vector can be found using its size method. for (int i = 0; i < v.size(); i++) { … } // iterates through the // contents of v Copying a Vector into Another Vector The insert method can be used to insert the entire contents of a vector at the end of another vector. In the example given below, the contents of v2 are inserted at the end of v1. v1.insert(v1.end(), v2.begin(), v2.end()); Testing your SLinkedList and HashTable classes Before you submit your assignment you should compile and run it with the a5simpledriver.cpp file from the course website. If you are unable to compile and run this program it is very likely that we will not be able to compile and run your submission and may not mark your assignment. The test function is not in any way intended to be a comprehensive test of your class so successfully running the program straight from the website without modification does not mean that you will get full marks for the assignment. It is recommended to add your own code to specifically test SLinkedList and HashTable objects in detail. Geoffrey Tien CMPT 225 – Assignment 5 4 Deliverables Submit a ZIP file to CourSys, with the following contents: Title page with names and student information of contributing group members slinkedlist.cpp hashtableprivate.h hashtable.cpp If you are unable to complete any of the methods, make sure that any calls to that method will still compile and run by writing a stub for that method that returns a default value of the appropriate type.
