Simple Chained HashMap

Question

I am very inexperienced at C++. I wrote a Hash Map which uses chaining for collision resolution. I intentionally did not use smart-pointers, as the objective of this was to learn and showcase. I have tested the code and removed all bugs I came across. I am hoping to get feedback on bad practices and potential risks associated with my code.

HashMap.h

#pragma once
#include <string>

#include "HashElement.h"

class HashMap
{
private:
    HashElement **map_;
    int size_;
    int count_;
public:
    HashMap(int);
    ~HashMap();
    int GetHash(int);
    void Put(int, std::string);
    std::string GetElement(int);
    bool Contains(int);
    void Remove(int);
    int GetCount();
};

HashMap.cpp

#include "HashMap.h"
#include "PrimeChecker.h"

HashMap::HashMap(int size)
{
    while (!PrimeChecker::IsPrime(size)){
        size++;
    }
    size_ = size;
    map_ = new HashElement*[size_]();
}

HashMap::~HashMap()
{
    for (int i = 0; i < size_; i++){
        int hash = GetHash(i);
        if (!map_[hash]){
            continue;
        }
        HashElement *current_element = map_[hash];
        HashElement *next_element = map_[hash];
        while (next_element->next_element_){
            next_element = next_element->next_element_;
            delete current_element;
            current_element = next_element;
        }
        delete current_element;
    }
}

int HashMap::GetHash(int key){
    return key % size_;
}

void HashMap::Put(int key, std::string value){
    int hash = GetHash(key);
    if (!map_[hash]){
        map_[hash] = new HashElement(key, value);
    }
    else{
        HashElement *last_element = map_[hash];
        while (last_element->next_element_){
            last_element = last_element->next_element_;
        }
        last_element->next_element_ = new HashElement(key, value);
    }
    count_++;
}

std::string HashMap::GetElement(int key){
    int hash = GetHash(key);
    if (map_[hash]){
        HashElement *current_element = map_[hash];
        while (current_element->GetKey() != key && current_element->next_element_){
            current_element = current_element->next_element_;
        }
        return current_element->GetValue();
    }
    return nullptr;
}

bool HashMap::Contains(int key){
    int hash = GetHash(key);
    if (map_[hash]){
        HashElement *current_element = map_[hash];
        while (current_element->GetKey() != key && current_element->next_element_){
            current_element = current_element->next_element_;
        }
        if (current_element->GetKey() == key){
            return true;
        }
    }
    return false;
}

void HashMap::Remove(int key){
    if (!Contains(key)){
        return;
    }
    int hash = GetHash(key);
    HashElement *current_element = map_[hash];
    if (current_element->GetKey() == key){
        map_[hash] = currentElement->next_element_;
        delete current_element;
    }
    else{
        HashElement *previous_element = current_element;
        current_element = current_element->next_element_;
        while (current_element->GetKey() != key){
            previous_element = current_element;
            current_element = current_element->next_element_;
        }
        previous_element->next_element_ = current_element->next_element_;
        delete current_element;
    }
    count_--;
}

int HashMap::GetCount(){
    return count_;
}

HashElement.h

#pragma once

#include <string>

class HashElement
{
private:
    int key_;
    std::string value_;
public:
    HashElement(int, std::string);
    ~HashElement();
    HashElement *next_element_;
    int GetKey();
    std::string GetValue();
};

HashElement.cpp

#include "HashElement.h"

HashElement::HashElement(int key, std::string value)
{
    key_ = key;
    value_ = value;
    next_element_ = nullptr;
}

HashElement::~HashElement()
{
}

int HashElement::GetKey(){
    return key_;
}

std::string HashElement::GetValue(){
    return value_;
}

PrimeChecker.h

#pragma once
namespace PrimeChecker
{
    bool IsPrime(int);
}

PrimeChecker.cpp

#include "PrimeChecker.h"

namespace PrimeChecker
{
    //This method was adapted from http://en.wikipedia.org/wiki/Primality_test
    bool IsPrime(int number)
    {
        if (number <= 3) {
            return number > 1;
        }
        else if (number % 2 == 0 || number % 3 == 0) {
            return false;
        }
        else {
            for (unsigned short i = 5; i * i <= number; i += 6) {
                if (number % i == 0 || number % (i + 2) == 0) {
                    return false;
                }
            }
            return true;
        }
    }
}

glampert · Accepted Answer · 2015-03-03 01:41:50Z

I think it is quite good. Without touching on algorithmic and design aspects, I can see a few points that you can further improve with the current code:

You are missing Const Correctness on const methods. This is an important aspect of C++ that is not obvious, so it is common for beginners or people migrating from other languages to miss it.
This is a bit of a personal suggestion, but I consider the public parts of a class to be more relevant for people reading my code, so I tend to place public methods and data first, followed by protected and finally private members, which are implementation details that only concern the programmer implementing the class(es).
I suggest keeping function parameter names in your function prototypes, as this will add to the documentation of the code.
For HashMap, I would change a few method names:

