Thursday, 21 July 2016

Explain hash_map and bucketing with examples


A small introduction to the hash map:

The template class describes an object that controls a varying-length sequence of elements that has bidirectional access. You use the container hash_map to manage a sequence of elements as a hash table, each table entry storing a bidirectional linked list of nodes, and each node storing one element.

Syntax of the hash map is:
Microsoft::VisualC::StlClr::GenericPair

Here the parameters are explained as shown below. Key - The type of the key component of an element in the controlled sequence.Mapped- The type of the additional component of an element in the controlled sequence.

In the above syntax an element consists of a key, for ordering the sequence, and a mapped value, which goes along for the ride.


Example for the Hash map: 

 /* Hash map template class*/
template >
class Example_HashMap {
 
    // hash Hash_Tbl_Node
   HashNode **Hash_Tbl_Node;
   Fun Hash_Fun;
public:
    Example_HashMap() {
        // construct zero initialized hash Hash_Tbl_Node of size
        Hash_Tbl_Node = new HashNode *[TABLE_SIZE]();
    }

    ~Example_HashMap() {
        // destroy all buckets one by one
        for (int i = 0; i < TABLE_SIZE; ++i) {
            HashNode *Hash_Entry_new = Hash_Tbl_Node[i];
            while (Hash_Entry_new != NULL) {
                HashNode *prev = Hash_Entry_new;
                Hash_Entry_new = Hash_Entry_new->getNext();
                delete prev;
            }
            Hash_Tbl_Node[i] = NULL;
        }
        // destroy the hash Hash_Tbl_Node
        delete [] Hash_Tbl_Node;
    }

    bool Get_Hash(const Key &key, Val &value) {
        unsigned long hashValue = Hash_Fun(key);
        HashNode *Hash_Entry_new = Hash_Tbl_Node[hashValue];

        while (Hash_Entry_new != NULL) {
            if (Hash_Entry_new->getKey() == key) {
                value = Hash_Entry_new->getValue();
                return true;
            }
            Hash_Entry_new = Hash_Entry_new->getNext();
        }
        return false;
    }

    void put(const Key &key, const Val &value) {
        unsigned long hashValue = Hash_Fun(key);
        HashNode *prev = NULL;
        HashNode *Hash_Entry_new = Hash_Tbl_Node[hashValue];

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

        if (Hash_Entry_new == NULL) {
            Hash_Entry_new = new HashNode(key, value);
            if (prev == NULL) {
                // insert as first bucket
                Hash_Tbl_Node[hashValue] = Hash_Entry_new;
            } else {
                prev->setNext(Hash_Entry_new);
            }
        } else {
            // just update the value
            Hash_Entry_new->setValue(value);
        }
    }

    void remove(const Key &key) {
        unsigned long hashValue = Hash_Fun(key);
        HashNode *prev = NULL;
        HashNode *Hash_Entry_new = Hash_Tbl_Node[hashValue];

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

        if (Hash_Entry_new == NULL) {
            // key not found
            return;
        }
        else {
            if (prev == NULL) {
                // remove first bucket of the list
                Hash_Tbl_Node[hashValue] = Hash_Entry_new->getNext();
            } else {
                prev->setNext(Hash_Entry_new->getNext());
            }
            delete Hash_Entry_new;
        }
    }
};


Small introduction to the Map::bucket:
size_type bucket ( const key_type& k ) const;

How to locate element's bucket? Returns the bucket number where the element with key k is located. The bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value of their key.

As like array the Buckets are numbered from 0 to (bucket_count-1). Using iterators we can access the elements in the bucket, see the sample code that helps us the usage of the buckets as iterators.
// unordered_map::bucket
#include 
#include 
#include 

int main ()
{
  std::unordered_map Ex_Map = {
    {"fruit","Apple"},
    {"Flower","Rose"},
    {"Animal","DOG"},
    {"Bird","DOVE"}
  };

  for (auto& elm_Key: Ex_Map) {
    std::cout << "Element [" << elm_Key.first << ":" << elm_Key.second << "]";
    std::cout << " is in bucket #" << Ex_Map.bucket (elm_Key.first) << std::endl;
  }

  return 0;
}

No comments: