4
\$\begingroup\$

Does this look like a proper implementation of a hash table in C++? Any errors anyone can find? Thanks in advance (:

template <typename T>
class HashTable
{
public:
HashTable(int amount)
{
    size = amount;
    values = new T*[size];
    for (int i = 0; i < size; i++)
    {
        *(values + i) = nullptr;
    }
}
~HashTable()
{
    if(values != nullptr)
    {
        for (int i = 0; i < size; i++)
        {
            if(*(values + i) != nullptr)
            {
                delete *(values + i);
                *(values + i) = nullptr;
            }
        }
        delete[] values;
    }
}

void addValue(const std::string & key, T value)
{
    int location = hash(key);

    if (*(values + location) == nullptr)
    {
        *(values + location) = new T;
    }

    **(values + location) = value;
}

void printValues()
{
    for (int i = 0; i < size; i++)
    {
        if (*(values + i) != nullptr)
        {
            printf("value : %i\n", **(values + i));
        }
    }
}

T* getValue(const std::string & key)
{
    return *(values + hash(key))
}

private:

int hash(const std::string & key)
{
    int value = 0;
    for (unsigned int i = 0; i < key.length(); i++)
    {
        value += key[i] * (i + 1);
    }
    return value % size;
}

int size;
T ** values = nullptr;
};
\$\endgroup\$
2
  • \$\begingroup\$ You are not handling collisions, i.e. when two different keys get mapped to the same slot you can't simply overwrite what was there (unless the keys are identical), but have to handle storing both key-value pairs somehow. There are several ways to do that, the Wikipedia page has some good descriptions of the main ones. \$\endgroup\$
    – Jaime
    May 3, 2016 at 18:37
  • 3
    \$\begingroup\$ No the correct way is to use the one provided by the standard. std::unordered_map \$\endgroup\$ May 3, 2016 at 19:23

2 Answers 2

2
\$\begingroup\$

The biggest issue is, as mentioned in the comments, that you don't handle collisions. I'm not going to cover that, but I'll address some other issues.

IMO your hashtable should be templated on at least 3 types - the key type, the value type, and the hash functor. This way you aren't limiting your users to having string keys or to rely on your hash function.

You should also use colon initialization - the data members will be default initialized at the starting curly brace of the constructor, but with colon initialization you skip the default initialization and the replacement with new values. That would look something like this

HashTable(size_t amount) : size(amount), values(new Value*[size]) { 
    for (size_t i = 0; i < size; ++i) {
        values[i] = nullptr; 
    }   
}

You'll notice I've replaced your ints with size_t - in these situations you don't need negative numbers. I've also used the subscript notation instead of pointer arithmatic, which is much, much easier to read and reason about. You should strongly prefer subscript notation if it is possible to use it.

Your destructor doesn't need to check if the the values are not nullptr - there isn't a sensible reason it should be.

You should be using const functions - printValues should be, and you should provide a const version of getValue as well.

You also assume that the value type can be default initialized, which is not necessarily true. You might want to use placement new here instead. Alternatively, you could just split up the code a bit.

void addValue(const std::string & key, T value)
{
    int location = hash(key);

    if (values[location] == nullptr) 
    {
        values[location] = new T(value);
    }
    else
    {
        *values[location] = value;
    }
}

This still requires that there be a copy constructor, however this is probably a less surprising requirement (most containers expect objects to be copy/move constructible).

You'll probably want to provide an iterator as well, but I'll leave that as an exercise for the reader.

Lastly, you should provide a method to find and erase, and probably resize your hash table. Without those things the hash table doesn't have much use.

\$\endgroup\$
2
\$\begingroup\$

Prefer to use the initializer list than write code.

HashTable(int amount)
{
    size = amount;
    values = new T*[size];
    for (int i = 0; i < size; i++)
    {
        *(values + i) = nullptr;
    }
}

This could be much easier written as:

HashTable(int amount)
    : size(amount)
    , values(new T*[size]())   // Notice the '()' this forces zero initialization.
                               // So all the elements in the array are nulls.
{}

No need to check for nullptr.

~HashTable()
{
    // You know this can never be nullptr.
    // you initialized it in the constructor.
    // Note: if new fails it throws an exception
    //       so this can never be null.
    if(values != nullptr)
    {
        for (int i = 0; i < size; i++)
        {
            // don't need to test before calling delete its valid.
            if(*(values + i) != nullptr)
            {

                // You can use array syntax for accessing the elements.
                delete *(values + i);
                *(values + i) = nullptr;
            }
        }
        delete[] values;
    }
}

Better version:

~HashTable()
{
    for (int i = 0; i < size; i++)
    {
        delete values[i];
    }
    delete[] values;
}

You don't objey the rule of three (or five). Look them up.

This does not handle collisions of the hash.

void addValue(const std::string & key, T value)

This is not very useful it just prints pointers.

void printValues()

C++ has a much better way of serializing values.

            printf("value : %i\n", **(values + i));

This is a very basic hashing function.

int hash(const std::string & key)

There are much better ones out there. I think you will find you get more clashes than you think from a standard corpus of text.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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