If you liked this post do not forget to upvote !

Hello everyone. Today I want to explain my favorite data structures HASH TABLE and MAP which I use many times when I solve problems. I think HASH TABLE and MAP are one of most powerful data structures. Before solving particular problem I advice to think about two questions for a few minutes:

bool answer = is it possible to apply HASH TABLE or MAP ?;

if(answer == true){
	//Think: HOW YOU CAN APPLY ?
}

I always do this and it really helps me to find the fast and easy solution for a problem.

So, those who do not familiar with HASH TABLE and MAP may ask what are they and what are their implementations ?

HASH TABLE and MAP are the types of containers which store data with key-value combination. It means that particular data will have an special key and the value associated (mapped value) with this key.

<key, value> You may ask: That is it ? it just stores key and the value which is associated with this key ? Actually for being able to solve most problems yes that is what you need to know, but if you want to learn more about HASH TABLE and MAP in theory then do it, but for solving most of the problems knowing <key, value> combiantion is really enough.

So let's go further. I always code on C++ so I will show their C++ implementation. The implementation of HASH TABLE on C++ is unordered_map<> and the implementation of map on C++ is map<>.

Unordered_map<> and map<> work almost on the same principle, many similar functions but they have one main difference.

In unordered_map<> keys are not sorted and insertion of particular key takes O(1). In map<> keys are in sorted order and the insertion of particular key will take O(logn).

This means that if you need keys to be in sorted order then it is better to use map<>, otherwise use unordered_map<>.

So let's look how you can create one key-value pair:

unordered_map<int, int> q;
q[3]=7;

For map:
map<int, int> q;
q[3]=7;

As you can see for map<> we can do in the same way as for unordered_map<> and further I will show just in unordered_map<> cases as for map<> it will be the same things (maybe different double check on internet).

That is simple example where we created <3, 7> combination and this means that in our q the key=3 will have the value=7 associated with it and if we want to print that:

cout<<q[3]<<endl;

Output:7 As you saw there:

unordered_map<int, int> q; Key and value will have particular types and we can construct many combinations like that:

unordered_map<int, int> q1;
unordered_map<int, vector<int>> q2;
unordered_map<int, vector<vector<string>>> q3;
unordered_map<char, pair<int, char>> q4;
unordered_map<string, int> q5;
There a lot of combinations which we can apply but if you are not sure about particular combination then just search it on internet and if it is possible to contruct the combination of types which you want then it is great !

Let's look how we can insert other key and with its associated value:

unordered_map<int, int> q;

//1st way: q.insert(make_pair(3, 7));

//2nd way: q[3]=7;

//3rd way: q.emplace(3, 7); But what if the key already exists:

unordered_map<int, int> q; q[3]=7; cout<<q[3]<<endl;

q[3]=10; cout<<q[3]<<endl; ~~~~~

Output: 7
        10
As you can see the value has changed. If you want to save the values by one key then you can do in following way:

unordered_map<int, vector> q; q[3].push_back(7); q[3].push_back(10); //in vector there will be 7 and 10 as you saved values in vector Let's look how you can check does the particular key exists or not:

unordered_map<int, int> q; int ourkey=3;

//1st way: q.count(ourkey)>0;

//2nd way:
unordered_map<int, int>:: iterator z;
z=q.find(ourkey);
if(z == q.end()){
   cout<<"This key does not exists"<<endl; 
}
else{
    cout<<z->first<<" "<<z->second<<endl;
}

//and if you want to delete and remove that key with its value from q you can use:

//1st way:
q.erase(ourkey);   // deletion by key

//2nd way:
q.erase(z);      // deletion by iterator
The next thing how to traverse unordered_map<>:

unordered_map<int, int> q; for(int i=1;i<=3;i++){ q[i]=i+1; // construct pairs, I mean key-value combinations } ~~~~~

for(auto z=q.begin();z!=q.end();z++){ //traversing from beginning till end cout<<"key is "<first<<" and the value is "<second<<endl; }

for(auto z=q.rbegin();z!=q.rend();z++){ //traversing from end till beginning cout<<"key is "<first<<" and the value is "<second<<endl; } For more examples, functions and operations you can search from internet and look deeper to standard library and reference.

Let's consider how we can apply these in problem solving:

Imagine we have an array and want to find are there exist two numbers which sum are equal to target:

Solution:

class Solution {
public:
    bool twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> q;
        for(int i=0;i<nums.size();i++){
            if(q.count(nums[i])>0){
                q.at(nums[i])=q.at(nums[i])+1;         //my value is the frequncy of key
            }
            else{
                q.insert(make_pair(nums[i], 1));
            }
        }
        unordered_map<int, int>:: iterator z;
        for(z=q.begin();z!=q.end();z++){
            if(target%2==0 && target==z->first*2 && z->second>1){
			   return true;
            }
            else if(q.count(target-z->first)>0){
			   return true;
            }
        }
        return false;
    }
};

or you can rewrite this code like this:

class Solution {
public:
    bool twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> q;
        for(int i=0;i<nums.size();i++){
		      q[nums[i]]++;
        }
        for(auto z: q){
            if(target%2==0 && target==z.first*2 && z.second>1){
			   return true;
            }
            else if(q.count(target-z.first)>0){
			   return true;
            }
        }
        return false;
    }
};