Leetcode List: https://leetcode.com/list/504wrexe

So in this chapter, we would be learning about HASH TABLE and MAP data structures 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 WE 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>

We might think: 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 we need to know, but if we want to learn more about HASH TABLE and MAP in theory then do it, but for solving most of the problems knowing <key, value> combination is really enough.

So let's go further. 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 we need keys to be in sorted order then it is better to use map<>, otherwise use unordered_map<>.

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

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

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

As we 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