Instantly share code, notes, and snippets.

@aozturk /HashMap.h
Last active Oct 22, 2018

Embed
What would you like to do?
Basic Hash Map (Hash Table) implementation in C++
// Hash map class template
template <typename K, typename V, typename F = KeyHash<K>>
class HashMap {
public:
HashMap() {
// construct zero initialized hash table of size
table = new HashNode<K, V> *[TABLE_SIZE]();
}
~HashMap() {
// destroy all buckets one by one
for (int i = 0; i < TABLE_SIZE; ++i) {
HashNode<K, V> *entry = table[i];
while (entry != NULL) {
HashNode<K, V> *prev = entry;
entry = entry->getNext();
delete prev;
}
table[i] = NULL;
}
// destroy the hash table
delete [] table;
}
bool get(const K &key, V &value) {
unsigned long hashValue = hashFunc(key);
HashNode<K, V> *entry = table[hashValue];
while (entry != NULL) {
if (entry->getKey() == key) {
value = entry->getValue();
return true;
}
entry = entry->getNext();
}
return false;
}
void put(const K &key, const V &value) {
unsigned long hashValue = hashFunc(key);
HashNode<K, V> *prev = NULL;
HashNode<K, V> *entry = table[hashValue];
while (entry != NULL && entry->getKey() != key) {
prev = entry;
entry = entry->getNext();
}
if (entry == NULL) {
entry = new HashNode<K, V>(key, value);
if (prev == NULL) {
// insert as first bucket
table[hashValue] = entry;
} else {
prev->setNext(entry);
}
} else {
// just update the value
entry->setValue(value);
}
}
void remove(const K &key) {
unsigned long hashValue = hashFunc(key);
HashNode<K, V> *prev = NULL;
HashNode<K, V> *entry = table[hashValue];
while (entry != NULL && entry->getKey() != key) {
prev = entry;
entry = entry->getNext();
}
if (entry == NULL) {
// key not found
return;
}
else {
if (prev == NULL) {
// remove first bucket of the list
table[hashValue] = entry->getNext();
} else {
prev->setNext(entry->getNext());
}
delete entry;
}
}
private:
// hash table
HashNode<K, V> **table;
F hashFunc;
};
@hershal

This comment has been minimized.

hershal commented Sep 30, 2015

Hey aozturk,

Your page has moved to here: https://medium.com/@aozturk/simple-hash-map-hash-table-implementation-in-c-931965904250

Cheers,

  • Hershal
@aozturk

This comment has been minimized.

Owner

aozturk commented Oct 8, 2015

Hi Hershal,
Brilliant catch :) Many thanks.

@jackwhit3

This comment has been minimized.

jackwhit3 commented Jan 2, 2016

Hi aozturk,

I was wondering how do you implement hashFunc?
Especially how to handle different types from template.

Many thanks.

@aozturk

This comment has been minimized.

Owner

aozturk commented Mar 6, 2016

Hi, thanks for asking.
The full project is here: HashMap project
and the related blog post of mine is here: blog post

@silvioraof

This comment has been minimized.

silvioraof commented Mar 27, 2017

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:

  1. typedef std::unordered_map<bitset<300>, Node> myHashmap;
  2. 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;

};

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment