7
\$\begingroup\$

I was asked to implement a hash map in this phone interview (screen-share), so time was limited and this is what I came up with. I'd appreciate if someone can take a minute to critique/review it and help me improve.

Here is an online version of the code.

#include <list>
#include <iostream>
using namespace std;

const int SIZE = 10;

class Node{
public:
    Node(){}
    Node(int k, int v):key(k), value(v){}
    int key, value;
};

class HashMap {
private:
    list<Node*> data[SIZE];

public:
    ~HashMap();
    Node* get(int key);
    void put(int key, int value);

    int hashFn(int val){ return val % 13; }
};

Node* HashMap::get(int key){
    int hashValue = hashFn(key);
    int bucket = hashValue % SIZE;
    list<Node*>::iterator it = data[bucket].begin();

    while(it != data[bucket].end()){

        Node ** d = &(*it); 
        if((*d)->key == key){
            return *d;
        }

        it++;
    }
    return NULL;
}

void HashMap::put(int key, int value){
    int hashValue = hashFn(key);
    int bucket = hashValue % SIZE;
    Node* node = this->get(key);
    if(node == NULL){
        data[bucket].push_front(new Node(key, value));
    }
    else{
        node->value = value;
    }
}

HashMap::~HashMap(){
    for(int i = 0; i < SIZE; ++i){
        list<Node*>& val = data[i];
        for(list<Node*>::iterator it = val.begin(); it != val.end(); it++){
            Node* n = *it;
            delete n;
        }
    }
}

int main(){
    HashMap map;
    cout << "Finding 5: " << map.get(5) << endl;  // -1
    map.put(5, 10);
    map.put(5, 11);
    cout << "Finding 5: " << map.get(5)->value;  // 11
    return 1;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ A destructor is not enough. You have forgotten the rule of three. \$\endgroup\$ – Martin York Aug 10 '12 at 10:14
  • \$\begingroup\$ Well, as I mentioned this was a part of telephonic interview and the focus here was on implementing get() and put(). However, I do agree with you and this definitely lacks the rule of three! \$\endgroup\$ – brainydexter Aug 10 '12 at 10:39
  • \$\begingroup\$ You have not declared the destructor in the class body. \$\endgroup\$ – Anton Golov Aug 10 '12 at 11:09
  • \$\begingroup\$ Yea, I posted the code on Mat's request. Forgot to update both the places. \$\endgroup\$ – brainydexter Aug 10 '12 at 11:16
  • \$\begingroup\$ Probably I should have also implemented the rules of three for the interviewer. \$\endgroup\$ – brainydexter Aug 10 '12 at 11:17
4
\$\begingroup\$

Some obvious problems

  1. It leaks memory (every newly allocated Node) when the Hashmap leaves the scope.
  2. A delete/remove function is missing.
  3. It doesn't replace the value within the existing Node on repeated puts with the same key but instead adds an additional Node every time.
  4. The size is fixed and therefore the hashmap get quickly degenerates into linked list search.
  5. Key and value types aren't generic.

Some positive things

  • It implements a hashmap
  • uses hash-lookup for search
  • returns correct results
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 1. when hashmap leaves the scope, destructor would be called upon its members, aka list and when it gets destroyed, it would call the destructor on its members and hence it won't be a memory leak ? \$\endgroup\$ – brainydexter Aug 10 '12 at 4:44
  • \$\begingroup\$ 3. In fact it does replace the value. I see if a node exists in the map, I return that instead and modify the value of that node. \$\endgroup\$ – brainydexter Aug 10 '12 at 4:45
  • \$\begingroup\$ 4. Yes, size is fixed, but a lot depends on the hashFunction to distribute the elements properly. What I wrote was a dummy function. \$\endgroup\$ – brainydexter Aug 10 '12 at 4:46
  • \$\begingroup\$ @brainydexter: For 1., no. The destructor for a List<T*> (or any other standard container) doesn't call delete on the pointers it contains. \$\endgroup\$ – Mat Aug 10 '12 at 5:02
  • \$\begingroup\$ @Mat Added destructor code also. \$\endgroup\$ – brainydexter Aug 10 '12 at 9:15
3
\$\begingroup\$

The first two things I noticed:

  1. Drop the pointers. They give you no advantage. Use value objects.
  2. Drop the linked list. It’s sluggishly slow. I have no idea why hash maps collision resolution, when taught in class, always mentions lists – probably because it makes the asymptotic runtime analysis easier. They are almost always slower.

Dropping pointers has the nice effect of plugging the leaks and making the code easier – in particular, the rule of three is then trivially satisfied – and more efficient.

Then, since Node is just an aggregate, I’d use std::pair.

For a real implementation, hashFn shouldn’t be a function inside the hash map, it should be a user-supplied function, depending on the type of data (potentially even if the type is not generic, since different data has different characteristics). But a real implementation also would need to be resizable and configurable by load factor.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$
int hashValue = hashFn(key);
int bucket = hashValue % SIZE;

I'd suggest having a bucket(key) function that returns the bucket rather then repeating this piece of code. I'd also create a Bucket class to handle the per-bucket logic. Then your get function would look like:

Node * HashMap::get(int key)
{
    return bucket(key).get(key);
}

Of course, Bucket::get would have more complicated logic than here, but I think it would simplify your code overall.

    Node ** d = &(*it); 

Its not clear this helps over using the iterator directly in the following lines.

list<Node*>::iterator it = data[bucket].begin();

while(it != data[bucket].end()){

Why not use a standard for loop here?

list<Node*> data[SIZE];

Linked lists are almost always the wrong choice. There are slower for every case except inserting/deleting in the middle. You don't use that here, so you should probably use a vector not a list.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ I agree with creating a bucket function but not quite sure if I understood making a Bucket class ? As for using a while loop over for loop, there was no particular reason, just a style of accessing iterators I prefer. And, though I agree with your suggestion of vector<Node*> data, but I also think, whenever we do a lookup based on a key, we have to loop through each element to find it and hence O(n) time. Similarly for insert, I am just inserting this at the beginning which is O(1), so I am not sure how would a vector be better in this case ? \$\endgroup\$ – brainydexter Aug 10 '12 at 18:08
  • \$\begingroup\$ If I were to store elements in a sorted manner, I could use binary search on the vector to reduce lookup time to O(lg n) from O(n) where n is the size of vector. This would increase the insertion time though. Inserting element in a sorted array would take O(n) time. So am not sure if we are actually gaining that much \$\endgroup\$ – brainydexter Aug 10 '12 at 18:11
  • 1
    \$\begingroup\$ @brainydexter, A Bucket Class would hold your list<> of Nodes and provide get and set methods just for items which fit into that list. \$\endgroup\$ – Winston Ewert Aug 10 '12 at 18:26
  • 1
    \$\begingroup\$ @brainydexter, lookup on a vector and list will both be O(n), but vector has a smaller O(n). A vector just to move forward in memory to iterate, but a list has to read a pointer and jump to a completely different memory location. \$\endgroup\$ – Winston Ewert Aug 10 '12 at 18:27
  • 1
    \$\begingroup\$ @brainydexter, both list and vectors keep track of the location of the last element, so both have O(1) insert at the end. You aren't gaining anything by inserting at the beginning. I'm not exactly sure how the insertion time itself compares between the two methods. Inserting a vector is usually faster, because there is less to do, but if it runs out of capacity it can be more expensive. \$\endgroup\$ – Winston Ewert Aug 10 '12 at 18:29

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.