Java 자료구조 - Map 정리

Map

• 키(Key)와 값(value)의 쌍으로 연관지어 이루어진 데이터의 집합이다.
• 값(value)은 중복되서 저장될수 있지만, 키(key)는 해당 Map에서 고유해야만 한다.
• 만일 기존에 저장된 데이터와 중복된 키와 값을 저장하면 기존의 값은 없어지고 마지막에 저장된 값이 남게 된다.

추상 메서드	설명
void clear()	Map의 모든 객체를 삭제
boolean containsKey(Object key)	지정된 key객체와 일치하는 객체가 있는지 확인
boolean containsValue(Object value)	지정된 value객체와 일치하는 객체가 있는지 확인
Set entrySet()	Map에 저장된 key-value쌍을 Map.Entry타입의 객체로 저장한 Set을 반환
boolean equals(Object o)	동일한 Map인지 비교
Object get(Object key)	지정한 key객체에 대응하는 value객체를 반환
boolean isEmpty()	Map이 비어있는지 확인
Set keySet()	Map에 저장된 모든 key객체를 반환
Object put(Object key, Object value)	Map에 key객체와 value객체를 연결(mapping)하여 저장
void putAll(Map t)	지정된 Map의 모든 key-value쌍을 추가
Object remove(Object key)	지정한 key객체와 일치하는 key-value객체를 삭제
int size()	Map에 저장된 key-value쌍의 개수를 반환
Collection values()	Map에 저장된 모든 value객체를 반환

 

Map 인터페이스의 메소드를 보면, Key값을 반환할때 Set 인터페이스 타입으로 반환하고, Value값을 반환할때 Collection 타입으로 반환하는걸 볼 수 있다. Map 인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection 타입으로 반환하고, 키(key)는 중복을 허용하지 않기 때문에 Set 타입으로 반환하는 것이다.

 

Map.Entry 인터페이스

• Map.Entry 인터페이스는 Map 인터페이스 안에 있는 내부 인터페이스이다.
• Map 에 저장되는 key - value 쌍의 Node 내부 클래스가 이를 구현하고 있다.
• Map 자료구조를 보다 객체지향적인 설계를 하도록 유도하기 위한 것이다.

메서드	설 명
Set<Map.Entry<K,V>> entrySet	Entry Set 반환
boolean equals(Object o)	동일한 Entry 인지 비교
Object getKey( )	Entry 의 key 객체를 반환
Object getValue( )	Entry 의 value 객체를 반환
int hashCode( )	Entry 의 해시코드 반환
Object setValue(Object value)	Entry 의 value 객체를 지정된 객체로 바꾼다.

Map<String, Integer> map = new HashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

// Map.Entry 인터페이스를 구현하고 있는 Key-Value 쌍을 가지고 있는 HashMap의 Node 객체들의 Set 집합을 반환
Set<Map.Entry<String, Integer>> entry = map.entrySet();

System.out.println(entry); // [1=a, 2=b, 3=c]

// Set을 순회하면서 Map.Entry를 구현한 Node 객체에서 key와 value를 얻어 출력
for (Map.Entry<String, Integer> e : entry) {
    System.out.printf("{ %s : %d }\n", e.getKey(), e.getValue());
}

 

Hashtable

• 자바 초기 버전에 나온 레거시 클래스이다.
• 검색과 삽입에 O(1)시간이 소요된다. (연결리스트로 이루어진 배열로)
• 키의 순서는 무작위로 섞여 있다.
• HashMap 보다는 느리지만 동기화가 기본 지원된다(thread-safe).
• 키와 값으로 null이 허용되지 않는다.

HashMap

• Hashtable을 보완한 컬렉션
• 검색과 삽입에 O(1) 시간이 소요된다. (연결리스트로 이루어진 배열로)
• 키의 순서는 무작위로 섞여 있다.
• 비동기로 작동하기 때문에 멀티스레드 환경에서 어울리지 않는다.
• key와 value에 null 값이 허용된다.

LinkedHashMap

• 검색과 삽입에 O(1)시간이 소요된다.
• 양방향 연결 버킷으로 구현되어 있다.
• 데이터들이 들어온 순서대로 순서를 보장한다.

TreeMap

• 검색과 삽입에 O(log N)이 소요된다.
• SortedMap 인터페이스를 구현하고 있어 Key 값을 기준으로 정렬되어 있다.
  • 키는 반드시 Comparable Or Comparator 인터페이스를 구현하고 있어야 한다.
  • 정렬된 순서로 키/값 쌍을 저장하므로 빠른 검색이 가능하다.
  • 단, 키와 값을 저장하는 동시에 정렬을 행하기 때문에 저장시간이 다소 오래 걸린다.
  • 정렬되는 순서는 숫자->알파벳 대문자->알파벳 소문자->한글
• red-black트리로 구현되어 있다. (TreeSet과 같은 원리)

import java.util.TreeMap;
import java.util.Map;
import java.util.Comparator;

public class TreeMapExample {
    public static void main(String[] args) {
        // Comparable을 이용한 TreeMap 생성
        TreeMap<Integer, String> numbers = new TreeMap<>();
        numbers.put(3, "Three");
        numbers.put(1, "One");
        numbers.put(4, "Four");
        numbers.put(2, "Two");

        // TreeMap 출력
        System.out.println("Natural order:");
        for (Map.Entry<Integer, String> entry : numbers.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }

        // Comparator를 이용한 TreeMap 생성
        TreeMap<String, String> strings = new TreeMap<>(new CustomComparator());
        strings.put("banana", "Banana");
        strings.put("apple", "Apple");
        strings.put("cherry", "Cherry");

        // Comparator로 정렬된 TreeMap 출력
        System.out.println("Custom order:");
        for (Map.Entry<String, String> entry : strings.entrySet()) {
            System.out.println(entry.getKey() + " => " + entry.getValue());
        }
    }

    // 사용자 정의 Comparator
    static class CustomComparator implements Comparator<String> {
    	@Override
        public int compare(String s1, String s2) {
            return s1.compareToIgnoreCase(s2);
        }
    }
}

Natural order:
1 => One
2 => Two
3 => Three
4 => Four
Custom order:
apple => Apple
banana => Banana
cherry => Cherry

 
 

일반적으로 별다른 이유가 없다면 HashMap을 사용한다.
삽입한 순서대로 키 정보를 얻고 싶다면 LinkedHashMap,
정렬된 순서대로 키 정보를 얻고 싶다면 TreeMap, 
병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면 HashTable