HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

Implementation of hash map

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationmaphash

Problem

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 
#include 
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 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::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 & val = data[i];
        for(list::iterator it = val.begin(); it != val.end(); it++){
            Node* n = *it;
            delete n;
        }
    }
}

int main(){
    HashMap map;
    cout value;  // 11
    return 1;
}

Solution

Some obvious problems

  • It leaks memory (every newly allocated Node) when the Hashmap leaves the scope.



  • A delete/remove function is missing.



  • 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.



  • The size is fixed and therefore the hashmap get quickly degenerates into linked list search.



  • Key and value types aren't generic.



Some positive things

  • It implements a hashmap



  • uses hash-lookup for search



  • returns correct results

Context

StackExchange Code Review Q#14498, answer score: 4

Revisions (0)

No revisions yet.