[Java] 자료 구조 - HashMap, TreeMap

JUNBEOM PARK·2022년 2월 24일

🧨 Java

목록 보기

30/33

🤔 Map ?

Map 인터페이스는 Collection 인터페이스와 다른 저장 방식을 가진다.
Map 인터페이스를 구현한 Map 컬렉션 클래스들은 key와 value를 하나의 쌍으로 저장하는 방식이다.
여기서 key란 실질적인 값(value)를 찾기 위한 이름의 역할을 한다.

Map의 특징
1. 요소의 저장 순서를 유지하지 않는다.
2. key는 중복을 허용하지 않지만, 값(value)의 중복은 허용한다.

😃 HashMap

HashMap 클래스는 Map 컬렉션 클래스에서 가장 많이 사용된다.
해쉬 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.
HashMap 클래스는 Map 인터페이스를 구현 하므로, 중복된 키로는 값을 저장할 수 없지만
다른 키로 저장하는 것은 가능하다.

HashMap 선언


HashMap<String, String> map = new HashMap<String, String>(); // String, String 타입 설정

Java에서 HashMap을 선언 하려면 java.util.HashMap을 import 한 뒤,
HashMap<element> map = new HashMap<>(); 과 같은 형식으로 선언 한다.

HashMap 값 추가


HashMap<String, String> map = new HashMap<String, String>(); // HashMap 선언 

// 값 추가 
map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

System.out.print(map); // {1=Java, 2=Oracle, 3=SQL, 4=Spring}

put(key, value) 메소드를 사용해 값을 추가한다.

들어가는 타입은 HashMap<'타입','타입'> 에 맞춰서 입력 해줘야 한다.

위 코드는 key, value 모두 String이니 String으로 추가 해준다.

HashMap 값 삭제


HashMap<String, String> map = new HashMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

