Improving HashMap in C++

I have created a HashMap<string,int> in C++. I would like you to take a look and say how good or bad it looks. I have not handled the errors and success 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.

1. 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 <key, value> pair will be lost.

2. How can I make this generic? i.e. instead of <string,int>, 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++?

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

#include <string>
#include <vector>

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<doubly *> table;

//hash function taken from net and modified.
size_t hash(const std::string data) {
    size_t h(0);
    for (int i=0; i<data.length(); i++){
        h = (h << (31-i) ^ (h >> 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
void insertNode(doubly ** root, int Value, const string Key){

    if(*root ==NULL){
        if(myHashStrKey::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 = current->right;
    }

    if(current ==NULL){
        if(myHashStrKey::currentCount >= ((hashsize+1)*3))
            return;
        doubly *newNode = new doubly();
        newNode->value = Value;
        newNode->key = Key;
        newNode->left = prev;
        newNode->right = NULL;
        prev->right = newNode;
        myHashStrKey::currentCount++;
    }
    else{
        (current)->value = Value;
    }
}

//Return the corresponding value for the given key from the table
int getNodeValue(doubly * root, string key){
    while(root != NULL){
        if(!key.compare(root->key)){
            return root->value;
        }
        root = root->right;
    }
    return -1;
}

//Removes the node from bucket if present and reduces the currentcount
//else nothing.
void removeNode(doubly ** root, string Key){
    doubly * toRemove;
    doubly * head = *root;

    //Check to see if the first element is the target.
    if((head != NULL) &&!(head->key).compare(Key)){
        toRemove = head;
        *root = head->right;
        if(head->right != NULL)
            head->right->left = NULL;
        delete toRemove;
        myHashStrKey::currentCount--;
        return;
    }
    //First element is not the target.
    else{
        if(head == NULL)
            return;

        while((head != NULL) &&(head->key).compare(Key)){
            head = head->right;
        }
        //Element not present. return
        if(head == NULL)
            return;

        //Element found. Remove the element and decrement currentCount.
        toRemove = head;

        head->left->right = head->right;
        if(head->right !=NULL)
            head->right->left = head->left;

        myHashStrKey::currentCount--;
        delete toRemove;
        return;
    }
}

public:
//Constructor for default size.
//I am considering that hash table size to have default value of 701.
//The average elements per bucket is 3.
//THe total allowed elements will be 701*3 i.e. tablesize*3.
myHashStrKey(){
    myHashStrKey::currentCount=0;
    myHashStrKey::hashsize = 701;
    myHashStrKey::table.insert(myHashStrKey::table.begin(),hashsize,((doubly *)NULL));
}

//Constructor for the user given size
//Hashsize is calculated to be size/3 +1 (average elements per bucket is 3)
myHashStrKey(int size){
    myHashStrKey::currentCount=0;
    myHashStrKey::hashsize = size/3 +1;
    myHashStrKey::table.insert(myHashStrKey::table.begin(),hashsize,((doubly *)NULL));
}


//Adds entry to the HashMap
void addKeyValue(const string &key,int value ){
    size_t keyHash = hash(key);
    insertNode(&(table[keyHash]), value, key);
}

//Gets the corresponding value for the key if present else nothing
int getValue(const string &key ){
    size_t keyHash = hash(key);
    int result = getNodeValue(table[keyHash],key);
    return result;
}

//Deletes the key if present else nothing.
void deleteKey(const string &key){
    size_t keyHash = hash(key);
    removeNode(&(table[keyHash]),key);
}
};