Instead of Put to add a value to the map, I would call it Insert, to closer resemble the Standard map<T> data structure that most C++ programmers are familiar with.

Also, instead of GetElement to fetch a value, I would name it Find, again to resemble the Standard map type but also because Get* implies a light weight operation while GetElement might be a linear search in the bucket chain if the value is not the first one.
You need to give some thought to the Rule of Three, which is about how your class is going to behave regarding value copy/assignment. As it stands, one could create copies of a HashMap using operator = and the default copy constructor. That would be disastrous, since each instance of a map own its memory and a copy with = would be a shallow copy of just the pointer, leading to duplicate attempts to free the same memory.

The simplest approach would be disabling copy and assignment by making operator = and the copy constructor private (or deleting them). A more robust solution is implementing custom ones that perform a deep copy of the map.
HashElement doesn't seem to be used anywhere outside HashMap, so it could be an inner class declared inside the private section of HashMap.
The destructor of HashElement is empty, so you should not declare one and let the compiler supply the default.
Try to always initialize data in constructors using the constructor initialization list. Taking HashElement as example, the proper way would be:
```
  HashElement::HashElement(int key, std::string value)
      : key_(key)
      , value_(std::move(value))
      , next_element_(nullptr)
  { }
```
Doing so will ensure that the members are also initialized by the constructor instead of the assignment operator.

Also note std::move() when initializing value_. This is part of the C++11 move semantics, which will remove a redundant copy that you don't need.

Consider providing operator [] to allow usage such as:

myMap[42] = "hello world";

The Standard C++ map provides such operator. You might want to use it as a guideline:

class HashMap {
    ...
    std::string& operator[] (int key);
};

std::string& HashMap::operator[] (int key)
{
    // How you'll implement this depends.
    // If you follow the convention of std::map,
    // This method should create a new entry if the
    // <key, value> pair is not present, returning a 
    // reference to it one completed.
    // If the entry is already available, 
    // just return a reference to the value.
    //
    // Pseudocode:
    //  if (key !in map)
    //      insert(key, new string);
    //  return ref find(key); 
}

The namespace PrimeChecker seems a bit unnecessary and verbose. IsPrime() at the global namespace would be fine too.

Such a detailed analysis! Thanks! I am still going through everything and learning what it all means along the way. But can you clarify on this one, please?: "I suggest keeping function parameter names in your function prototypes, as this will add to the documentation of the code." — Evorlor
– Evorlor, Commented Mar 2, 2015 at 18:40
@Evorlor, sure. Take Put(int, std::string) for instance. It might not be clear which of the parameters is the key and which is the value. Not all maps necessarily use an integer as key (strings are also very common). If you instead keep the parameter names: Put(int key, std::string value) that becomes explicit. This is self-documenting. No need to write a commend at the top saying "first parameter is the key, second is the value". — glampert
– glampert, Commented Mar 2, 2015 at 18:57
I hate to ask, but I have a couple of follow up questions if you don't mind: 1. What redundant copy of value_ are you talking about? Why do I need to std::move() it, but nothing else? 2. Can you provide an example of operator[]? I have read around and tried a few examples, but I keep getting a missing arguments error. — Evorlor
– Evorlor, Commented Mar 2, 2015 at 23:59
@Evorlor, If you notice it, the std::string parameter value, is being passed by value (C++ has pass-by-value, pointer and reference). When you pass a parameter by value, it is copied into the function. Move elides the copy by just, well, moving the local object to its final destination, as the name suggests. This is the recommended for modern C++11, that is, passing by value using std::move when you are copying a parameter. — glampert
– glampert, Commented Mar 3, 2015 at 1:28
@Evorlor, by default, everything is passed by value in C++, which involves a copy. For native types, that's what you want, but complex objects might be expensive to copy, so we should take extra care. — glampert
– glampert, Commented Mar 3, 2015 at 2:56

ChrisWue · Accepted Answer · 2015-03-02 19:17:07Z

There is a bug in GetElement. The hash of the key is just a modulo the size of the hashmap which means it's very easy to create different keys with the same hash. If you find an entry for a given hash value you just iterate the list until you either find the entry with the provided key or you have reached the end. If the end is reached the last entry in the list is returned even if the key didn't match. Bug reproduced here.
While putting the code through ideone it failed with a compile error in Remove due to currentElement not being declared - should have been current_element instead.
I think a lot of the operations could be simplified if you create a method which returns a pointer to the previous element of the one you are interested in (so that prev->next points to the entry you are interested in) or nullptr in case it's not found. This allows you to simplify implementations for finding and removing elements and reducing duplicate code.

1. Great catch! I removed " && current_element->next_element_". 2. Oops! Missed one when I was fixing my naming conventions. 3. Great idea! I will definitely work on making that method. I should have done that initially. — Evorlor
– Evorlor, Commented Mar 2, 2015 at 19:47

Stack Exchange Network

Simple Chained HashMap

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Simple Chained HashMap

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions