11
\$\begingroup\$

I have created a HashMap<string,int> 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.

  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);
}
};
\$\endgroup\$
  • 5
    \$\begingroup\$ I suggest you look at the boost implementation of a TR1 unordered_map. \$\endgroup\$ – smithco Feb 21 '11 at 4:10
9
\$\begingroup\$

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 <key, value> 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 <string,int> , 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 <typename Key, typename Value>
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<Node*> to vector<vector<Node> >. In my opinion, this would be the better option, as it removes the responsibility for memory management from your class.
\$\endgroup\$
  • \$\begingroup\$ Thanks Mike. I have been thinking about the implementation details which you suggested. 1. If the implementation is going to be in vector<vector<node>>, where the first dimension will be my effective table and the second will act as the bucket. If this is the case, then how do I decide the place in the table i.e. the first dimension without doing 'h = h%hashsize;'. 2. Moving the hash function. I dont understand what you mean by "any user of the hash template can overload it ". I had initially thought of having overloaded hash function for all data type . Please clarify my doubts \$\endgroup\$ – bsoundra Feb 25 '11 at 21:45
  • \$\begingroup\$ 1. You calculate the table index as hash(key)%hashsize. You are still doing the modulo calculation, but not in the hash function itself; that means the hash function is independent of the hash table. \$\endgroup\$ – Mike Seymour Feb 28 '11 at 14:01
  • \$\begingroup\$ 2. You can (and should) overload the hash function for most, if not all, built-in and standard types. However, the user might define a different type (which you have no knowledge of) and want to use it as a hash key. By placing the hash function in the namespace outside your hash table, anyone can create overloads for their own types, and use them as keys in your template. By leaving it as a member, they are restricted to the types that you provide overloads for. \$\endgroup\$ – Mike Seymour Feb 28 '11 at 14:04
  • \$\begingroup\$ One more question though, instead of using the second dimension as a vector, would it help in performance if I used a List ??? I was thinking about the (1) for few days and this morning I got it and I logged in to say that and I see your comment :) . Now I got the (2) point . Thank you. \$\endgroup\$ – bsoundra Mar 2 '11 at 18:51
  • 1
    \$\begingroup\$ A vector will most likely be faster, as it will involve fewer memory allocations when adding and removing elements, and probably better cache behaviour when iterating through it. Since the order doesn't matter, you can add elements at the end, and remove one by swapping it with the last element, then removing it from the end. These are all constant-time operations, so a list wouldn't improve on that. \$\endgroup\$ – Mike Seymour Mar 3 '11 at 10:33
-1
\$\begingroup\$

Other features which may be convenient and are missing: isEmpty(), size(), addAll(), removeAll(), set view of the keys, subset views based on input key. Also even if it is not your primary concern the lookup time seems to be in logarithmic magnitude which can reduce its interest.

\$\endgroup\$
  • \$\begingroup\$ The lookup time isn't logarithmic; finding the bucket takes constant time, and finding the node within the bucket is linear in the bucket size (which should be small if the hash function is good and the map isn't too full). \$\endgroup\$ – Mike Seymour Mar 5 '11 at 12:20
  • \$\begingroup\$ Correct, went thru the code too quickly. \$\endgroup\$ – Y G Mar 7 '11 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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