5
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You know std::map is 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\$ May 15 at 20:28
  • 1
    \$\begingroup\$ If I had given out the task, I would probably have failed it due to its usage of std::map \$\endgroup\$
    – erikkallen
    May 16 at 9:56
9
\$\begingroup\$
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;
}

is equivalent to:

    const std::lock_guard<std::mutex> lock(m_slotMutex);
    return m_slots.insert({ key, data }).second;

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;
}

could just be:

    const std::lock_guard<std::mutex> lock(m_slotMutex);
    return (m_slots.erase(key) == 1u);

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;
}

This does two lookups, one in m_slots.find(key) and one in m_slots[key]. We could do:

   if (auto i = m_slots.find(key); i != m_slots.end())
   {
       i->second = data;
       return true;
   }

   return false;

There's no need to specify that boolean result variable right at the start and lug it across the whole function body.


    std::vector<std::shared_ptr<Block<K,D> > > m_blocks;

As Deduplicator says, we don't need shared_ptrs here.


const unsigned int MAX_BLOCK_SIZE = 5000;
const unsigned int MIN_BLOCK_SIZE = 5000;

:(

(Do we really need these at all?)


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;
        }
    }

There's no need to catch and rethrow the exception. If we use std::vector<Block<K, D>> m_blocks; then our Hashmap constructor can be reduced to just:

Hashmap(unsigned int blockSize): 
    m_blockSize(std::clamp(blockSize, MIN_BLOCK_SIZE, MAX_BLOCK_SIZE)),
    m_blocks(m_blockSize) { }

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;
}

Again, we shouldn't catch the exception. We might be out of memory, or something might have gone wrong in copying the data value when inserting. Either way, the user has to know about it, so we want to let the exception propagate. Eating it and returning false is dangerous.

So we can do:

    return m_blocks[getBlockNum(key)].insert(key, data);

The erase and read and update functions have the same problem.


\$\endgroup\$
7
\$\begingroup\$
  1. Building-blocks only ever interact directly with the user in two circumstances:

    • A violation of program invariants is detected and the program must be shut down immediately to avoid further damage.
      Normal output is wrong for that, logging and error-stream resp. error-prompt are appropriate.

    • The purpose of the code is interacting with the user.

    Everything else is deferred to the caller using error-codes and exceptions, because you don't have any business to decide what to do about it.

    Your code doesn't fall under the second category, and even if it would fulfill the first (it doesn't), it goes about informing wrong.

  2. Nowhere in the description is any indication you should care about thread-safety. Don't pay the code and runtime penalty.

    But especially, don't half-arse it. Part of your code tries to be thread-safe, part of your code doesn't care.

  3. Shared ownership is for the exceptional cases it cannot be avoided. You can though.

  4. Do you want to avoid copying keys and values? Your code is a bit bi-polar in that respect.
    For bonus points, allow emplace-construction.

  5. Take a look at the standard-libraries naming-conventions. Try to follow them.

\$\endgroup\$
1
  • \$\begingroup\$ The standard libraries naming isn't always consistent, I think as long as a common and consistent naming style is applied that's totally fine. \$\endgroup\$
    – jjj
    May 16 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.