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 <iostream>#include <string>#include bucket.husing namespace std;template <class T>class Dictionary{private:    Bucket<T>* mBuckets;    // Number of buckets    int mCount;    int hash(string key)    {        // Modular hashing algorithm        int value = 0;        for (int i = 0; i < key.length(); i++)            value += key[i];        return value % mCount;    }public:    Dictionary();    Dictionary(int mCount);    ~Dictionary();    bool containsKey(string key);    void display();    int getCount();    T getData(string key);    bool insert(string key, T value);    bool isEmpty();};// ********************************************************//                Constructor / Destructor// ********************************************************template <class T>Dictionary<T>::Dictionary(){    // Default mCount to 16    this->mCount = 16;    // Define mBins    mBuckets = new Bucket<Item<T>>[mCount];}template <class T>Dictionary<T>::Dictionary(int mCount){    // Default mCount to 16 if invalid    this->mCount = (mCount >= 0 ? mCount : 16);    // Define mBins    mBuckets = new Bucket<T>[mCount];}template <class T>Dictionary<T>::~Dictionary(){    delete[] mBuckets;}// ********************************************************//                       Functions// ********************************************************template <class T>bool Dictionary<T>::containsKey(string key){    int bin = hash(key);    return mBuckets[bin].isExist(key);}template <class T>void Dictionary<T>::display(){    cout        <<  Dictionary - Items: << getCount() << \n        << *********************** \n;    for (int i = 0; i < mCount; i++)    {        cout << left << i << : ;        mBuckets[i].display();        cout << \n\n;    }}template <class T>void Dictionary<T>::displayDistribution(){    cout        <<  Dictionary - Distribution: << getCount() << \n        << *********************** \n;    for (int i = 0; i < mCount; i++)    {        cout             << left             << i << :  << mBuckets[i].getCount();        cout << \n;    }}template <class T>int Dictionary<T>::getCount(){    int count = 0;    for (int i = 0; i < mCount; i++)    {        count += mBuckets[i].getCount();    }    return count;}template <class T>T Dictionary<T>::getData(string key){    int bin = hash(key);    return mBuckets[bin].getData(key);}template <class T>bool Dictionary<T>::insert(string key, T value){    int bin = hash(key);    mBuckets[bin].insert(key, value);    return true;}template <class T>bool Dictionary<T>::isEmpty(){    return getCount() == 0;}#endifBucket class:#ifndef _BUCKET_H_#define _BUCKET_H_#include <iostream>using namespace std;template <class T>class Bucket{private:    template <class T>    struct Node    {        string mKey;        T mData;        Node<T> *mNext, *mPrevious;        Node()        {            mKey = ;            mData = T();            mNext = NULL;            mPrevious = NULL;        }        Node(string key, T data)        {            mKey = key;            mData = data;            mNext = NULL;            mPrevious = NULL;        }    };    Node<T> *mHead, *mTail;    int mCount;public:    Bucket();    ~Bucket();    int getCount();    bool isEmpty();    bool isExist(string searchKey);    bool remove(string searchKey);    void display();    void insert(string key, T data);    T getData(string key);};// ********************************************************//                Constructor / Destructor// ********************************************************template <class T>Bucket<T>::Bucket(){    mHead = NULL;    mTail = NULL;    mCount = 0;}template <class T>Bucket<T>::~Bucket(){    Node<T> *tmp, *toBeDeleted;    tmp = mHead;    // removing node by node    while (tmp != NULL)    {        toBeDeleted = tmp;        tmp = tmp->mNext;        toBeDeleted->mNext = NULL;        delete toBeDeleted;    }    // reinitialize the pointers    mHead = NULL;    mTail = NULL;    mCount = 0;}// ********************************************************//                       Functions// ********************************************************template <class T>int Bucket<T>::getCount(){    return mCount;}template <class T>bool Bucket<T>::isEmpty(){    return mCount == 0;}template <class T>bool Bucket<T>::isExist(string searchKey){    Node<T> *tmp = mHead;    while (tmp != NULL)    {        if (tmp->mKey == searchKey)            return true;        tmp = tmp->mNext;    }    return false;}template <class T>bool Bucket<T>::remove(string searchKey){    Node<T> *tmp, *prev;    if (mHead == NULL)        return false;    else if (searchKey < mHead->mKey || searchKey > mTail->mKey)        return false;    tmp = mHead;    prev = NULL;    for (int i = 0; i < mCount; i++)    {        if (searchKey == tmp->mKey)            break;        prev = tmp;        tmp = tmp->mNext;    }    if (tmp != NULL)    {        if (tmp == mHead)        {            tmp = mHead;            mHead = mHead->mNext;            if (mHead == NULL)                mTail = NULL;            tmp->mNext = NULL;        }        else if (tmp == mTail)        {            prev->mNext = NULL;            mTail = prev;        }        else        {            prev->mNext = tmp->mNext;            tmp->mNext = NULL;        }        delete tmp;        mCount--;        return true;    }    return false;}template <class T>void Bucket<T>::display(){    Node<T> *tmp;    if (mHead == NULL)    {        cout << { }\n;        return;    }    cout << { ;    tmp = mHead;    while (tmp != NULL)    {        cout            << [            << tmp->mKey            << ,             << tmp->mData            << ]            << (tmp != mTail ? ,  :  });        tmp = tmp->mNext;    }    cout << \n;}template <class T>void Bucket<T>::insert(string key, T data){    Node<T> *tmp, *oneBefore, *newNode;    newNode = new Node<T>(key, data);    if (newNode == NULL)        return;    if (mHead == NULL)    {        mHead = newNode;        mTail = newNode;    }    else    {        if (key < mHead->mKey) // Put at head        {            newNode->mNext = mHead;            newNode->mPrevious = NULL;            mHead = newNode;        }        else if (key > mTail->mKey) // Put at tail        {            mTail->mNext = newNode;            newNode->mPrevious = mTail;            mTail = newNode;        }        else if (key == mHead->mKey || key == mTail->mKey) // Dont insert if already added        {            delete newNode;            return;        }        else        {            tmp = mHead;            oneBefore = mHead;            // Iterate through list to find position            while (tmp->mKey < key)            {                oneBefore = tmp;                tmp = tmp->mNext;            }            if (tmp->mKey != key)            {                newNode->mNext = tmp;                tmp->mPrevious = newNode;                oneBefore->mNext = newNode;                newNode->mPrevious = oneBefore;            }            else            {                delete newNode;                return;            }        }    }    mCount++;}template <class T>T Bucket<T>::getData(string key){    Node<T> *tmp = mHead;    while (tmp != NULL)    {        if (tmp->mKey == key)            return tmp->mData;        tmp = tmp->mNext;    }    return T();}#endifI've been testing the run times of my search function by loading pairs from a file with 398484 unique entries, all keys in alphabetical order. Here's a link to the file.I have a few other concerns, mainly, IS this a correct hash table implementation? Sounds weird, but I've never made a hash table before, so what I know about them is derived from many a Stack Overflow and Google link.The way it's currently implemented, my buckets can be however large they want, and the number of items per bucket averages out at around (numItems/numBuckets).The results of searching for keys at the beginning, middle, and end of the file:Search Key: aSearch key found. Search time: 2.82251898e-05 seconds.Key: aValue: 1411153Search Key: mesophylsSearch key found. Search time: 0.001279370876 seconds.Key: mesophylsValue: 1418758Search Key: zyzzyvasSearch key found. Search time: 0.001327610291 seconds.Key: zyzzyvasValue: 2223394
HashTable implementation in C++
c++;performance;hash table