-
-
Save aozturk/2368896 to your computer and use it in GitHub Desktop.
| // Very simple yet complete Hash Map implementation in C++ | |
| // | |
| // Configurable table size constant | |
| const int TABLE_SIZE = 128; | |
| // Hash node class | |
| class HashNode { | |
| public: | |
| HashNode(int key, int value) : | |
| _key(key), _value(value), _next(0) { | |
| } | |
| int key() { | |
| return _key; | |
| } | |
| int value() { | |
| return _value; | |
| } | |
| HashNode* next() { | |
| return _next; | |
| } | |
| void set_value(int value) { | |
| _value = value; | |
| } | |
| void set_next(HashNode* next) { | |
| _next = next; | |
| } | |
| private: | |
| // Key-value pair | |
| int _key; | |
| int _value; | |
| HashNode* _next; | |
| }; | |
| // Hash map class | |
| class HashMap { | |
| public: | |
| HashMap() { | |
| _table = new HashNode*[TABLE_SIZE]; | |
| for (int i = 0; i < TABLE_SIZE; ++i) | |
| _table[i] = 0; | |
| } | |
| ~HashMap() { | |
| for (int i = 0; i < TABLE_SIZE; ++i) { | |
| HashNode* entry = _table[i]; | |
| while (entry != 0) { | |
| HashNode* prev = entry; | |
| entry = entry->next(); | |
| delete prev; | |
| } | |
| } | |
| } | |
| // Should be optimized according to specific needs | |
| int HashFunc(int key) { | |
| return key % TABLE_SIZE; | |
| } | |
| int Get(int key) { | |
| int hash_val = HashFunc(key); | |
| HashNode* entry = _table[hash_val]; | |
| while (entry != 0) { | |
| if (entry->key() == key) { | |
| return entry->value(); | |
| } | |
| entry = entry->next(); | |
| } | |
| return -1; | |
| } | |
| void Put(int key, int value) { | |
| int hash_val = HashFunc(key); | |
| HashNode* prev = 0; | |
| HashNode* entry = _table[hash_val]; | |
| while (entry != 0 && entry->key() != key) { | |
| prev = entry; | |
| entry = entry->next(); | |
| } | |
| if (entry == 0) { | |
| entry = new HashNode(key, value); | |
| if (prev == 0) { | |
| _table[hash_val] = entry; | |
| } else { | |
| prev->set_next(entry); | |
| } | |
| } else { | |
| entry->set_value(value); | |
| } | |
| } | |
| void Remove(int key) { | |
| int hash_val = HashFunc(key); | |
| HashNode* entry = _table[hash_val]; | |
| HashNode* prev = 0; | |
| while (entry != 0) { | |
| if (entry->key() == key) { | |
| break; | |
| } | |
| prev = entry; | |
| entry = entry->next(); | |
| } | |
| if (entry == 0) | |
| return; | |
| else { | |
| if (prev == 0) { | |
| _table[hash_val] = entry->next(); | |
| } else { | |
| prev->set_next(entry->next()); | |
| } | |
| delete entry; | |
| } | |
| } | |
| private: | |
| // Hash table | |
| HashNode** _table; | |
| }; |
Hi Hershal,
Brilliant catch :) Many thanks.
Hi aozturk,
I was wondering how do you implement hashFunc?
Especially how to handle different types from template.
Many thanks.
Hi, thanks for asking.
The full project is here: HashMap project
and the related blog post of mine is here: blog post
Hi aozturk,
Excellent post and example.
But I actually tried to make a hash_func with with my Class using this and boos unordered_map, and I've waste days.
I think will not be so difficult for you as it is for me. But I don´t know how to start. Thank you for help.
I know I need a hash_func but don´t know with ou without the Node, or just the bitset.
I need something like this:
- typedef std::unordered_map<bitset<300>, Node> myHashmap;
- typedef std::unordered_map<int, myHashmap > myHashMap;
My class Node is like this:
class Node
{
public:
Node() { id = 0;}
virtual ~Node() {}
int getId(){return id;}
void setId(int id){this->id = id;}
bool operator==(const Node& node) const
{
return (id == node.id);
}
Node& operator=(const Node& node)
{
id = node.id;
return *this;
}
Node operator=(const Node &n)
{
id = n.id;
}
protected:
private:
int id;
};
Hey aozturk,
Your page has moved to here: https://medium.com/@aozturk/simple-hash-map-hash-table-implementation-in-c-931965904250
Cheers,