TreeMap
TreeMap은 이진트리를 기반으로 Map 인터페이스를 구현한 컬렉션 클래스다. HashMap과 마찬가지로 키와 값(Key-Value) 쌍을 저장한다. HashMap은 키의 해시값을 기반으로 해시테이블을 구축하는 반면 TreeMap은 키 값을 이용해서 이진트리를 구축하고, 이진 트리의 노드에 값을 엔트리(Entry) 형태로 저장한다. 이진트리를 구축했기 때문에 키 값에 따라 정렬된 상태로 저장한다.
TreeMap이 키와 값을 내부에 저장하는 이진트리는 '레드-블랙트리(Red-Black Tree)'로 구현되어있다. 일반적인 이진트리의 성질에 균형잡힌 트리(Balanced Tree)의 특성을 부여한 이진트리로 노드들이 트리의 전반에 걸쳐 고르게 분포된다. (이는 곧 Skew 되지 않음을 의미하며 최악의 경우에도 O(log n)의 탐색시간을 보장함을 의미한다)
내부에 키와 값을 레드 블랙 트리에 저장하기 때문에 TreeMap에 값을 추가하거나 삭제하는 동작에 트리의 균형을 맞추는 작업이 들어가게 된다. 때문에 값의 추가와 삭제가 HashMap 보다는 느릴 수 있다.
TreeMap 사용법
TreeMap 생성
TreeMap 객체를 생성할 때에는 어떤 객체를 다룰 것인지 '지네릭스(Generics)'로 명시해줘야한다.
TreeMap<String, String> map1 = new TreeMap<>(); // TreeMap 객체 생성
TreeMap<String, String> map2 = new TreeMap<>(otherCollection); // 다른 컬렉션으로부터 생성다른 컬렉션 객체들처럼 선언해서 사용하면 된다. 다만 HashMap과 다르게 초기 용량(Capacity)을 지정할 수 있는 생성자가 없다는게 좀 다르다.
TreeMap에 Entry 추가
TreeMap 역시 Map 인터페이스를 구현하고 있기 때문에 put() 메소드를 이용해서 키와 값을 추가할 수 있다.
map.put("Key1", "Value1");
map.put("Key2", "Value2");
map.put("Key1", "Value3"); // 기존 값이 덮어쓰여짐
HashMap과 마찬가지로 키가 TreeMap에 없으면 Key-Value 엔트리가 TreeMap에 삽입된다. 만약 동일한 키를 갖는 엔트리가 이미 TreeMap에 존재하면 덮어쓰여진다.
TreeMap에서 Entry 삭제
map.remove("Key1"); // 키에 해당하는 엔트리 삭제
map.clear(); // 전부 삭제TreeMap에서 엔트리를 삭제하려면 remove() 메소드를 이용하면된다. remove() 메소드에 삭제하려는 엔트리의 키를 입력해주면, 키에 해당하는 엔트리가 TreeMap에서 제거된다.
만약 모든 데이터를 다 삭제하려면 clear() 메소드를 이용하면 된다.
TreeMap에서 값 출력
map.get("Key"); // "Key"에 해당하는 값 리턴
map.firstEntry(); // 저장된 엔트리 중 가장 키 값이 작은 엔트리 리턴
map.firstKey(); // 저장된 엔트리 중 가장 작은 키 리턴
map.lastEntry(); // 저장된 엔트리 중 키 값이 가장 큰 엔트리 리턴
map.lastKey(); // 저장된 엔트리 중 가장 큰 키 리턴TreeMap에서 값을 얻어오기 위해서는 get() 메소드를 이용하면된다. get() 메소드에 키를 입력하면 키에 해당하는 엔트리의 값이 리턴된다.
TreeMap은 단순히 키와 값을 얻어오는 것 이외에 최대/최소 값을 얻어올 수 있는 메소드를 제공한다. firstEntry()와 firstKey() 메소드는 TreeMap 내부의 레드-블랙 트리에서 가장 작은 키에 해당하는 엔트리와 키를 리턴한다. 반대로 lastEntry()와 lastKey() 메소드는 가장 큰 키에 해당하는 엔트리와 키를 리턴한다.
TreeMap 순회
// Entry Set으로 순회
for (Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getValue());
}
// Key Set으로 순회
for (String k : map.keySet()) {
String value = map.get(k);
System.out.println(value);
}
// Entry Iterator로 순회
Iterator<Entry<String, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
Map.Entry<String, String> entry = entries.next();
System.out.println(entry.getValue));
}
// Key Iterator로 순회
Iterator<String> keys = map.keySet().iterator();
while(keys.hasNext()){
String key = keys.next();
String value = map.get(key);
System.out.println(value);
}다른 Map 객체와 마찬가지로 for each 구문을 이용해서 TreeMap 전체를 순회할 수 있다.
댓글