Author : Kumar K
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials
PART 2 (Hashmap and Hashset) :
In the previous part , we got introduced to the concept of Hashing .
We solved an interesting problem where in we used array as HashTable for our problem which solved the problem efficiently .
Here is the link to the previous part :
In this part , I want to introduce you to two containers which we can use as HashTables in our problems , namely HashSet and HashMap
Important points:-
0. We have two containers , namely HashSet and HashMap
1. Both containers can store elements inside them .
Introduction to HashSet :-
In C++ , HashSet is a simple container inside which you can store different data-types like strings and numbers . It supports an additional functionality , if you query(ask) say some element "b" exists in the HashSet or not, it can tell you the correct answer . If you insert the same number multiple times in the HashSet , it will have no effect . Similarly , you can remove elements from the HashSet too .
In C++,
[C++]unordered_set<int> b : On an average , each operation like insert , find and delete takes O(1) time on average . Worst Case can take O(N) time for each operation but it rarely occurs.
[C++]set<int> b : On an average , each operation like insert , find and delete takes O(logN) time on average . Worst Case will also take O(logN) time for each operation . Thats the advantage over unordered_set<int>b. All elements are stored in sorted order.
In Java, properties of HashSet is very similar to that of unordered_set in C++. It implements set interface which ensures no duplicate elements are present in hashset. The insertion of an object in hashset is based on its hash value, therefore when you iterate over hashset the order of elements that you'll get will most probably be different than how they were entered in the hashset. Hash value is the unique value of an object generated by a hash function to uniquely identify an object.
[Java]HashSet<Integer> set : Average time complexity for add, remove and look-up operation of HashSet is O(1). Worst case time complexity is O(N) which rarely occurs.
[Java]TreeSet<Integer> set : On an average , each operation like insert , find and delete takes O(logN) time on average . Worst Case will also take O(logN) time for each operation. Thats the advantage over HashSet<Integer> set. All elements are stored in sorted order.
In Python ,
there are two types of sets:
-
Set: It is an unordered collection of unique elements. In other words, it does not store duplicates.
-
SortedSet: It is a sorted collection of unique elements. In other words, it does not store duplicates and its elements are sorted in ascending order.
Note that the implementation of the Set and SortedSet interfaces in Python is different from their counterparts in Java. In Python, the Set is implemented using the built-in set() function, while the SortedSet is implemented using the built-in sorted() function.
To know in more detail for python ; read -> https://www.geeksforgeeks.org/internal-working-of-set-in-python/
-> https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/
That’s it!
Example :-
Say I give you a set of numbers : (2,3,3,5,2,5,5,5,5) . After inserting all these numbers in the HashSet , it will look like this :
Query input number : (2) - Does number 2 exists in the HashSet ? HashSet will say "Yes".
Query input number : (1) - Does number 1 exists in the HashSet ? HashSet will say "No".
Hell yea!
HashMap : It is very much same as HashSet , it can store elements like strings and numbers and answer the queries like HashSet . Elements can even be removed . The only difference is that , we can additionally even find the frequency of each element in the HashMap !!
Voila !!!!!!!!
It stores things in {key,value} format ..
In C++, unordered_map<int,int> b : On an average , each operation like insert , find and delete takes O(1) time on average . Worst Case can take O(N) time for each operation but it rarely occurs.
map<int,int> b : On an average , each operation like insert , find and delete takes O(logN) time on average . Worst Case will also take O(logN) time for each operation . Thats the advantage over unordered_map<int,int> b. All keys maintain sorted order.
In Java, HashMap<Integer, String> map : Average time complexity is O(1) and worst case time complexity is O(n). Similar to unordered_map in C++.
HashMap<Integer, Integer> a = new HashMap<>();
or
Map<Integer, Integer> a = new HashMap<>();
There are more type of maps like TreeMap, LinkedHashMap which have properties of map but are not much efficient as compared to hashmap because of the data structure implementing them.
For Java ; Tree Map ; read- >https://www.geeksforgeeks.org/treemap-in-java/
For Python ; Map is called as dictionary :->
https://www.geeksforgeeks.org/python-dictionary/
https://www.geeksforgeeks.org/python-sorted-containers-an-introduction/
That’s it!
Example :-
Say I give you a set of numbers : (2,3,3,5,2,5,5,5,5) . After inserting all these numbers in the HashMap , it will look like this :
Query input number : (2) - Does number 2 exists in the HashMap ? HashMap will say "Yes".
Query : (Frequency of 3??) - HashMap will say 2.
Query : (Frequency of 2??) - HashMap will say 2.
Query : (Frequency of 5??) - HashMap will say 5.
Hell yea! For further study : https://www.geeksforgeeks.org/set-vs-map-c-stl/
Code :
Java : Code
Python : https://ideone.com/DYrMJz
All Tutorials of Hashing are listed here : https://www.desiqna.in/tag/hashing_tutorials