[Java API] Map 인터페이스(HashMap, LinkedHashMap, TreeMap)

https://claremont.tistory.com/entry/Java-API-%EC%BB%AC%EB%A0%89%EC%85%98-%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%ACCollection-Framework

[Java API] 컬렉션 프레임워크(Collection Framework)

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep2-%EC%82%AC%EC%A0%84dictionary

[알고리즘] ep2) 사전(dictionary)

ㅁMap: 키-값 쌍을 저장하는 자료구조

순서 X,  key: 중복 X / value: 중복 O

 

 

(맵 인터페이스는 컬렉션 인터페이스를 상속받지 않는다)

맵 인터페이스 - 해시 맵 - 링크드해시맵

                        - 트리 맵     

Map 인터페이스

Map 인터페이스는 사전 ADT에 부합하는 자료구조이다. (순서 X,  key: 중복 X / value: 중복 O)

Map은 인터페이스이기 때문에, 직접 인스턴스를 생성할 수는 없다. 대신 HashMap(순서 X, key: 중복 X / value: 중복 O), LinkedHashMap(순서 O, key: 중복 X / value: 중복 O), TreeMap(순서 - key 기준 정렬, key: 중복 X / value: 중복 O) 등의 여러 구현 클래스를 가지고 있으며, 각 클래스는 Map 인터페이스를 구현하며 각각의 특성을 갖고 있다.

 

(참고)

Map과 Set은 거의 같다. 단지 옆에 Value를 가지고 있는가 없는가의 차이일 뿐이다.

 

[Map 인터페이스의 주요 메서드]

 

(HashMap 메서드 활용 코드)

package collection.map;

import java.util.HashMap;
import java.util.Map;

public class MapMain1 {
    public static void main(String[] args) {
        Map<String, Integer> studnetMap = new HashMap<>();

        // 학생 성적 데이터 추가
        studnetMap.put("studentA", 90);
        System.out.println(studnetMap);

        studnetMap.put("studentA", 100); // 같은 키에 저장시 기존 값 교체
        System.out.println(studnetMap);

        boolean containsKey = studnetMap.containsKey("studentA");
        System.out.println("containsKey = " + containsKey);

        // 특정 학생의 값 삭제
        studnetMap.remove("studentA");
        System.out.println(studnetMap);
    }
}

 

package collection.map;

import java.util.HashMap;
import java.util.Map;

public class MapMain2 {
    public static void main(String[] args) {
        Map<String, Integer> studnetMap = new HashMap<>();

        // 학생 성적 데이터 추가
        studnetMap.put("studentA", 50);
        System.out.println(studnetMap);

        // 학생이 없는 경우에만 추가1
        if (!studnetMap.containsKey("studentA")) {
            studnetMap.put("studentA", 100);
        }
        System.out.println(studnetMap);

        // 학생이 없는 경우에만 추가2
        studnetMap.putIfAbsent("studentA", 100);
        studnetMap.putIfAbsent("studentB", 100);
        System.out.println(studnetMap);
    }
}

 

package collection.map;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class MapMain3 {
    public static void main(String[] args) {
        Map<String, Integer> studentMap = new HashMap<>();
        // 학생 성적 데이터 추가
        studentMap.put("studentA", 90);
        studentMap.put("studentB", 80);
        studentMap.put("studentC", 80);
        studentMap.put("studentD", 100);
        System.out.println(studentMap);
        // 특정 학생의 값 조회
        Integer result = studentMap.get("studentD");
        System.out.println("result = " + result);
        System.out.println();

        System.out.println("keySet 활용: key들을 Set형태로 반환");
        Set<String> keySet = studentMap.keySet();
        for (String key : keySet) {
            Integer value = studentMap.get(key);
            System.out.println("key = " + key + ", value = " + value);
        }
        System.out.println();

        System.out.println("values 활용: value들을 Collection형태로 반환");
        Collection<Integer> values = studentMap.values();
        for (Integer value : values) {
            System.out.println("value = " + value);
        }
        System.out.println();

        System.out.println("entrySet 활용: key-value쌍을 Set<Map.Entry<K, V>>형태로 반환");
        Set<Map.Entry<String, Integer>> entries = studentMap.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("key = " + key + ", value = " + value);
        }
    }
}

 

 

 

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep4-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94hashtable

