Improving HashMap in C++

I have created a HashMap in C++. I would like help determining if it is good or bad.

I have not handled the errors or successes with messages. I have also not implemented the load factor in this map. As of now, once the size limit is reached, no more keys are accepted. I have written this code for just educational purpose only. I would like to know few things to make it better.

-
How can I implement the load factor concept? The hash function O/P is dependent on the previous table size. If we are to change the table size, the old ` pair will be lost.

-
How can I make this generic? i.e. instead of , is it possible to write a template code for both key and the value?

Implementing a hash function will not be a problem, since the hash function can be overloaded. What about the storage? In case of Java, the key and value will be treated as Object. Is there any option similar to that in C++?

-
Any other important (or mandatory) feature this map is missing?

``
#include
#include

using namespace std;

typedef struct Node {
string key;
int value;
struct Node * left;
struct Node * right;
}doubly;

class myHashStrKey{

private:
int currentCount;
int hashsize; // Default n = 2000. So 701 slots will be initialized.
vector table;

//hash function taken from net and modified.
size_t hash(const std::string data) {
size_t h(0);
for (int i=0; i> i) ^ data[i]);
}
h = h%hashsize;
return h;
}

//Inserts the key and value. If the key is already present, the value is updated.
//Checks if the currentCount = ((hashsize+1)*3))
return;
doubly * newNode = new doubly();
newNode->value = Value;
newNode->left = NULL;
newNode->right = NULL;
newNode->key = (Key);
*root = newNode;
myHashStrKey::currentCount++;
return;
}

doubly * prev = NULL;
doubly current = root;
while(current != NULL && ((current)->key).compare(Key)){
prev = current;
current = c

How to implement the load factor concept, because the hash function o/p is dependent on the previous table size. If we are to change the table size, the old ` pair will be lost.

You will need to rehash when the table size changes, removing the nodes from the old table and inserting them in their new locations in the new table. I would suggest that you remove the line h = h%hashsize; from the hash function, and apply the modulo operation when you're actually doing the table lookup, for two reasons:

• The hash function will no longer be dependent on the hash table, and can be made a static or non-member function

• You can store the raw hash value in the node, so you won't need to recalculate when you rehash.

How to make this generic ? i.e. instead of , is it possible to write a template code for both key and the value ?

You can make it generic by turning it into a class template, with template parameters to specify the key and value types:

template 
class MyHashMap
{
    struct Node
    {
        Key key;
        Value value;
        ...
    };
    ...
};

Then find where you're using string as a key type and replace it with Key; similarly, replace int as a value type with Value. You'll then need to make sure you're always using generic rather than type-specific operations on them. In particular, your (slightly odd) string comparisons will need to change from, for example, !(head->key).compare(key) to head->key == key - which is rather more readable anyway, in my opinion.

Finally, as you say, you'll need hash functions for each key type. The best way to support this is to move the hash function outside the class; then any user of the hash template can overload it for their own types.


Any other important (or mandatory )feature this map is missing ?

You do not have a destructor, so when the map is destroyed any memory allocated for the nodes will be lost. There are two choices here:

• Add a destructor to walk through all remaining nodes and delete them. Add a copy constructor and assignment operator (or declare them private), to prevent shallow copying leading to double deletion.

• Use a memory-managed container to store the nodes; remove the left and right pointers, and change the type of table from vector to vector >`. In my opinion, this would be the better option, as it removes the responsibility for memory management from your class.

StackExchange Code Review Q#892, answer score: 9