patterncppMinor
Implementation of hash map
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.
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
Some positive things
- It leaks memory (every
newly allocatedNode) when the Hashmap leaves the scope.
- A delete/remove function is missing.
- It doesn't replace the value within the existing
Nodeon repeatedputs with the same key but instead adds an additionalNodeevery time.
- The size is fixed and therefore the hashmap
getquickly 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.