[알고리즘] ep4) 해시테이블(hashtable)

ㅇHashMap: hash 자료구조를 사용해 Map을 구현

- HashMap의 주요 연산(추가, 삭제, 검색)은 평균 O(1) 시간 복잡도를 가진다

 

 

ㅇLinkedHashMap: HashMap + LinkedList (HashMap의 순서가 있는 버전)

- 그림에서 이해를 돕기 위해 단방향 화살표로 나타냈지만, 실제로는 양방향이다

- HashMap과 마찬가지로 주요 연산(추가, 삭제, 검색)은 평균 O(1) 시간 복잡도를 가진다

- 데이터의 유일성과 함께 삽입 순서를 유지해야 할 때 적합하다

 

 

https://claremont.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-ep3-%ED%83%90%EC%83%89%ED%8A%B8%EB%A6%AC

[알고리즘] ep3) 탐색트리

ㅇTreeMap: 이진탐색 트리를 사용해 Map을 구현 (레드-블랙 트리를 사용해 균형을 유지 -> 최악의 상황에도 O(log n) 성능)

- 요소들은 입력되는 시점에 정렬된 순서로 저장되며, 순서의 기준은 비교자(Comparator)로 변경할 수 있다

- 주요 연산들은 O(log n) 시간 복잡도를 가진다 (HashMap보다는 느리다)

- 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 할 때 사용한다

 

 

 

이렇게 해시를 사용해서 키와 값을 저장하는 자료구조를 일반적으로 해시테이블이라 한다. 앞서 학습한 HashSet은 해시테이블의 주요 원리를 사용하지만, 키-값 저장 방식 대신 키만 저장하는 특수한 형태의 해시 테이블로 이해하면 된다.

사전 ADT = 해시테이블 = Map 이라 생각하면 편하다 (물론 셋이 완전히 같은 개념은 아니다)

 

Map의 Key로 사용되는 객체는 반드시 hashCode()와 equals()를 오버라이딩 해야 한다. 참고로 자바가 제공하는 String, Integer 같은 기본 클래스들은 전부 hashCode(), equals()가 오버라이딩 되어 있어 따로 해줄 필요가 없다. 따라서 우리는 커스텀 객체에 대해서만 필요할 때 오버라이딩을 하면 된다.

 

실무에서는 Map이 필요한 경우 HashMap을 가장 많이 사용한다. 그리고 입력 순서 유지, 값 정렬 필요에 따라서 LinkedHashMap, TreeMap을 선택하면 된다.

(HashMap, LinkedHashMap, TreeMap 사용 예시 코드)

package collection.map;

import java.util.*;

public class MapMain4 {
    public static void main(String[] args) {
        run(new HashMap<>()); // 순서 X, key: 중복 X / value: 중복 O
        run(new LinkedHashMap<>()); // 순서 O, key: 중복 X / value: 중복 O
        run(new TreeMap<>()); // 순서 - key 기준 정렬, key: 중복 X / value: 중복 O
    }

    private static void run(Map<String, Integer> map) {
        System.out.println("map = " + map.getClass());
        map.put("C", 10);
        map.put("B", 20);
        map.put("A", 30);
        map.put("1", 40);
        map.put("2", 50);

        Set<String> keySet = map.keySet();
        Iterator<String> iterator = keySet.iterator();
        while (iterator.hasNext()) {
            String key = iterator.next();
            System.out.print(key + "=" + map.get(key) + " ");
        }
        System.out.println();
        System.out.println();
    }
}

 

 

 

 

 

(참고) HashSet의 구현은 대부분 HashMap의 구현을 가져다 사용한다. Map에서 Value만 비워두면 Set으로 사용할 수 있다.

 

참고 및 출처: 김영한의 실전 자바 - 중급 2편

https://www.inflearn.com/course/%EA%B9%80%EC%98%81%ED%95%9C%EC%9D%98-%EC%8B%A4%EC%A0%84-%EC%9E%90%EB%B0%94-%EC%A4%91%EA%B8%89-2