자바 자료구조4 -HashMap과 HashSet-

1. HashMap

 

해싱을 기반으로 데이터들을 관리해주는 자료구조

 

파이썬에서 dict와 대응된다

 

HashMap은 (key,value) 쌍 형태로 들어가 있어서, key와 그 key에 따른 value값을 동시에 저장하는 형태

 

따라서 HashMap의 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도는 O(1)이다.

 

HashMap은 TreeMap보다 속도가 빠르며, 값 자체에만 관심이 있지, 그 순서에는 관심이 없는 자료구조

 

HashMap 사용을 위해서

 

import java.util.HashMap;

 

HashMap<K,V> (name) = new HashMap<>(); 형태의 선언이 필요하다.

 

K,V는 key와 value에 해당하는 타입이다.

 

import java.util.HashMap;

public class Main {
    public static void main(String[] args){
        HashMap<Integer, Integer> m;
    }
}

 

 

Key는 문자열도 가능하다

 

HashMap<String, Integer>로 선언하면 가능

 

import java.util.HashMap;

public class Main {
    public static void main(String[] args){
        HashMap<String, Integer> m = new HashMap<>();
        
        m.put("banana", 6);
        
        m.put("helloworld", 2);
        
        m.put("apple", 5);
        
        //key가 banana인 쌍의 value 출력
        System.out.println(m.get("banana"));
    }
}

 

 

 

2. HashMap 핵심 메소드

 

2-1) put(K,V)

 

HashMap에 (K,V)쌍을 추가

 

이미 K가 존재한다면, K에 대응하는 value를 V로 변경

 

2-2) remove(K)

 

HashMap에 들어있는 데이터 중 key가 K인 쌍을 찾아 제거

 

2-3) get(K)

 

현재 HashMap에 key가 K인 쌍을 찾아 값 V를 반환

 

해당하는 쌍이 없다면 에러 발생하므로 (hashmap).containsKey(K)가 true인 경우에만 사용해야한다.

 

혹은 getOrDefault(K,D) 함수는 K에 해당하는 key가 없으면 값 D를 기본값으로 제공

 

import java.util.HashMap;

public class Main {
    public static void main(String[] args){
    
    //정수를 관리할 hashmap 선언
        HashMap<Integer, Integer> m = new HashMap<>();
        
        m.put(5,6);
        m.put(2,2);
        m.put(10,1);
        
        //key가 2인 쌍이 hashmap에 있다면..
        //key가 2인 value값을 출력
        if(m.containsKey(2)){
            System.out.println(m.get(2));
        }
        
        //key가 5인 쌍을 제거
        m.remove(5);
        
        //key가 5인 쌍이 hashmap에 없다면...
        if(!m.containsKey(5)){
            System.out.println("not exists!");
        }
        
        //key가 2인 곳에 들어있는 value를 10으로 변경
        m.put(2,10);
        
        //key가 2인 value 10 출력
        System.out.println(m.get(2));
    }
}

 

여기서 보면 알 수 있는데 put은 이미 있는 key이면 value를 새로 들어온 값으로 덮어 씌운다

 

 

3. 연습문제1

 

• add k v : (k, v) 쌍을 hashmap에 추가합니다. key가 k, value가 v라는 뜻입니다. 이때 만약 동일한 k가 이미 존재한다면, v로 덮어씁니다.
• remove k : key가 k인 쌍을 찾아 hashmap에서 제거합니다. 잘못된 입력은 주어지지 않습니다.
• find k : key가 k인 쌍이 hashmap에 있는지를 판단합니다. 있다면 해당하는 value를 출력하고, 없다면 None을 출력합니다.

 

import java.util.HashMap;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        HashMap<Integer,Integer> m = new HashMap<>();

        for(int i = 0; i < n; i++){

            String q = sc.next();

            if(q.equals("add")){
                int k = sc.nextInt();
                int v = sc.nextInt();

                m.put(k,v);
            } else if(q.equals("remove")){

                int k = sc.nextInt();

                m.remove(k);
            } else {

                int k = sc.nextInt();

                if(m.containsKey(k) == true){
                    System.out.println(m.get(k));
                } else {
                    System.out.println("None");
                }
            }
        }
    }
}

 

 

4. HashSet

 

해싱을 기반으로 데이터들을 관리해주는 자료구조

 

삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 O(1)

 

파이썬에서 set에 대응된다. 그러니까 중복된 원소를 제거할 수 있겠네

 

TreeSet보다 속도가 빠르지만, 값의 존재 여부에만 관심이 있지, 그 순서에는 전혀 관심이 없는 자료구조이다.

 

사용하기 위해서는

 

import java.util.HashSet;

 

HashSet<(type)> (name) = new HashSet<>(); 형태의 선언이 필요

 

import java.util.HashSet;

public class Main {
    public static void main(String[] args){
        HashSet<Integer> s = new HashSet<>();
    }
}

 

 

5. HashSet 핵심 메소드

 

5-1) add(E)

 

데이터 E를 추가

 

5-2) remove(E)

 

현재 hashset에 들어있는 데이터 중 숫자 E를 찾아 제거

 

5-3) contains(E)

 

숫자 E가 들어있는지 찾고, 있으면 true, 없으면 false를 반환

 

import java.util.HashSet;

public class Main {
    public static void main(String[] args){
        
        //정수를 관리할 hashset을 선언(빈 set)
        HashSet<Integer> s = new HashSet<>();
        
        //3,9,5를 넣고
        s.add(3);
        s.add(9);
        s.add(5);
        
        //숫자 3이 set에 있다면...
        if(s.contains(3)){
            System.out.println("exists!");
        }
        
        //숫자 9를 제거
        s.remove(9);
        
        //숫자 9가 없다면...
        if(!s.contains(9)){
            System.out.println("not exists!");
        }
    }
}

 

6. 연습문제2

 

n개의 명령이 주어질때, 각 명령을 수행하는 프로그램을 작성

 

• add x : 숫자 x를 hashset에 추가합니다. 중복되는 경우 무시합니다.
• remove x : 숫자 x를 hashset에서 제거합니다. 잘못된 입력은 주어지지 않습니다.
• find x : 숫자 x가 hashset에 있는지를 판단합니다. 있다면 true, 없다면 false를 출력합니다.

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 여기에 코드를 작성해주세요.

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        HashSet<Integer> s = new HashSet<>();

        for(int i = 0; i < n; i++){

            String q = sc.next();

            if(q.equals("add")){

                int x = sc.nextInt();

                s.add(x);
            } else if(q.equals("remove")){

                int x = sc.nextInt();

                s.remove(x);
            } else {

                int x = sc.nextInt();

                System.out.println(s.contains(x));

            }
        }
    }
}