I have been asked to implement a HASHMAP in C++ in a job interview (home assignment).
I'm a bit unsure about exception safety, but this is what I came up with:
Block.h
#ifndef BLOCK_H
#define BLOCK_H
#include <deque>
#include <map>
#include <mutex>
#include <iostream>
#include <memory>
namespace NsHashmap
{
template <class K, class D>
using MapIterator = typename std::map<K,D>::iterator;
template <class K, class D>
class Block
{
private:
std::map<K,D> m_slots;
std::mutex m_slotMutex;
public:
bool insert (const K &key, const D &data);
bool update (const K &key, const D &data);
bool read(const K &key, D &data);
bool erase (const K &key);
Block()
{ }
};
/* <summary>
Inserts element into the HashMap.
</summary>
<param name="key">Key of the data to be inserted</param>
<param name="data">Data to be inserted</param>
<returns>Returns Success if inserted or returns false</returns>
*/
template <class K, class D>
bool Block<K,D>::insert(const K &key, const D &data)
{
bool result = false;
const std::lock_guard<std::mutex> lock(m_slotMutex);
if (m_slots.find(key) == m_slots.end())
{
m_slots[key] = data;
result = true;
}
else
{
//Key already present , cant insert return false.
result = false;
}
return result;
}
/* <summary>
Read the element from the slot.'data' is the pass by reference parameter
the read element will be stored in 'data' , so user can use it.
Return parameter is used to pass success/failure of the read.
</summary>
<param name="key">Key of the data to be read</param>
<param name="data">Data to be read</param>
<returns>Returns Success if read or returns false</returns>
*/
template <class K,class D>
bool Block<K,D>::read(const K &key, D &data)
{
bool result = false;
const std::lock_guard<std::mutex> lock(m_slotMutex);
MapIterator<K,D> itr;
if (( itr = m_slots.find(key)) != m_slots.end())
{
data = itr->second;
result = true;
}
return result;
}
/* <summary>
Erases the element from the Slot.
</summary>
<param name="key">Key of the data to be erased</param>
<param name="data">Data to be erased</param>
<returns>Returns Success if erased or returns false</returns>
*/
template <class K,class D>
bool Block<K,D>::erase(const K &key)
{
bool result = false;
const std::lock_guard<std::mutex> lock(m_slotMutex);
MapIterator<K,D> itr;
if (( itr = m_slots.find(key)) != m_slots.end())
{
m_slots.erase(itr);
result = true;
}
return result;
}
/* <summary>
Update the data of an element in the Slot.
</summary>
<param name="key">Key of the data to be updated</param>
<param name="data">Data to be updated</param>
<returns>Returns Success if updated or returns false</returns>
*/
template <class K,class D>
bool Block<K,D>::update(const K &key, const D &data)
{
bool result= false;
const std::lock_guard<std::mutex> lock(m_slotMutex);
if (m_slots.find(key) != m_slots.end())
{
m_slots[key] = data;
result = true;
}
return result;
}
}
#endif
HashMap.h
#ifndef Hashmap_H
#define Hashmap_H
#include<iostream>
#include "Block.h"
#include <vector>
#include <memory>
namespace NsHashmap
{
const unsigned int MAX_BLOCK_SIZE = 5000;
const unsigned int MIN_BLOCK_SIZE = 5000;
/* <summary>
Template Class for Hashmap.
</summary>
<typeparam name="K">Datatype of the Key</typeparam>
<typeparam name="K">Datatype of the data to be stored in Hashmap</typeparam>
*/
template <class K, class D>
class Hashmap
{
private:
std::vector<std::shared_ptr<Block<K,D> > > m_blocks;
std::hash<K> m_hashGen;
int getBlockNum(K key);
unsigned int m_blockSize;
public:
/* <summary>
Inserts element into the Hashmap
</summary>
<param name="key">Key of the data to be inserted</param>
<param name="data">Data to be inserted</param>
<returns>Returns Success if inserted or returns false</returns>
*/
bool insert(K key, D data);
/* <summary>
Read element from the Hashmap by Key
</summary>
<param name="key">Key of the data to be read</param>
<param name="data">Data read from the Hashmap.
this is a reference object,out parameter
// to send the data to the caller</param>
<returns>Returns Success if read the data or returns false</returns>
*/
bool read(K key, D &data);
/* <summary>
Update the element's data in the Hashmap
</summary>
<param name="key">Key of the data to be updated </param>
<param name="data">Data to be updated</param>
<returns>Returns Success if updated or returns false</returns>
*/
bool update(K key, D data);
/* <summary>
Erase the element's data in the Hashmap
</summary>
<param name="key">Key of the data to be erased </param>
<param name="data">Data to be erased</param>
<returns>Returns Success if erased or returns false</returns>
*/
bool erase(K key);
/* <summary>
Hashmap Constructor, it creates blocks and store in vector
</summary>
<param name="blockSize"> Table Size of the Hashmapblock</param>
*/
Hashmap( unsigned int blockSize): m_blockSize(blockSize)
{
if (m_blockSize > MAX_BLOCK_SIZE)
{
m_blockSize = MAX_BLOCK_SIZE;
}
else if (m_blockSize < MIN_BLOCK_SIZE)
{
m_blockSize = MIN_BLOCK_SIZE;
}
try
{
m_blocks.reserve(m_blockSize);
for (auto i=0; i< m_blockSize;++i)
{
std::shared_ptr<Block<K,D>> objBlock = std::make_shared<Block<K,D>>
();
m_blocks.push_back(objBlock);
}
}
catch(const std::exception& e)
{
std::cerr << e.what() << '\n';
throw e;
}
}
};
template <class K, class D>
bool Hashmap<K,D>::insert(K key, D data)
{
bool result = false;
try
{
auto blockNum = getBlockNum(key);
result = m_blocks[blockNum]->insert(key,data);
}
catch(std::exception &e)
{
std::cout <<"Exception Occured in Hashmap Insert"<<e.what() <<"\n";
}
return result;
}
template <class K, class D>
bool Hashmap<K,D>::erase(K key)
{
bool result = false;
try
{
auto blockNum = getBlockNum(key);
result = m_blocks[blockNum]->erase(key);
}
catch(std::exception &e)
{
std::cout <<"Exception Occured in Hashmap erase:"<< e.what() <<"\n";
}
return result;
}
template <class K, class D>
bool Hashmap<K,D>::read(K key, D &data)
{
bool result = false;
try
{
auto blockNum = getBlockNum(key);
result= m_blocks[blockNum]->read(key, data);
}
catch(std::exception &e)
{
std::cout <<"Exception Occured in Hashmap read:"<<e.what() <<"\n";
}
return result;
}
template <class K, class D>
int Hashmap<K,D>::getBlockNum(K key)
{
auto hashKey = m_hashGen(key);
return (hashKey % m_blockSize);
}
template <class K, class D>
bool Hashmap<K,D>::update(K key, D data)
{
bool result = false;
try
{
auto blockNum = getBlockNum(key);
result = m_blocks[blockNum]->update (key,data);
}
catch(std::exception &e)
{
std::cout <<"Exception Occured in Hashmap Update:"<<e.what() <<"\n";
}
return result;
}
}
#endif
std::mapis normally a balanced (red-black) tree, right? That sounds like overkill for each bucket of a hash table; hash tables normally perform well when they're usage percentage is low enough that most elements don't collide. \$\endgroup\$