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 */ /** constructor * Standard constructor for the HashDictionary * * @param tableSize The size of the hash table that should be * generated for internal use by this dictionary for hasing. * @param emptyKey A special flag/value that can be used to detect * invalid/unused keys. We need this so we can indicate which * slots/buckets in our hash table are currently empty, and also * this value is used as a return result when an unsuccessful * search is performed on the dictionary. */ template <class Key, class Value> HashDictionary<Key, Value>::HashDictionary(int tableSize, Key emptyKey) { this->tableSize = tableSize; this->EMPTYKEY = emptyKey; valueCount = 0; // allocate an array/table of the indicated initial size hashTable = new KeyValuePair<Key, Value>[tableSize]; // initialize the hash table so all slots are initially empty for (int index = 0; index < tableSize; index++) { hashTable[index].setKey(EMPTYKEY); } } /** destructor * Standard destructor for the HashDictionary. Be good memory managers and * free up the dynamically allocated array of memory pointed to by hashTable. */ template <class Key, class Value> HashDictionary<Key, Value>::~HashDictionary() { delete[] hashTable; } /** size * Accessor method to get the current size of this dictionary, * e.g. the count of the number of key/value pairs currently being * managed in our hash table. * * @returns in Returns the current number of items being managed by * this dictionary and currently in our hashTable. */ template <class Key, class Value> int HashDictionary<Key, Value>::size() const { return valueCount; } // Place your implementations of the class methods probe(), hash(), // insert() and find() here /** overload indexing operator[] * Overload indexing operator[] to provide direct access * to hash table. This is not normally part of the Dictionary * API/abstraction, but included here for testing. * * @param index An integer index. The index should be in the range 0 - tablesize-1. * * @returns KeyValuePair<> Returns a KeyValuePair object if the index into the * internal hash table is a valid index. This method throws an exception if * the index is not a valid slot of the hash table. */ template <class Key, class Value> KeyValuePair<Key, Value>& HashDictionary<Key, Value>::operator[](int index) { if (index < 0 || index >= tableSize) { cout << "Error: <HashDictionary::operator[] invalid index: " << index << " table size is currently: " << tableSize << endl; assert(false); } return hashTable[index]; } /** HashDictionary output stream operator * Friend function for HashDictionary. We normally wouldn't have * something like this for a Dictionary or HashTable, but for testing * and learning purposes, we want to be able to display the contents of * each slot in the hash table of a HashDictionary container. * * @param out An output stream reference into which we should insert * a representation of the given HashDictionary. * @param aDict A HashDictionary object that we want to display/represent * on an output stream. * * @returns ostream& Returns a reference to the original given output stream, * but now the values representing the dictionary we were given should * have been sent into the output stream. */ template <typename K, typename V> ostream& operator<<(ostream& out, const HashDictionary<K, V>& aDict) { for (int slot = 0; slot < aDict.tableSize; slot++) { out << "Slot: " << slot << endl; out << " Key : " << aDict.hashTable[slot].key() << endl; out << " Value: " << aDict.hashTable[slot].value() << endl; } out << endl; return out; }