map.remove("3);

System.out.print(map); // {1=Java, 2=Oracle, 4=Spring}

remove(key) 메소드를 사용해 해당 하는 key를 삭제 할 수 있다.
clear() 메소드를 사용하면 HashMap의 모든 키 값을 삭제 한다.

HashMap 크기


HashMap<String, String> map = new HashMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 


System.out.print(map); // {1=Java, 2=Oracle, 4=Spring}

System.out.print("Size : " + map.size()); // Size : 4

size() 메소드를 사용해 HashMap의 크기를 구할 수 있다.

HashMap 값 출력

HashMap의 값을 출력하는 방법은 여러가지가 있는데 대표적인 두 가지 방법은 향상된 for문과 Iterator클래스를 사용 하는 방법이다.

향상된 for문

HashMap<String, String> map = new HashMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

for(Map.Entry<String, String> e : map.entrySet()) {
	System.out.println("Key : " + e.getKey() + ", Value : " + e.getValue());
}

for(Map.Entry<타입, 타입> 변수명 : entrySet()) 을 사용하여 HashMap을 반복문을 실행한다

이어서 getKey(), getValue() 메소드를 사용해 HashMap의 key 갑과 value 값을 가져 올 수 있다.

Iterator

HashMap<String, String> map = new HashMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

Iterator<Entry<String, String>> iter = map.entrySet().iterator();
		
while(iter.hasNext()) {
	Map.Entry<String, String> e = (Map.Entry<String, String>)iter.next();// (key, value)
	System.out.println("key : "+e.getKey()+", value : "+e.getValue()); 
}

Iterator를 Entry로 선언하여 위의 향상된 for문 처럼 getKey(), getValue() 방식으로 가져올 수 있다.

😉 TreeMap

TreeMap 클래스는 이진트리를 기반으로 한 Map 컬렉션클래스 이다.
같은 Tree 구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값만 저장 한다면 TreeMap은 키와 값이 저장된 Map, Entry를 저장한다.
TreeMap에 객체를 저장하면 자동으로 정렬된다.
key는 저장과 동시에 자동으로 오름차순으로 정렬된다.
정렬 순서는 기본적으로 부모 키값과 비교해서 키 값이 낮은 것은 왼쪽 자식 노드에 키 값이 높은 것은 오른쪽 자식 노드에 Map.Entry 객체를 저장 한다.
TreeMap은 일반적으로 Map으로써의 성능이 HashMap보다 떨어진다.
TreeMap은 데이터를 저장할 때 즉시 정렬하기 때문에 추가나 삭제가 HashMap보다 오래 걸린다.
정렬된 상태로 Map을 유지해야 하거나 정렬된 데이터를 조회해야 하는 범위 검색이 필요한 경우 TreeMap이 더 효율적 이다.

TreeMap은 이진탐색트리의 문제점을 보완한 레드-블랙 트리(Red-Black Tree)로 이루어져 있다.
일반적인 이진탐색 트리는 높이만큼 시간이 필요한다. 값이 전체 트리에 잘 분산 되어 있다면 효율성에 있어 크게 문제가 없으나 데이터가 들어올 때 값이 한쪽으로 편향하게 되어 들어올 경우 한쪽 방면으로 크게 치우쳐진 트리가 되어 굉장히 비효율적인 효율을 낸다.
이 문제를 보완하기 위해 레드 블랙 트리가 등장 했다. 레드 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식으로, 큰 값을 가지는 노드는 오른쪽 자식으로 배치하여 데이터의 추가나 삭제시 트리가 한쪽으로 치우쳐지지 않도록 균형을 맞추어 준다.

TreeMap 선언

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

Java에서 TreeMap을 선언 하려면 java.util.TreeMap을 import 한 뒤,
TreeMap<element> map = new TreeMap<>(); 과 같은 형식으로 선언 한다.

TreeMap 값 추가

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

System.out.print(map); // {1=Java, 2=Oracle, 3=SQL, 4=Spring}

TreeMap은 구조만 HashMap과 다를뿐이지 기본적으로 Map인터페이스를 같이 상속 받고 있으므로 기본적인 메소드의 사용법 자체는 HashMap과 동일하다.

TreeMap 값 삭제

TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

map.remove("3);

System.out.print(map); // {1=Java, 2=Oracle, 4=Spring}

TreeMap 값 삭제 또한 HashMap과 동일하다

TreeMap 단일 값 출력


TreeMap<String, String> map = new TreeMap<String, String>(); // String, String 타입 설정

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

System.out.print(map); // 전체 출력 : {1=Java, 2=Oracle, 3=SQL, 4=Spring}
System.out.println(map.get(1));//key값 1의 value얻기 : Java
System.out.println(map.firstEntry());//최소 Entry 출력 : 1=Java
System.out.println(map.firstKey());//최소 Key 출력 : 1
System.out.println(map.lastEntry());//최대 Entry 출력: 4=Spring
System.out.println(map.lastKey());//최대 Key 출력 : 4

TreeMap은 HashMap과는 달리 Tree구조로 이루어져 있기에 항상 정렬이 되어 있어 최솟값, 최댓값을 바로 가져오는 다양한 메소드를 지원한다. firseEntry는 최소 Entry값, fisrtKey는 최소 key값, lastEntry는 최대 Entry값, lastKey는 최대 key값을 리턴한다.

TreeMap 전체 출력

전체 출력 또한 HashMap과 동일하다.

향상된 for문

TreeMap<String, String> map = new TreeMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

for(Map.Entry<String, String> e : map.entrySet()) {
	System.out.println("Key : " + e.getKey() + ", Value : " + e.getValue());
}

Iterator

TreeMap<String, String> map = new TreeMap<String, String>(); // HashMap 선언 

map.put("1", "Java"); 
map.put("2", "Oracle"); 
map.put("3", "SQL"); 
map.put("4", "Spring"); 

Iterator<Entry<String, String>> iter = map.entrySet().iterator();
		
while(iter.hasNext()) {
	Map.Entry<String, String> e = (Map.Entry<String, String>)iter.next();// (key, value)
	System.out.println("key : "+e.getKey()+", value : "+e.getValue()); 
}