Hashmap / Treemap

이번 시간에는 map 구조, 그 중 가장 많이 쓰이는 hashmap과 treemap에 대해 알아보려고 합니다.

Map 인터페이스를 구현한 Map 컬렉션 클래스들은 키와 값을 하나의 쌍으로 저장하는 방식(key-value 방식)을 사용합니다.

여기서 키(key)란 실질적인 값(value)을 찾기 위한 이름의 역할을 합니다.

Map 컬렉션 클래스의 공통된 특징 2가지가 다음과 같습니다.

 

1. 요소의 저장 순서를 유지하지 않습니다.

2. 키는 중복을 허용하지 않지만, 값의 중복은 허용합니다.

 

해시 알고리즘(hash algorithm)이란 해시 함수(hash function)를 사용하여 데이터를 해시 테이블(hash table)에 저장하고, 다시 그것을 검색하는 알고리즘입니다.

자바에서 해시 알고리즘을 이용한 자료구조는 그림과 같이 배열과 연결 리스트로 구현됩니다.

저장할 데이터의 키 값을 해시 함수에 넣어 반환되는 값으로 배열의 인덱스를 구합니다.

그리고 해당 인덱스에 저장된 연결 리스트에 데이터를 저장하게 됩니다.

 

Hashmap은 map 클래스 중 가장 많이 사용되는 예시로, 앞서 설명한 해시 알고리즘을 사용합니다.

중복된 키로는 값을 저장할 수 없지만, 같은 값을 서로 다른 키로 저장할 수는 있습니다.

다시 말해, 위 예시에서 ‘김말이’라는 동일한 키 값을 두 번 추가할 수는 없지만, ‘야채튀김’이라는 새로운 키 값을 배열에서 ‘김말이’가 저장된 01번지에 추가로 저장할 수는 있다는 뜻입니다.

HashMap<K, V> 클래스에서 제공하는 주요 메소드는 다음과 같습니다.

메소드	설명
void clear()	맵(map)의 모든 매핑(mapping) 제거
boolean containsKey(Object key)	맵이 전달된 키를 포함하고 있는지 확인
boolean containsValue(Object value)	맵이 전달된 값에 하는 하나 이상의 키를 포함하고 있는지 확인
V get(Object key)	맵에서 전달된 키에 대응하는 값 반환 :만약 맵이 전달된 키를 포함한 매핑을 포함하고 있지 않으면 null을 반환
boolean isEmpty()	맵이 비어 있는지 확인
Set<K> keySet()	맵에 포함되어 있는 모든 키로 만들어진 Set 객체 반환
V put(K key, V value)	맵에 전달된 키에 대응하는 값으로 특정 값을 매핑
V remove(Object key)	맵에서 전달된 키에 대응하는 매핑을 제거
boolean remove(Object key, Object value)	맵에서 특정 값에 대응하는 특정 키의 매핑 제거
V replace(K key, V value)	맵에서 전달된 키에 대응하는 값을 특정 값으로 대체
boolean replace(K key, V oldValue, V newValue)	맵에서 특정 값에 대응하는 전달된 키의 값을 새로운 값으로 대체
int size()	맵의 매핑의 총 개수 반환

아래 코드를 통해 Hashmap에 대해 알아보겠습니다.

Put() 메서드를 사용하여 값을 추가하였더니, 가장 최근 추가한 값부터 출력되는 것을 확인했습니다.

그리고 해시맵이름.get(key) 메서드를 사용하여 키에 저장된 값을 꺼낼 수 있었습니다.

그리고 keySet() 메소드는 해당 맵에 포함된 모든 키 값들을 하나의 집합(Set)으로 반환해 줍니다.

package jaryogujo;
import java.util.*;
public class Hashmap {
	public static void main(String[] args) {
		HashMap<String, Integer> hm = new HashMap<String, Integer>();
		// put() 메소드를 이용한 요소의 저장
		hm.put("삼십", 30);
		hm.put("십", 10);
		hm.put("사십", 40);
		hm.put("이십", 20);
		// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
		System.out.println("맵에 저장된 키들의 집합 : " + hm.keySet());
		for (String key : hm.keySet()) { //확장포문
		    System.out.println(String.format("키 : %s, 값 : %s", key, hm.get(key))); //해시맵이름.get(key) = value 꺼내짐
		}

		// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
		System.out.println("맵에 저장된 키들의 집합 : " + hm.keySet());
		for (String key : hm.keySet()) { //확장포문
		    System.out.println(String.format("키 : %s, 값 : %s", key, hm.get(key))); //해시맵이름.get(key) = value 꺼내짐
		}

Remove()메서드를 사용하여 키 ‘사십’ 과 이에 해당하는 값 40을 함께 삭제했습니다.

그 결과를 iterator()메서드를 사용하여 키 개수만큼 반복하여 출력한 결과가 다음과 같습니다.

	hm.remove("사십");		 

	// iterator() 메소드와 get() 메소드를 이용한 요소의 출력
	Iterator<String> keys = hm.keySet().iterator();
	while (keys.hasNext()) {
	    String key = keys.next();
	    System.out.println(String.format("키 : %s, 값 : %s", key, hm.get(key)));
}

Replace()메서드로 키 ‘이십’에 해당하는 값 20을 200으로 수정했습니다.

// replace() 메소드를 이용한 요소의 수정
	hm.replace("이십", 200);		 
	for (String key : hm.keySet()) {
	System.out.println(String.format("키 : %s, 값 : %s", key, hm.get(key)));
}

이 해시맵의 크기는 다음과 같이 size()메서드로 구할 수 있습니다.

	// size() 메소드를 이용한 요소의 총 개수
		System.out.println("맵의 크기 : " + hm.size());
	}

}

