foo

Question 4 (AB Exam) Class Version

This question concerns the design of a templated hash table class. In this problem the hash table class is used to store names. Assume that a class Name has been declared as shown below. class Name { public: Name(); // constructor Name(const apstring & s); // construct from string // accessor functions int length() const; // returns # characters in name char kthChar(int k) const; // returns k-th character of name char operator [](int k) const; // returns k-th character of name bool Equal(const Name & rhs) const; // check equality int HashValue() const; // return hash value of name private: // declarations here }; // commented prototypes // int Name::length() const; // postcondition: returns # characters in self // char Name::kthChar(int k) const; // postcondition: if 0 <= k < length(), returns k-th character // otherwise returns space // char Name::operator[](int k) const; // postcondition: if 0 <= k < length(), returns k-th character // otherwise returns space // bool Name::Equal(const Name & rhs) const; // postcondition: returns true if rhs == self, otherwise returns false // int Name::HashValue() const; // postcondition: returns a hash value for name bool operator == (const Name & lhs, const Name & rhs) // postcondition: returns true if lhs == rhs, otherwise returns false { return lhs.Equal(rhs); } A simple hash table class is used in this problem. Any type that supports comparisons using operator == and that has a member function HashValue can be used with the templated hash table class. Because the class Name has a member function HashValue and an overloaded operator == it can be used with the hash table class.

Part A

Write member function HashValue, whose header is given below. HashValue returns the hash value of a Name object. The hash value is computed as follows:

  1. Compute a number for each character in the Name object. The number is the value of the character (treat the character as an int) multiplied by the position in which the character occurs where the first character has position 1 and the last character has position length().

  2. The sum of the all the numbers is the hash value, return this value.

For example:

Number for each Value returned by
value of Name character HashValue()
Ken 75*1 + 101*2 + 110*3 607
Susan 83*1 + 117*2 + 115*3 + 97*4 + 110*5 1600
Mark 77*1 + 97*2 + 114*3 + 107*4 1041
Cary 67*1 + 97*2 + 114*3 + 121*4 1087
Don 68*1 + 111*2 + 110*3 620
Y 89*1 89

Complete the member function HashValue below the following header. In writing Hash you may call member functions of the class Name (Name::length, Name::kthChar, Name::operator[], Name::Equal) and the overloaded operator == . You will not receive full credit if your code relies on a particular implementation of Name. Assume that the precondition of member function HashValue is satisfied whenever it is called.

int Name::HashValue() const // preconditon: 0 < length() // postcondition: returns hash value

Answer

Part B

Assume that the hash table will be implemented using an apvector of linked lists. The list in the kth element of the vector will hold all names with hash value k that have been inserted into the hash table. If no inserted name has hash value k, then the kth element of the vector will be NULL/0. For example, if the size of the vector is 5, and the names Ken, Susan, Mark, Cary, Don, and Y have been inserted into the hash table, then the vector will be as shown below.

*

The declaration for templated class hashTable is shown below:

template <class Type> class HashTable { public: HashTable(int size); // size of hashtable bool Contains(const Type & key) const; // is key in hashtable? void Insert(const Type & key); // insert key into table // other member functions as needed private: // node for linked list struct Node { Type info; Node * next; Node(const Type & val, Node * link = 0) : info(val), next(link) { } }; apvector<Node *> myTable; // vector linked lists int mySize; // size of myTable };

Write member function Contains, whose header is given below. Contains should return true if the parameter key is in the hash table; otherwise it should return false. Contains should use the hash value of key to identify the list that might contain key; the index of the linked list in myTable is the remainder when key.HashValue() is divided by mySize. For example, if variable Table represents the hash table shown on the previous page (so that mySize has the value 5):

index of linked list Value returned by
value of key key.HashValue() in myList Table.Contains(key)
Susan 1600 0 true
Gail 1044 4 false
Chris 1612 2 false

In writing Contains you may call member functions of the class Name and the overloaded operator == for Name values. You will not receive full credit if your code relies on a particular implementation of Name. Assume that function Name::HashValue from part (a) works as specified, regardless of what you wrote in part (a).

Complete function Contains below the following header.

template <class Type> bool HashTable<Type>::Contains(const Type & key) const // postcondition: returns true if key is in hash table // otherwise returns false

Answer

Complete HashTable class


Owen L. Astrachan
Last modified: Wed May 14 10:57:38 EDT