Map - 컬렉션 프레임워크 - Map 구현체

자바의 Map 인터페이스는 키-값 쌍을 저장하는 자료 구조이다. Map은 인터페이스이기 때문에, 직접 인스턴스를 생성할 수는 없고, 대신 Map 인터페이스를 구현한 여러 클래스를 통해 사용할 수 있다. 대표적으로 HashMap, TreeMap, LinkedHashMap이 있다.

 

Map vs Set

그런데 Map을 어디서 많이 본 것 같지 않은가? Map의 키는 중복을 허용하지 않고, 순서를 보장하지 않는다.

Map의 키가 바로 Set과 같은 구조이다. 그리고 Map은 모든 것이 Key를 중심으로 동작한다.

Values는 단순히 Key 옆에 따라 붙는 것 뿐이다. Key 옆에 Value만 하나 추가해주면 Map이 되는 것이다.
Map과 Set은 거의 같다. 단지 옆에 Value를 가지고 있는가 없는가의 차이가 있을 뿐이다.

 

이런 이유로 Set과 Map의 구현체는 거의 같다.

• HashSet -> HashMap
• LinkedHashSet -> LinkedHashMap
• TreeSet -> TreeMap

참고 : 실제로 자바 HashSet의 구현은 대부분 HashMap의 구현을 가져다 사용한다. Map에서 value만 비워두면 Set으로 사용할 수 있다.

 

각각의 특징을 알아보자.

참고로 앞서 Set에서 학습한 내용과 거의 같다.

 

 

1.HashMap

• 구조 : HashMap은 해시를 사용해서 요소를 저장한다. 키(Key)값은 해시 함수를 통해 해시 코드로 변환되고, 이 해시 코드는 데이터를 저장하고 검색하는데 사용된다.
• 특징 : 삽입, 삭제, 검색 작업은 해시 자료구조를 사용하므로 일반적으로 상수 시간( O(1) )의 복잡도를 가진다
• 순서 : 순서를 보장하지 않는다.

2. LinkedHashMap

• 구조 : LinkedHashMap은 HashMap과 유사하지만, 연결 리스트를 사용하여 삽입 순서 또는 최근 접근 순서에 따라 요소를 유지한다.
• 특징 : 입력 순서에 따라 순회가 가능하다. HashMap과 같지만 입력 순서를 링크로 유지해야 하므로 조금 더 무겁다.
• 성능 : HashMap과 유사하게 대부분의 작업은 O(1)의 시간 복잡도를 가진다.
• 순서 : 입력 순서를 보장한다.

3.TreeMap

• 구조 : TreeMap은 레드 - 블랙 트리를 기반으로 한 구현이다.
• 특징 : 모든 키는 자연 순서 또는 생성자에 제공된 Comparator에 의해 정렬된다.
• 성능 : get, put, remove와 같은 주요 작업들은 O(log n)의 시간 복잡도를 가진다.
• 순서 : 키는 정렬된 순서로 저장된다.

package collection.Map;

import java.util.*;

public class JavaMapMain {
    public static void main(String[] args) {
        run(new HashMap<>());
        run(new LinkedHashMap<>());
        run(new TreeMap<>());

    }

    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.println(key + " = " + map.get(key) + " ");
        }
        System.out.println();

    }
}

 

실행 결과

map = class java.util.HashMap
A = 30 
1 = 40 
B = 20 
2 = 50 
C = 10 

map = class java.util.LinkedHashMap
C = 10 
B = 20 
A = 30 
1 = 40 
2 = 50 

map = class java.util.TreeMap
1 = 40 
2 = 50 
A = 30 
B = 20 
C = 10

• HashMap : 입력한 순서를 보장하지 않는다.  O(1)
• LinkedHashMap : 키를 기준으로 입력한 순서를 보장한다. O(1)
• TreeMap : 키 자체의 데이터 값을 기준을 정렬한다. O(log n)

 

 

JavaHashMap의 작동 원리

자바의 HashMap과 HashSet은 작동 원리가 같다

Set과 비교하면 다음과 같은 차이가 있다.

• Key를 사용해서 해시 코드를 생성한다.
• Key뿐만 아니라 값(Value)을 추가로 저장해야 하기 대문에 Entry를 사용해서 Key, Value를 하나로 묶어서 저장한다.
•  

이렇게 해시를 사용해서 키와 값을 저장하는 자료 구조를 일반적으로 해시 테이블이라 한다.

앞서 학습한 HashSet은 해시 테이블의 주요 원리를 사용하지만, 키-값 저장 방식 대신 키만 저장하는 특수한 형태의 해시 테이블로 이해하면 된다.

 

주의 ! 

Map의 Key로 사용되는 객체는 hashCode(), equals()를 반드시 구현해야 한다.

 

정리

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