Skip to content

Instantly share code, notes, and snippets.

@aozturk

aozturk/HashMap.h

Last active April 2, 2022 00:47
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save aozturk/2368896 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save aozturk/2368896 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. aozturk revised this gist Nov 6, 2013. 1 changed file with 0 additions and 2 deletions.
    2 changes: 0 additions & 2 deletions HashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -22,8 +22,6 @@ class HashMap {
    delete [] table;
    }



    bool get(const K &key, V &value) {
    unsigned long hashValue = hashFunc(key);
    HashNode<K, V> *entry = table[hashValue];
  2. aozturk renamed this gist Nov 6, 2013. 1 changed file with 0 additions and 51 deletions.
    51 changes: 0 additions & 51 deletions SimpleHashMap.h → HashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,54 +1,3 @@
    // Author: Abdullah Ozturk
    // Description: Simple Hash Map implementation in C++

    // Configurable table size constant
    const int TABLE_SIZE = 128;

    // Hash node class template
    template <typename K, typename V>
    class HashNode {
    public:
    HashNode(const K &key, const V &value) :
    key(key), value(value), next(NULL) {
    }

    K getKey() const {
    return key;
    }

    V getValue() const {
    return value;
    }

    void setValue(V value) {
    HashNode::value = value;
    }

    HashNode *getNext() const {
    return next;
    }

    void setNext(HashNode *next) {
    HashNode::next = next;
    }

    private:
    // key-value pair
    K key;
    V value;
    // next bucket
    HashNode *next;
    };

    // Default hash function class
    template <typename K>
    struct KeyHash {
    unsigned long operator()(const K& key) const
    {
    return reinterpret_cast<unsigned long>(key) % TABLE_SIZE;
    }
    };

    // Hash map class template
    template <typename K, typename V, typename F = KeyHash<K>>
    class HashMap {
  3. Abdullah Ozturk revised this gist Nov 6, 2013. 1 changed file with 60 additions and 45 deletions.
    105 changes: 60 additions & 45 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,25 +1,26 @@
    // Author: Abdullah Ozturk
    // Description: Very simple yet complete Hash Map implementation in C++
    // Description: Simple Hash Map implementation in C++

    // Configurable table size constant
    const int TABLE_SIZE = 128;

    // Hash node class
    // Hash node class template
    template <typename K, typename V>
    class HashNode {
    public:
    HashNode(int key, int value) :
    key(key), value(value), next(NULL) {
    HashNode(const K &key, const V &value) :
    key(key), value(value), next(NULL) {
    }

    int getKey() const {
    K getKey() const {
    return key;
    }

    int getValue() const {
    V getValue() const {
    return value;
    }

    void setValue(int value) {
    void setValue(V value) {
    HashNode::value = value;
    }

    @@ -32,91 +33,104 @@ class HashNode {
    }

    private:
    // Key-value pair
    int key;
    int value;
    // key-value pair
    K key;
    V value;
    // next bucket
    HashNode *next;
    };

    HashNode* next;
    // Default hash function class
    template <typename K>
    struct KeyHash {
    unsigned long operator()(const K& key) const
    {
    return reinterpret_cast<unsigned long>(key) % TABLE_SIZE;
    }
    };

    // Hash map class
    // Hash map class template
    template <typename K, typename V, typename F = KeyHash<K>>
    class HashMap {
    public:
    HashMap() {
    table = new HashNode*[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; ++i)
    table[i] = NULL;
    // 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* entry = table[i];
    HashNode<K, V> *entry = table[i];
    while (entry != NULL) {
    HashNode* prev = entry;
    HashNode<K, V> *prev = entry;
    entry = entry->getNext();
    delete prev;
    }
    table[i] = NULL;
    }

    // destroy the hash table
    delete [] table;
    }

    // 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];

    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) {
    return entry->getValue();
    value = entry->getValue();
    return true;
    }
    entry = entry->getNext();
    }
    return -1;
    return false;
    }

    void put(int key, int value) {
    int hash_val = HashFunc(key);
    HashNode* prev = NULL;
    HashNode* entry = table[hash_val];
    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(key, value);
    entry = new HashNode<K, V>(key, value);
    if (prev == NULL) {
    table[hash_val] = entry;
    // insert as first bucket
    table[hashValue] = entry;
    } else {
    prev->setNext(entry);
    }
    } else {
    // just update the value
    entry->setValue(value);
    }
    }

    void remove(int key) {
    int hash_val = HashFunc(key);
    HashNode* entry = table[hash_val];
    void remove(const K &key) {
    unsigned long hashValue = hashFunc(key);
    HashNode<K, V> *prev = NULL;
    HashNode<K, V> *entry = table[hashValue];

    HashNode* prev = NULL;
    while (entry != NULL) {
    if (entry->getKey() == key) {
    break;
    }
    while (entry != NULL && entry->getKey() != key) {
    prev = entry;
    entry = entry->getNext();
    }
    if (entry == NULL)

    if (entry == NULL) {
    // key not found
    return;
    }
    else {
    if (prev == NULL) {
    table[hash_val] = entry->getNext();
    // remove first bucket of the list
    table[hashValue] = entry->getNext();
    } else {
    prev->setNext(entry->getNext());
    }
    @@ -125,6 +139,7 @@ class HashMap {
    }

    private:
    // Hash table
    HashNode** table;
    // hash table
    HashNode<K, V> **table;
    F hashFunc;
    };
  4. Abdullah Ozturk revised this gist Nov 6, 2013. 1 changed file with 53 additions and 49 deletions.
    102 changes: 53 additions & 49 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    // Very simple yet complete Hash Map implementation in C++
    //
    // Author: Abdullah Ozturk
    // Description: Very simple yet complete Hash Map implementation in C++

    // Configurable table size constant
    const int TABLE_SIZE = 128;
    @@ -8,119 +8,123 @@ const int TABLE_SIZE = 128;
    class HashNode {
    public:
    HashNode(int key, int value) :
    _key(key), _value(value), _next(0) {
    key(key), value(value), next(NULL) {
    }

    int key() {
    return _key;
    int getKey() const {
    return key;
    }
    int value() {
    return _value;

    int getValue() const {
    return value;
    }
    HashNode* next() {
    return _next;

    void setValue(int value) {
    HashNode::value = value;
    }
    void set_value(int value) {
    _value = value;

    HashNode *getNext() const {
    return next;
    }
    void set_next(HashNode* next) {
    _next = next;

    void setNext(HashNode *next) {
    HashNode::next = next;
    }

    private:
    // Key-value pair
    int _key;
    int _value;
    int key;
    int value;

    HashNode* _next;
    HashNode* next;
    };

    // Hash map class
    class HashMap {
    public:
    HashMap() {
    _table = new HashNode*[TABLE_SIZE];
    table = new HashNode*[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; ++i)
    _table[i] = 0;
    table[i] = NULL;
    }
    ~HashMap() {
    for (int i = 0; i < TABLE_SIZE; ++i) {
    HashNode* entry = _table[i];
    while (entry != 0) {
    HashNode* entry = table[i];
    while (entry != NULL) {
    HashNode* prev = entry;
    entry = entry->next();
    entry = entry->getNext();
    delete prev;
    }
    }

    delete [] _table;
    delete [] table;
    }

    // Should be optimized according to specific needs
    int HashFunc(int key) {
    return key % TABLE_SIZE;
    }

    int Get(int key) {
    int get(int key) {
    int hash_val = HashFunc(key);
    HashNode* entry = _table[hash_val];
    HashNode* entry = table[hash_val];

    while (entry != 0) {
    if (entry->key() == key) {
    return entry->value();
    while (entry != NULL) {
    if (entry->getKey() == key) {
    return entry->getValue();
    }
    entry = entry->next();
    entry = entry->getNext();
    }
    return -1;
    }

    void Put(int key, int value) {
    void put(int key, int value) {
    int hash_val = HashFunc(key);
    HashNode* prev = 0;
    HashNode* entry = _table[hash_val];
    HashNode* prev = NULL;
    HashNode* entry = table[hash_val];

    while (entry != 0 && entry->key() != key) {
    while (entry != NULL && entry->getKey() != key) {
    prev = entry;
    entry = entry->next();
    entry = entry->getNext();
    }

    if (entry == 0) {
    if (entry == NULL) {
    entry = new HashNode(key, value);
    if (prev == 0) {
    _table[hash_val] = entry;
    if (prev == NULL) {
    table[hash_val] = entry;
    } else {
    prev->set_next(entry);
    prev->setNext(entry);
    }
    } else {
    entry->set_value(value);
    entry->setValue(value);
    }
    }

    void Remove(int key) {
    void remove(int key) {
    int hash_val = HashFunc(key);
    HashNode* entry = _table[hash_val];
    HashNode* entry = table[hash_val];

    HashNode* prev = 0;
    while (entry != 0) {
    if (entry->key() == key) {
    HashNode* prev = NULL;
    while (entry != NULL) {
    if (entry->getKey() == key) {
    break;
    }
    prev = entry;
    entry = entry->next();
    entry = entry->getNext();
    }
    if (entry == 0)
    if (entry == NULL)
    return;
    else {
    if (prev == 0) {
    _table[hash_val] = entry->next();
    if (prev == NULL) {
    table[hash_val] = entry->getNext();
    } else {
    prev->set_next(entry->next());
    prev->setNext(entry->getNext());
    }
    delete entry;
    }
    }

    private:
    // Hash table
    HashNode** _table;
    HashNode** table;
    };
  5. aozturk revised this gist Aug 11, 2013. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -52,6 +52,8 @@ class HashMap {
    delete prev;
    }
    }

    delete [] _table;
    }

    // Should be optimized according to specific needs
  6. aozturk revised this gist Apr 12, 2012. 1 changed file with 3 additions and 0 deletions.
    3 changes: 3 additions & 0 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,6 @@
    // Very simple yet complete Hash Map implementation in C++
    //

    // Configurable table size constant
    const int TABLE_SIZE = 128;

  7. aozturk revised this gist Apr 12, 2012. 1 changed file with 96 additions and 96 deletions.
    192 changes: 96 additions & 96 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -4,118 +4,118 @@ const int TABLE_SIZE = 128;
    // Hash node class
    class HashNode {
    public:
    HashNode(int key, int value) :
    _key(key), _value(value), _next(0) {
    }
    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;
    }
    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;
    // Key-value pair
    int _key;
    int _value;

    HashNode* _next;
    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;
    }
    }
    }
    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;
    }
    // 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];
    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;
    }
    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];
    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();
    }
    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);
    }
    }
    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];
    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;
    }
    }
    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;
    };
    // Hash table
    HashNode** _table;
    };
  8. aozturk created this gist Apr 12, 2012.
    121 changes: 121 additions & 0 deletions SimpleHashMap.h
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,121 @@
    // 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;
    };