Use the implementation of the basic hashmap template that we studied and do the following modifications:

• modify the implementation of insert() so that it provides "safe insert", i.e.: returns a pair: , where
  • pointer is a pointer to the newly inserted value or the old value with the same key
  • result is a boolean value which is true if the element is inserted
• on the basis of your updated insert() implementation, modify the implementation of the overloaded indexing operator [] to eliminate inefficient second invocation of find(). That is, in your implementation, find() should only be invoked once.
• modify the implementation of erase() so that it returns a pair , where
  • pointer is a pointer to the element past one erased. Note that if the next element in a different bucket, it should still be returned. In case the element with the key specified to erase() does not exist, the value of the returned pointer is unspecified. If erase() removes the last element of the container (the last element of the list of the last bucket), then erase() should return nullptr.
  • result is a boolean value which is true if the element is successfully erased; result is false if the element with the specified key is not present in the container.
• implement void rehash(size_t n) sets the number of buckets in the container to n. Note that the existing elements need to be re-arranged according to their new hash value. Note also that Hash: the object that provides hashing, needs to be updated to contain the new number of buckets. If the parameter n is smaller than the current number of buckets, no actions need to be taken.

Provide test code that declares and populates a container and then demonstrates the operation of the functions you implemented.

Hashmap.hpp

#include #include #include #include #include using std::vector; using std::list; using std::pair; using std::make_pair; ////////////////////////////////////////// // hash function implemented as a class ////////////////////////////////////////// // any Hash Class must provide // two methods: hash() and numBuckets(). template class DefaultHash { public: DefaultHash(size_t numBuckets = defaultNumBuckets); size_t hash(const T& key) const; size_t numBuckets() const { return numBuckets_; } private: // default number of buckets in the hash static const size_t defaultNumBuckets = 101; size_t numBuckets_; }; template DefaultHash::DefaultHash(size_t numBuckets): numBuckets_(numBuckets) {} // uses the division method for hashing. // treats the key as a sequence of bytes, sums the ASCII // values of the bytes, and mods the total by the number // of buckets. // note, this function does not work for C++ strings template size_t DefaultHash::hash(const T& key) const { size_t res = 0; for (size_t i = 0; i < sizeof(key); ++i) { const unsigned char b = *(reinterpret_cast(&key) + i); res += b; } return res % numBuckets_; } //////////////////////////////////////////////// // container class //////////////////////////////////////////////// template , typename Hash = DefaultHash> class hashmap{ public: typedef pair Element; // constructor // invokes constructors for comparison and hash objects hashmap(const Compare& comp = Compare(), const Hash& hash = Hash()); Element* find(const Key& x); // returns pointer to element with key x, // nullptr if not found void insert(const Element& x); // inserts the key/value pair void erase(const Key& x); // erases element with key x, if exists Value& operator[] (const Key& x); // returns reference on value of // element with key, inserts if does not exist private: // helper function for various searches typename list::iterator findElement(const Key& x, const size_t bucket); size_t size_; // number of elements in the container Compare comp_; // comparison functor, equal_to by default Hash hash_; // hash functor // hash contents: vector of buckets // each bucket is a list containing key->value pairs vector> elems_; }; //////////////////////////////////////////////// // container member functions //////////////////////////////////////////////// // Construct elems_ with the number of buckets. template hashmap::hashmap( const Compare& comp, const Hash& hash): size_(0), comp_(comp), hash_(hash) { elems_ = vector>(hash_.numBuckets()); } // helper function template typename list>::iterator // return type hashmap::findElement(const Key& x, size_t bucket){ // look for the key in the bucket for (auto it = elems_[bucket].begin(); it != elems_[bucket].end(); ++it) if (comp_(it->first, x)) return it; return elems_[bucket].end(); // element not found } // returns a pointer to the element with key x // returns nullptr if no element with this key template typename hashmap::Element* // return value type hashmap::find(const Key& x) { size_t bucket = hash_.hash(x); auto it=findElement(x, bucket); // use the findElement() helper if (it != elems_[bucket].end()) // found the element. Return a pointer to it. return &(*it); // dereference the iterator to list // then take the address of list element else // didn't find the element -- return nullptr return nullptr; } // finds the element with key x, inserts an // element with that key if none exists yet. Returns a reference to // the value corresponding to that key. template void hashmap::insert(const Element& x) { size_t bucket = hash_.hash(x.first); auto it = findElement(x.first, bucket); // try to find the element // if not found, insert a new one. if (it == elems_[bucket].end()) { ++size_; elems_[bucket].push_back(x); } } // removes the Element with key x, if it exists template void hashmap::erase(const Key& x) { size_t bucket = hash_.hash(x); auto it = findElement(x, bucket); // try to find the element if (it != elems_[bucket].end()) { // the element exists, erase it elems_[bucket].erase(it); --size_; } } // returns reference to value of element with key x, // inserts if does not exist template Value& hashmap::operator[] (const Key& x) { Element* found = find(x); if (found == nullptr) { // if key not found, create new element with empty value insert(make_pair(x, Value())); // calling default constructor on Value found = find(x); // inefficient but avoids code duplication } return found->second; }

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

testhashmap.cpp

#include "hashmap.hpp" #include #include using std::cin; using std::cout; using std::endl; using std::string; int main() { hashmap myHash; myHash.insert(pair(4, 40)); myHash.insert(make_pair(6, 60)); // x will have type hashmap::value_type* auto x = myHash.find(4); if (x != nullptr) cout << "4 maps to " << x->second << endl; else cout << "cannot find 4 in map" << endl; myHash.erase(4); auto x2 = myHash.find(4); if (x2 != nullptr) cout << "4 maps to " << x2->second << endl; else cout << "cannot find 4 in map" << endl; myHash[4] = 35; myHash[4] = 60; auto x3 = myHash.find(4); if (x3 != nullptr) cout << "4 maps to " << x3->second << endl; else cout << "cannot find 4 in map" << endl; hashmap employees; // entering entries with indexing operator employees[123] = "Mike"; employees[345] = "Charlie"; employees[192] = "Joe"; employees[752] = "Paul"; employees[328] = "Peter"; cout << "Enter new employee number: "; int num; cin >> num; cout << "Enter new employee name: "; string name; cin >> name; employees[num] = name; // "unsafe" insert // searching map cout << "Enter employee number to look for: "; cin >> num; auto it = employees.find(num); if(it != nullptr) cout << it->first << ":" << it->second << endl; else cout << "employee not found" << endl; // removing from a map cout << "Enter employee number to fire: "; cin >> num; employees.erase(num); // check if not there auto removed = employees.find(num); if (removed == nullptr) cout << "Employee removed successfully" << endl; }