HashTable implementation in C++

I made a simple hash table and I was wondering if there was any way to increase the efficiency of search times. My table class is called Dictionary, because C# has tainted me.

The way I set this up is that Dictionary has an array of Buckets, a modified linked list whose Nodes store string keys as well as whatever other data.

I use a modular hash function to get the index of the array the Dictionary should access in, then search/insert with the Bucket at that index.

Dictionary class:

```
#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_

#include
#include

#include "bucket.h"

using namespace std;

template
class Dictionary
{
private:

Bucket* mBuckets;

// Number of buckets
int mCount;

int hash(string key)
{
// Modular hashing algorithm

int value = 0;

for (int i = 0; i
Dictionary::Dictionary()
{
// Default mCount to 16
this->mCount = 16;

// Define mBins
mBuckets = new Bucket>[mCount];
}

template
Dictionary::Dictionary(int mCount)
{
// Default mCount to 16 if invalid
this->mCount = (mCount >= 0 ? mCount : 16);

// Define mBins
mBuckets = new Bucket[mCount];
}

template
Dictionary::~Dictionary()
{
delete[] mBuckets;
}

//
// Functions
//

template
bool Dictionary::containsKey(string key)
{
int bin = hash(key);

return mBuckets[bin].isExist(key);
}

template
void Dictionary::display()
{
cout

void Dictionary::displayDistribution()
{
cout

int Dictionary::getCount()
{
int count = 0;
for (int i = 0; i
T Dictionary::getData(string key)
{
int bin = hash(key);

return mBuckets[bin].getData(key);
}

template
bool Dictionary::insert(string key, T value)
{
int bin = hash(key);

mBuckets[bin].insert(key, value);

return true;
}

template
bool Dictionary::isEmpty()
{
return

First and foremost

there is std::unordered_map. If you just need a hash map, use it.

What's wrong

-
Your hash is an int, if your string consists of negative chars or overflows, you will get a negative value at the end. In C/C++ the modulo operator (%) returns a negative value for a negative input.

-
How does that compile? What's Item?

mBuckets = new Bucket>[mCount];

Performance

-
Your code doesn't support rebalance. That is quite essential if you want to provide generic performance. See std::unordered_map::rehash.

-
Profile your code to find out where time is spent.

-
Avoid unnecessary copies when taking generic arguments as parameters and returning them. In general take by const& and return (const)&. This applies both for the std::string parameters as well as for the generic type T. If this is really heavyly used library code, consider using perfect forwarding.

Points for improvement

• Do not use using std. Especially not in library code.

• You don't provide const interface. You cant even ask isEmpty on a const Dictionary

• Your hash function is bad: Just adding the values does not work well. "foo" has the same hash as "oof".

• Implement the standard operators following the expected semantic e.g. operator[] for element access.

• Use nullptr instead of NULL.

• Use std::unique_ptr<> for owning pointers instead of managing memory manually.

• Use initializer lists instead of initializing members in constructors.

• Don't implement all aspects of a constructor twice, rely on one from the other if possible

• Simply returning when your new returns NULL is a VERY BAD IDEA.

• Provide begin()/end() for iterators.

• Don't implement output within your template library code.

• Why use double linked Nodes? The whole point of the hashtable is that there should never be an excess number of Nodes in one Bucket anyway. The Bucket::insert is incredibly difficult to read.

• Use algorithms instead of raw loops.

• Your manual new / delete will probably start leak as soon as exceptions happen.

Due to the amount of points I cannot go into details with each and everyone. Most of the points are standard items that should be easily searchable. Please ask if you have a specific question.

StackExchange Code Review Q#108695, answer score: 14