Hashing

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date April 8, 2019 * @assg Assignment 13 * * @description Template class for definining a dictionary * that uses a hash table of KeyValuePair items. * Based on Shaffer hashdict implementation pg. 340 */ #include <cassert> #include <iostream> #include "KeyValuePair.hpp" using namespace std; #ifndef HASHDICTIONARY_HPP #define HASHDICTIONARY_HPP /** HashDictionary * An implementation of a dictionary that uses a hash table to insert, search * and delete a set of KeyValuePair items. In the assignment, we will be * implementing a closed hashing table with quadratic probing. The hash function * will implement a version of the mid-square hasing function described in * our Shaffer textbook. * * @value hashTable An array of KeyValuePair items, the hash table this class/container * is managing. * @value tableSize The actual size of the hashTable array * @value valueCount The number of KeyValuePair items that are currently being * managed and are contained in the hashTable * @value EMPTYKEY A special user-supplied key that can be used to indicate empty * slots. Since how we determine what is a valid/invalid key will depend on the * key type, the user must supply this special flag/value when setting up the * hash dictionary. */ template <class Key, class Value> class HashDictionary { protected: KeyValuePair<Key, Value>* hashTable; // the hash table int tableSize; // the size of the hash table, e.g. symbol M from textbook int valueCount; // the count of the number of value items currently in table Key EMPTYKEY; // a special user-supplied key that can be used to indicate empty slots public: // constructors and destructors HashDictionary(int tableSize, Key emptyKey); ~HashDictionary(); // accessor methods int size() const; // searching and insertion // all 4 of the methods you were required to create for this // assignment should have appropriate class method signatures // defined here. // overload operators (mostly for testing) KeyValuePair<Key, Value>& operator[](int index); template <typename K, typename V> friend ostream& operator<<(ostream& out, const HashDictionary<K, V>& aDict); }; #include "HashDictionary.cpp" #endif // HASHDICTIONARY_HPP