Question

The goals of this assignment are to:

* Help you understand how to implement a linked-list based hashtable.
* To understand the importance of a hash function.
* Have you work with true hash tables including a hash table of hash tables, which is very common in industry code.
* Give you further practice in working with an assignment in which multiple classes all interact with each other.

For this assignment, you will complete functionality for two classes: modifiedLinkedList and hashTable. The main purpose of the hashTable class is to provide a linked list driven hash table to store many key value pairs for fast insertion and retrieval. Each linked list referenced by the hash table is an instance of the modifiedLinkedList class.

The definition of the hashTable class is as follows:

template <typename T, typename U>
class hashTable {
public:

    hashTable() {/* some constructor code */}
    hashTable(unsigned int(*hashFunction)(const void *));
    hashTable(const hashTable& obj);
    ~hashTable();
    hashTable& operator=( hashTable tmp );

    void add(const T& key, const U& value);
    bool exists(const T& key) const;
    void remove(const T& key);
    U item(const T& key);
    U& operator[](const T& key);

    //friended so the checkTest function can have access to private data members of this class.
    friend void testSimpleIntHash();
    friend void testHashOfObjects();

protected:
    modifiedLinkedList<T, U> *linkedListArray; //The array of linked lists
    unsigned int hash(const T& key) const;
private:
    int getWorstBucket() const;
    int getTotalCount() const;
    unsigned int(*hashFunction)(const void*);
    static const int NUMBER_OF_LINKED_LISTS = 1000;
};

The following methods of hashTable have been completed for you:
• The default constructor
• The copy constructor
• The assignment = operator
• The destructor
• The two private data methods (getWorstBucket()and getTotalCount())
• The two friend functions which are used for testing purposes

You need to complete the following (all these items can be implemented using very few lines of code):

• Within the one-arg hashTable constructor, an array of 1000 linked lists will be created and assigned to the linkedListArray member variable.
• The add() method will add a key/value pair to the hash table.
• The exists() method will return true if the key is found in the hash table; false otherwise.
• The item() method will return the item’s information by reference from the hash table, if the key was found.
• The remove() method will remove an item from the hash table, if the key was found.
• The overloaded operator[] method will allow the use of string indexes, not just integer indexes, when accessing objects.

The following methods should also be implemented:

hashFunctionInt() to turn an int key into a number between 0 and 999 (inclusive)
hashFunctionString() to turn a string key into a number between 0 and 999 (inclusive)

The following methods in the doubly linked list class modifiedLinkedList should also be completed. These methods can be leveraged by the hashTable functions to add an item, search for an item, check for the existence of an item, and remove an item. The nodeType class used to assemble the modifiedLinkedList declares members suitable for storing key/value pairs in a doubly linked list.

• The insertLast() method should add a node to the end of the list.
• The nodeWithKeyExists() method determines if the list has a node with a matching key. If so, return true; otherwise, return false.
• The searchForKey() method determines if the list has a node with a matching key. If so, return a reference to the info; otherwise, throw an Error object.
• The deleteNodeWithKey() determines if the list has a node with a matching key. If so, this node is deleted.

For this assignment, assume only one unique key is allowed per item stored in the hashTable. Don’t worry about duplicate key conditions – in this situation, the most recent item will simply overwrite the current item.

The functionality of your code will be examined using the testing statements included in the supplied starter file.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

#include <iostream>
#include <string>
#include <sstream>
#include <ctime>
#include <cstdlib>
#include <map>

#include "hashTable.h"

using std::cout;
using std::endl;
using std::string;
using std::stringstream;


//--------------------------------------------
//A quick and dirty class that simulates a product object.
//--------------------------------------------
class product {
public:
    void setCost(int cost);
    void setName(const string&);
    string getName();
    int getCost();
    string getAllInfo();
private:
    string name;
    int cost;
};
void product::setCost(int cost) {
    this->cost = cost;
}
void product::setName(const string& name) {
    this->name = name;
}

string product::getName() {
    return name;
}

int product::getCost() {
    return cost;
}

string product::getAllInfo() {
    stringstream ss;
    ss << "Name: " << name << ", Cost: " << cost << endl;
    return ss.str();
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Assisting Tutor

Related Homework Solutions

Arrays and Vectors in C++
Homework Solution
$13.00
Computer Science
C++ Programming
Arrays
Vectors
Animals
Data Storage
Names
Items
Lists
Statements
Variables
C Programming Exercises
Homework Solution
$28.00
Computer Science
C Programming
Arrays
Integers
Functions
Products
Values
Input
Output
Boxes
Stars
Symbols
Statements
Variables
Minesweeper Game in C
Homework Solution
$60.00
Computer Science
C Programming
Minesweeper Game
Fields
Mines
Objects
Numbers
Players
Moves
Board
Rows
Columns
Global Variables
Messages
C++ Programming Problems
Homework Solution
$35.00
Computer Science
C++ Programming
Classes
Bank Accounts
Customers
Accessor
Mutator
Balance
Tax
Methods
C Programming Problems
Homework Solution
$78.00
Computer Science
C Programming
Arrays
Functions
Null Characters
Strings
Mean Values
Median Values
Elements
Intersection
Union
Get help from a qualified tutor
Live Chats