Hash Mapping

Use the implementation of the hash_example.cpp and do the following modifications:

• modify the implementation of insert() so that it provides "safe insert", i.e.: returns a pair: < pointer, result>, 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 < pointer, result>, 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.cpp

// demoes hashmap implementation


#include "hashmap.h"
#include < iostream>
#include < string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

int main()
{
// Test the safe insert
hashmap numbers;

// Expect insert successful since "One" is unique
pair result = numbers.insert(pair(1, 1));

if (result.second)
{
cout << "Insert of <1, 1> returned positive response... test ok." << endl;

if (*result.first != 1)
cout << "After insert of <1, 1> it returned the value 1... test failed." << endl;
else
cout << "After insert of <1, 1> it did not return the value 1... test ok." << endl;
}
else
{
cout << "Insert of <1, 1> returned negative response... test failed." << endl;
}

// Re-insert a "One" but should fail because it is not unique
result = numbers.insert(pair(1, 2));

if (result.second)
cout << "Insert of <1, 2> returned a positive response... test failed." << endl;

// Test the indexing operator still works
cout << "numbers[1] = " << numbers[1] << " ... expected value should be 1" << endl;

// Test erase
result = numbers.erase(1);

if (result.second)
{
cout << "Remove 1 returned a positve response... test ok." << endl;

if (*result.first != 1)
cout << "After remove, the removed value is 1... test ok." << endl;
else
cout << "After remove, the removed value is not 1... test failed." << endl;
}
else
{
cout << "Remove 1 returned a positive response... test failed." << endl;
}

// Populate the hashmap
for (int i = 1; i <= 10; i++)
{
cout << "Insert <" << i << ", " << i << ">..." << endl;
numbers.insert(pair(i, i));
}

// Retrieve
for (int i = 1; i <= 10; i++)
cout << "numbers[" << i << "] = " << numbers[i] << "... expected value should be " << i << endl;


// Rehash test
cout << "Rehashing, numbers.rehash(5)" << endl;
numbers.rehash(5);

// Retrieve
for (int i = 1; i <= 10; i++)
cout << "numbers[" << i << "] = " << numbers[i] << "... expected value should be " << i << endl;

return 0;
}

hashmap.h

// implementation basic hashmap (unordered container)


#include < cstddef>
#include < utility>
#include < functional>
#include < vector>
#include < list>

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 < typename T>
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 < typename T>
DefaultHash< T>::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 < typename T>
size_t DefaultHash< T>::hash(const T& key) const {
size_t res = 0;
for (size_t i = 0; i < sizeof(key); ++i) {
const unsigned char b =
*(reinterpret_cast< const unsigned char*>(&key) + i);
res += b;
}
return res % numBuckets_;
}


////////////////////////////////////////////////
// container class
////////////////////////////////////////////////

template < typename Key, typename Value,
typename Compare = std::equal_to< Key>,
typename Hash = DefaultHash< Key >>
class hashmap {

public:
typedef pair< const Key, Value> 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

pair< Value *, bool> insert(const Element& x); // inserts the key/value pair
pair< Value *, bool> 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

void rehash(size_t n);
private:

// helper function for various searches
typename list< Element>::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< list< Element>> elems_;
};


////////////////////////////////////////////////
// container member functions
////////////////////////////////////////////////

// Construct elems_ with the number of buckets.
template < typename Key, typename Value, typename Compare, typename Hash>
hashmap< Key, Value, Compare, Hash>::hashmap(
const Compare& comp, const Hash& hash) :
size_(0), comp_(comp), hash_(hash) {
elems_ = vector< list< Element>>(hash_.numBuckets());
}


// helper function
template < typename Key, typename Value,
typename Compare, typename Hash>
typename list< pair< const Key, Value>>::iterator // return type
hashmap< Key, Value, Compare, Hash>::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 Key, typename Value, typename Compare, typename Hash>
typename hashmap< Key, Value, Compare, Hash>::Element* // return value type
hashmap< Key, Value, Compare, Hash>::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 < typename Key, typename Value, typename Compare, typename Hash>
pair< Value *, bool> hashmap< Key, Value, Compare, Hash>::insert(const Element& x)
{
// TO DO
}


// removes the Element with key x, if it exists
template < typename Key, typename Value, typename Compare, typename Hash>
pair< Value *, bool> hashmap< Key, Value, Compare, Hash>::erase(const Key& x)
{
// TO DO
}


// returns reference to value of element with key x,
// inserts if does not exist
template < typename Key, typename Value, typename Compare, typename Hash>
Value& hashmap< Key, Value, Compare, Hash>::operator[] (const Key& x) {
// TO DO
}

// Re-hash the elements with a new size
template < typename Key, typename Value, typename Compare, typename Hash>
void hashmap< Key, Value, Compare, Hash>::rehash(size_t n)
{
// TO DO
}