What is Hashing and What are Java HashMaps?
When to use Java HashMaps?
Application of HashMaps in DSA Problems?
How to Implement Java HashMaps?
Some Popular problems and how to optimize them with HashMaps?
Twitter | Linkedin | Github
video Reference: Hashing Challenge by Anuj
Hashing is the technique which helps to formulate the HashMaps, HashSets, HashTables etc.
using hashing we can do Insert search and delete operation in O(1) time complexity, that is why it is used widely.
We could use an ArrayList, but hashmaps allows us some calrity
Implementation of Hashing in Java-
we will use a HashSet, that is found in java.util library.
package JavaDSA1;
import java.util.*;
class HashSet{
public static void main(String[] args) {
HashSet<Integer> s= new HashSet<>();
s.add(5);
s.add(10);
System.out.println(s);
if(s.contains(10)){
System.out.println("present");
}
else{
System.out.println("not present");
}
s.remove(10);
System.out.println(s.size());
System.out.println(s.isEmpty());
//returns empty if the array is empty
s.clear();
}
}
The problems having where we have to count the distinct elements or union of two arrays or find the intersection of the two arrays, in that cases naive approach is to do iteration of elements one by one.
Java HashMaps
Problem 1: Count distinct Elements in the array
a[]={5,10,5,4,5,10}
ans=3
a[]={3,4,5}
ans=3
a[]={5,5,5}
ans=1, distinct element is 5
naive solution is iteration(for and inner for loop) of elements, if elements is present earlier count do not increase count; if distinct element is present then increase count.but time complexity will be O(n^2) to using HashSet it can be reduced to O(n). which can be implemented as follows-
package javaDSA2;
import java.util.*;
class DistinctElements{
static int countDistinct(int arr[], int n)
HashSet<Integer> s= new HashSet<>();
for(int i=0; i<n; i++){
set.add(arr[i]);
}
return set.size();
}
public static void main(String[] args) {
int arr[]= new int{6,10, 5,4,9, 120,4,6,10};
system.out.println(countDistinct(arr, arr.length ));
}
}
In the above case set only store distinct element so it will return false on the repeated value, so size of the hashset can give the value of unique elements in them.
Problem 2: union of the array
join two unsorted arrays and give the size.
a[]= {5,10.15,5}
b[]={10,15,4}
naive solution is to sort and put distinct element in a array list and count the elements in that.
int unionArray(int a[], int b[]){
set <Integer> set = new HashSet<>();
for(int it:a){
set.add(it)
}
for (int it:b){
set add(it);
}
return set.size();
}
problem 3: Intersection of Array
int intersect (int a[], int b[]){
Set<Integer> set = new Hashset<>();
int count=0;
for(int it:a){
set.add(it);
}
for (int it:b){
if(set.contains(it)){
count ++;
set.remove(it);
}
return count;
}
Make sure to remove the element from the set from element 2,as we end up counting the element twice and we do not want that.
Problem 4: count the distinct elements in every window of size k
a=[1,2,2,1,3,1,1,3]
k=4
Problem 5: finding unique characters in a string
Example 1:
Input: s = "leetcode"
Output: 0
Example 2:
Input: s = "loveleetcode"
Output: 2
Example 3:
Input: s = "aabb"
Output: -1
Constraints:
1 <= s.length <= 105
s consists of only lowercase English letters.
// Java program to find first
// non-repeating character
// Note : hashmap is used
import java.util.*;
class CountIndex {
int count, index;
// constructor for first occurrence
public CountIndex(int index)
{
this.count = 1;
this.index = index;
}
// method for updating count
public void incCount()
{
this.count++;
}
}
class GFG {
static final int NO_OF_CHARS = 256;
static HashMap<Character, CountIndex> hm
= new HashMap<Character, CountIndex>(NO_OF_CHARS);
/* calculate count of characters
in the passed string */
static void getCharCountArray(String str)
{
for (int i = 0; i < str.length(); i++) {
// If character already occurred,
if (hm.containsKey(str.charAt(i))) {
// updating count
hm.get(str.charAt(i)).incCount();
}
// If it's first occurrence, then store
// the index and count = 1
else {
hm.put(str.charAt(i), new CountIndex(i));
}
}
}
/* The method returns index of first non-repeating
character in a string. If all characters are repeating
then returns -1 */
static int firstNonRepeating(String str)
{
getCharCountArray(str);
int result = Integer.MAX_VALUE, i;
for (Map.Entry<Character, CountIndex> entry : hm.entrySet())
{
int c=entry.getValue().count;
int ind=entry.getValue().index;
if(c==1 && ind < result)
{
result=ind;
}
}
return result;
}
// Driver method
public static void main(String[] args)
{
String str = "geeksforgeeks";
int index = firstNonRepeating(str);
System.out.println(
index == Integer.MAX_VALUE
? "Either all characters are repeating "
+ " or string is empty"
: "First non-repeating character is "
+ str.charAt(index));
}
}
Top comments (0)