그리고 hashmap의 개념을 확장한 것이 treemap입니다.

TreeMap 클래스는 키와 값을 한 쌍으로 하는 데이터를 이진 검색 트리(binary search tree) 형태로 저장합니다.

이진 검색 트리는 데이터를 추가/제거하는 기본동작 시간이 매우 빠릅니다.

그리고 TreeMap 클래스는 NavigableMap 인터페이스를 기존의 이진 검색 트리의 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현하여, 정렬된 검색 결과를 가져올 수 있습니다.

수정, 삭제 등의 기능은 모두 hashmap과 동일하지만, 결과값이 정렬되어 출력된다는 점이 가장 큰 treemap의 특징입니다.

그래서 treemap 예제는 데이터의 입출력까지만 살펴볼 것입니다.

package jaryogujo;
import java.util.*;
public class Treemap {
public static void main(String[] args) {
TreeMap<Integer, String> tm = new TreeMap<Integer, String>();
		// put() 메소드를 이용한 요소의 저장
		tm.put(30, "삼십");
		tm.put(10, "십");
		tm.put(40, "사십");
		tm.put(20, "이십");
		// Enhanced for 문과 get() 메소드를 이용한 요소의 출력
		System.out.println("맵에 저장된 키들의 집합 : " + tm.keySet());
		for (Integer key : tm.keySet()) {
			System.out.println(String.format("키 : %s, 값 : %s", key, tm.get(key)));
		}

TreeMap<K, V> 에서만 특징적으로 사용되는 메소드는 다음과 같습니다.

메소드	설명
Map.Entry<K, V> ceilingEntry(K key)	맵에서 전달된 키와 같거나, 전달된 키보다 큰 키 중에서 가장 작은 키와 그에 대응하는 값의 엔트리를 반환함. 만약 해당하는 키가 없으면 null을 반환
K ceilingKey(K key)	맵에서 전달된 키와 같거나, 전달된 키보다 큰 키 중에서 가장 작은 키를 반환 만약 해당하는 키가 없으면 null을 반환
NavigableMap<K, V> descendingMap()	맵에 포함된 모든 매핑을 역순으로 반환
Set<Map.Entry<K, V>> entrySet()	맵에 포함된 모든 매핑을 Set 객체로 반환
Map.Entry<K, V> firstEntry()	맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환
K firstKey()	맵에서 현재 가장 작은(첫 번째) 키를 반환
Map.Entry<K, V> floorEntry(K key)	맵에서 전달된 키와 같거나, 전달된 키보다 작은 키 중에서 가장 큰 키와 그에 대응하는 값의 엔트리를 반환 :만약 대응하는 키가 없으면 null을 반환
K floorKey(K key)	맵에서 전달된 키와 같거나, 전달된 키보다 작은 키 중에서 가장 큰 키를 반환 만약 해당하는 키가 없으면 null을 반환
SortedMap<K, V> headMap(K toKey)	맵에서 전달된 키보다 작은 키로 구성된 부분만을 반환
Map.Entry<K, V> higherEntry(K key)	맵에서 전달된 키보다 작은 키 중에서 가장 큰 키와 그에 대응하는 값의 엔트리를 반환 :만약 해당하는 키가 없으면 null을 반환
K higherKey(K key)	맵에서 전달된 키보다 작은 키 중에서 가장 큰 키를 반환 만약 해당하는 키가 없으면 null을 반환
Map.Entry<K, V> lastEntry()	맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리를 반환
K lastKey()	맵에서 현재 가장 큰(마지막) 키를 반환
Map.Entry<K, V> lowerEntry(K key)	맵에서 전달된 키보다 큰 키 중 가장 작은 키와 그에 대응하는 값의 엔트리를 반환 :만약 해당하는 키가 없으면 null을 반환
K lowerKey(K key)	맵에서 전달된 키보다 큰 키 중에서 가장 작은 키를 반환 :만약 해당하는 키가 없으면 null을 반환
Map.Entry<K, V> pollFirstEntry()	맵에서 현재 가장 작은(첫 번째) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
Map.Entry<K, V> pollLastEntry()	맵에서 현재 가장 큰(마지막) 키와 그에 대응하는 값의 엔트리를 반환하고, 해당 엔트리를 맵에서 제거
SortedMap<K, V> ubmap(K fromKey, K toKey)	맵에서 fromKey부터 toKey까지로 구성된 부분만을 반환 이때 fromKey는 포함되나, toKey는 포함되지 않음.
SortedMap<K, V> tailMap(K fromKey)	맵에서 fromKey와 같거나, fromKey보다 큰 키로 구성된 부분만 반환

그래서, hashmap과 treemap의 차이점을 다음과 같이 요약할 수 있습니다.

 

	get	containsKey	Next	notes
Hashmap	O(1)	O(1)	O(h/n)	h is the table capacity
Treemap	O(log n)	O(log n)	O(log n)

 

다음 시간에는 stack에 대해 알아보겠습니다.