[JAVA] Map - HashMap, TreeMap, LinkedHashMap

Map 컬렉션 클래스

Map은 List, Set의 인터페이스인 Collection 인터페이스와 다른 저장 방식을 가진다.

 

Map은 Key - Value의 pair 형식의 데이터 저장 방식을 가진다.

Map 인터페이스로 구현한 모든 Map 컬렉션 클래스는

데이터의 저장 순서를 유지하지 않는다.

Key와 Value는 매칭이 되어 있는데 키는 중복을 허용하지 않지만 값은 중복을 허용한다.

 

즉, Key는 고유의 key를 가져야 하고, Value는 여러 군데에서 쓰일 수 있다는 얘기다.

 

예로 들어

C - 언어, 자바 - 언어

위와 같이 Value는 중복이 허용이 되지만

 

과일 - 사과, 과일 - 포도

위와 같이 Key는 중복이 허용이 불가능하다.

 

Map에서 많이 쓰이는 함수는 put(), get(), remove() 등이 있다.

 

put() 사용법

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		System.out.println(map);
		
		map.put("파이썬", "언어");
		System.out.println(map);
		map.put("C++", "언어");
		System.out.println(map);
		
		map.put("C++", "객체");
		System.out.println(map);
	}
}
-------------------- 출력 결과 ---------------------------
{C=언어, 자바=언어}
{C=언어, 파이썬=언어, 자바=언어}
{C++=언어, C=언어, 파이썬=언어, 자바=언어}
{C++=객체, C=언어, 파이썬=언어, 자바=언어}

위와 같이 put을 통해 key - value로 값을 저장할 수 있다.

 

여기서 C와 자바를 먼저 저장하고 파이썬을 저장했지만 출력 결과 위치가

일정하지 않다는 것을 확인할 수 있다.(요소의 저장 순서를 유지하지 않는다.)

 

또한 Value는 Key 값이 다르면 중복이 가능하지만

Key는 중복을 허용하지 않아 값을 덮어쓴다.

 

 

get() 사용법

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		
		System.out.println(map.get("자바"));
	}
}
------------- 출력 결과 ----------------------
언어

get()을 통해 key 값을 입력하면 key와 매칭이 되어 있는 value 값을 가져온다.

 

 

remove() 사용법

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		
		System.out.println(map.get("자바"));
		
		map.remove("자바");
		System.out.println(map.get("자바"));
	}
}
----------------------- 출력 결과 -----------------------------
언어
null

remove를 통해 해당 key를 삭제할 수 있다.

 

 

 

Map 인터페이스로 구현된 여러 클래스들이 존재하는데

그 중 가장 많이 쓰이는 클래스는 HashMap, TreeMap, LinkedHashMap 이다.

 

 

HashMap

HashMap은 Map 컬렉션 클래스 중 가장 많이 사용되는 클래스이다.

내부적으로 Entry 배열을 만들어 관리한다.

 

put() 메소드를 이용하여 엔트리를 추가하면 key 값으로 넘겨준 해시 코드를 계산하여

Entry 배열의 접근할 인덱스로 사용을 한다.

 

해시 알고리즘을 통해 O(1)의 시간복잡도를 가질 수 있다.

해시 알고리즘으로 알고리즘 구현이 가능하다면 매우 빠른 검색 속도를 가질 수 있다.

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		
		System.out.println("map에 담긴 키의 집합 : " + map.keySet());
		for(String key : map.keySet()) {
			System.out.println(map.get(key));
		}
		
		Set<String> keySet = map.keySet();
		System.out.println("map에 담긴 키의 집합 : " + keySet);
		for(String key : keySet) {
			System.out.println(map.get(key));
		}
	}
}
------------------------- 출력 결과 ---------------------------
map에 담긴 키의 집합 : [C, 자바]
언어
언어
map에 담긴 키의 집합 : [C, 자바]
언어
언어

keySet() 메소드는 맵에 저장되어 있는 모든 키 값을 하나의 집합(Set)으로 반환을 한다.

map.keySet() 메소드로 바로 사용할 수 있고, 집합으로 반환하기 때문에

당연하게 Set<String>을 통하여 선언도 가능하다.

 

이번 예제에서는 향상된 for문을 사용하였는데

컬렉션 프레임워크에서 해당 인스턴스에 저장된 모든 데이터를 순회할 경우 많이 사용한다.

 

forEach문 사용 예제

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		
		map.forEach((key, value) -> {
			System.out.println(key +" : "+value);
		});
	}
}
------------- 출력 결과 -----------------
C : 언어
자바 : 언어

 

여기서 드는 생각은 키 값은 keySet을 통해 모든 key 값을 반환할 수 있는데

value 또한 for문을 하지 않고 모든 value 값을 반환할 수 있지 않을까?

 

물론 가능하다.

public class HashMapSample {

