foo
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:
- 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().
- 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 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 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
bool HashTable::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