Java HashMaps:5 시작하기 위한 중요한 사항

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?
| | Github

비디오 참조:
해싱은 HashMaps, HashSets, HashTables 등을 공식화하는 데 도움이 되는 기술입니다.
해싱을 사용하면 O(1) 시간 복잡도에서 삽입 검색 및 삭제 작업을 수행할 수 있으므로 널리 사용됩니다.

ArrayList를 사용할 수 있지만 해시맵을 사용하면 약간의 주의가 필요합니다.

Java에서 해싱 구현-
우리는 java.util 라이브러리에 있는 HashSet을 사용할 것입니다.

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();
    }
}

고유한 요소 또는 두 배열의 합집합을 계산하거나 두 배열의 교차점을 찾아야 하는 문제가 있는 경우 순진한 접근 방식은 요소를 하나씩 반복하는 것입니다.

자바 해시맵

문제 1: 배열의 개별 요소 수 계산

a[]={5,10,5,4,5,10}
ANS=3
a[]={3,4,5}
ANS=3
a[]={5,5,5}
ans=1, 고유 요소는 5입니다.

순진한 솔루션은 요소의 반복(for 및 내부 for 루프)입니다. 요소가 더 일찍 존재하는 경우 카운트가 증가하지 않습니다. 고유한 요소가 있으면 개수를 늘리십시오. 그러나 HashSet을 사용하는 데 시간 복잡도는 O(n^2)이므로 O(n)으로 줄일 수 있습니다. 다음과 같이 구현할 수 있습니다.

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 ));

}
}

위의 경우 세트는 고유한 요소만 저장하므로 반복되는 값에 대해 false를 반환하므로 해시 세트의 크기는 고유한 요소의 값을 제공할 수 있습니다.

문제 2: 배열 합집합
두 개의 정렬되지 않은 배열을 결합하고 크기를 지정하십시오.
a[]= {5,10.15,5}
b[]={10,15,4}
순진한 솔루션은 배열 목록에 고유한 요소를 정렬하고 배치하고 그 요소를 계산하는 것입니다.

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();
}

문제 3: 배열의 교차

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;
}

요소 2의 세트에서 요소를 제거해야 합니다. 결국 요소를 두 번 세게 되고 원하지 않기 때문입니다.

문제 4: 크기가 k인 모든 창에서 개별 요소를 계산합니다.

a=[1,2,2,1,3,1,1,3]
k=4

문제 5: 문자열에서 고유한 문자 찾기

예 1:

입력: s = "리트코드"
출력: 0
예 2:

입력: s = "loveleetcode"
출력: 2
예 3:

입력: s = "aabb"
출력: -1

제약:

1 <= 길이 <= 105
s는 영문 소문자로만 구성됩니다.

// 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));
    }
}