	public static void main(String[] args) {
		
		Map<String, String> map = new HashMap<String, String>();
		map.put("C", "언어");
		map.put("자바", "언어");
		
		System.out.println("map에 담긴 값의 집합 : " + map.values());
		
		Collection<String> value = map.values();
		System.out.println("map에 담긴 값의 집합 : " + value);
	}
}
--------------- 출력 결과 -------------------
map에 담긴 값의 집합 : [언어, 언어]
map에 담긴 값의 집합 : [언어, 언어]

map.value()를 통해 map에 담긴 value의 모든 값을 반환할 수 있다.

선언 또한 가능한데

value는 Collection<V> values 로 value의 목록을 Collection으로 반환한다. 

 

 

 

TreeMap

Map에서 정렬을 할 때 사용하는 클래스이다.

데이터를 내부적으로 RB-Tree 형태로 관리하기 때문에 탐색-삽입-삭제에 O(log n)시간이 걸린다.

 

일반적으로는 HashMap을 많이 사용하지만

HashMap에는 정렬이 존재하지 않기 때문에 가끔 Map에서 데이터를 정렬할 때

TreeMap을 사용한다. 정렬은 key를 기준으로 정렬하고

숫자 -> 알파벳 대문자 -> 알파벳 소문자 -> 한글 순으로 정렬이 된다.

public class TreeMapSample {
	public static void main(String[] args) {
		TreeMap<String, String> map = new TreeMap<String, String>();
		map.put("a", "A");
		map.put("가", "기역");
		map.put("c", "C");
		map.put("b", "B");
		map.put("1", "one");
		map.put("F", "f");
		
		map.forEach((key, value) -> {
			System.out.println(key +" : "+value);
		});
	}
}
------------------------ 출력 결과 ---------------------------
1 : one
F : f
a : A
b : B
c : C
가 : 기역

 

TreeMap은 정렬을 목적으로 많이 사용이 되기 때문에

그에 관련된 메소드들이 존재한다.

public class TreeMapSample {
	public static void main(String[] args) {
		TreeMap<String, String> map = new TreeMap<String, String>();
		map.put("a", "A");
		map.put("가", "기역");
		map.put("c", "C");
		map.put("b", "B");
		map.put("1", "one");
		map.put("F", "f");
		
		System.out.println(map.firstKey());
		System.out.println(map.firstEntry());
	}
}
---------------------- 출력 결과 ----------------------------
1
1=one

map.firstKey()는 해당 맵의 가장 작은 키를 반환하고

map.firstEntry()는 해당 맵의 가장 작은 집합을 반환한다.

 

public class TreeMapSample {
	public static void main(String[] args) {
		TreeMap<String, String> map = new TreeMap<String, String>();
		map.put("a", "A");
		map.put("가", "기역");
		map.put("c", "C");
		map.put("b", "B");
		map.put("1", "one");
		map.put("F", "f");
		
		System.out.println(map);
		System.out.println(map.higherKey("c"));
	}
}
----------------------- 출력 결과 -------------------------
{1=one, F=f, a=A, b=B, c=C, 가=기역}
가

map.higherKey(key)는 전달된 키보다 작은 키 중에서 가장 큰 키가 반환된다.

즉 전달된 키의 다음 키를 반환하게 된다.

 

이 외에도 순서에 관한 많은 메소드들이 있다.

 

 

LinkedHashMap

TreeMap에서는 정렬의 순서가 존재하였지만,

LinkedHashMap은 데이터가 입력된 순서를 기억한다.

 

Map.Entry 클래스를 구현한 Node 클래스이며

내부적으로 before, after를 갖는 연결리스트 구조로 이루어져있다.

 

연결리스트 구조로 이루어져있어 탐색-추가-삭제에 O(1)의 시간을 가진다.

public class TreeMapSample {
	public static void main(String[] args) {
		LinkedHashMap<String, String> map = new LinkedHashMap<String, String>();
		map.put("a", "A");
		map.put("가", "기역");
		map.put("c", "C");
		map.put("b", "B");
		map.put("1", "one");
		map.put("F", "f");
		
		
		map.forEach((key, value) -> {
			System.out.println(key+" : "+value);
		});
	}
}
--------------------- 출력 결과 ------------------------
a : A
가 : 기역
c : C
b : B
1 : one
F : f

TreeMap에서 사용하던 코드를 LinkedHashMap으로 바꾸어보면

정렬의 순서가 정해져 있던 TreeMap과 달리

입력된 순서에 맞게 데이터가 출력되는 것을 볼 수 있다.

 

 

 

이렇게 HashMap, TreeMap, LinkedHashMap에 대해 알아보았다.

 

요약하자면

HashMap은 순서를 보장하지 않지만, 해시 값을 사용하기 때문에 시간 복잡도가 O(1)이다.

 

TreeMap은 key값을 통해 순서를 보장한다.(사전순)

(key값을 이용한 클래스를 Comparator 인터페이스로 구현한다면 순서 조정이 가능)

 

LinkedHashMap은 입력된 순서를 보장한다.

(Linked-list를 유지하는 비용이 들 수 있음)

 

각각 다른 특성을 가지지만

순서를 지켜야할 특별한 이유가 없다면 HashMap을 쓰는 것이 가장 좋다.