[Java] NavigableMap

출처

ChatGPT

---

NavigableMap은 자바 컬렉션 프레임워크에서 정렬된 키-값 쌍을 저장하고, 양방향 탐색 기능을 제공하는 인터페이스이다. NavigableMap은 SortedMap 인터페이스를 확장하여, 상위 또는 하위 값을 찾고 서브맵을 생성하는 등, 더 많은 탐색 관련 기능을 제공한다.

• 관련 글 -> [Java] SortedMap

 

1. NavigableMap의 주요 특징

정렬된 맵

NavigableMap은 키가 항상 정렬된 순서로 저장된다. 기본적으로 자연 순서(Natural Ordering)에 따라 정렬되지만, 사용자가 제공한 Comparator를 통해 사용자 정의 순서로 정렬할 수도 있다.

• 관련 글 -> [Java] 자연 순서 Natural Ordering

양방향 탐색

NavigableMap은 키와 값을 기준으로 상위 또는 하위 방향으로 탐색할 수 있다. 예를 들어, 가장 가까운 상위 키나 하위 키를 찾는 메서드를 제공한다.

서브맵 생성

키의 범위를 지정해 서브맵을 생성할 수 있다. 이를 통해 특정 구간에 속한 키-값 쌍들만을 포함하는 부분 맵을 얻을 수 있다.

 

2. NavigableMap을 구현한 클래스

TreeMap 

NavigableMap 인터페이스를 구현한 대표적인 클래스이다. TreeMap은 내부적으로 레드-블랙 트리를 사용해 정렬된 맵을 구현한다.

• 관련 글 -> [자료 구조] 레드-블랙 트리 Red-Black Tree

 

3. NavigableMap의 주요 메소드

1. 범위 탐색 메소드

lowerEntry(K key)

주어진 키보다 작은, 가장 큰 키-값 쌍을 반환한다. 키가 없다면 null을 반환한다.

floorEntry(K key)

주어진 키와 같은 값이거나, 작은 키-값 쌍들 중 가장 큰 값을 반환한다. 

ceilingEntry(K key)

주어진 키보다 같은 값이거나, 큰 키-값 쌍들 중 가장 작은 값을 반환한다.

highterEntry(K key)

주어진 키보다 작은 키-값 쌍을 반환한다.

 

 

이 메소드들은 양방향 탐색을 지원하는 주요 메소드들로, 특정 키에 대해 상위 또는 하위 방향으로 가장 가까운 키를 찾는 데 사용된다.

2. 서브맵 메소드

subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusiive)

주어진 범위 안에 포함된 키-값 쌍으로 이루어진 서브맵을 반환한다.

headMap(K toKey, boolean inclusive)

주어진 키보다 작은 키-값 쌍을 포함하는 서브맵을 반환한다.

tailMap(K fromKey, boolean inclusive)

주어진 키보다 큰 키-값 쌍을 포함하는 서브맵을 반환한다.

 

 

서브맵 메소드는 특정 범위에 속한 요소들만을 가져오는 데 유용하다. 이 메소드들은 범위 기반 조회를 가능하게 한다.

3. 내림차순 정렬 메소드

descendingMap()

맵의 키-값 쌍을 내림차순으로 정렬한 새로운 맵을 반환한다.

descendingKeySet()

키만 내림차순으로 정렬한 navigableSet을 반환한다.

 

 

descendingMap()을 사용하면 NavigalbeMap을 내림차순으로 정렬된 새로운 맵으로 변환할 수 있다. 원래의 맵에는 영향을 미치지 않고, 내림차순으로 순회할 수 있다.

4. 기타 메소드

pollFirstEntry()

맵의 첫 번째(가장 작은 키-값 쌍)를 제거하고 반환한다.

pollLastEntry()

맵의 마지막(가장 큰 키-값 쌍)을 제거하고 반환한다.

 

 

이 메소드들은 가장 작거나 가장 큰 요소를 제거하는 데 사용된다. 이는 큐의 작업처럼 동작하며, 제거된 키-값 쌍을 반환한다.

 

4. NavigableMap의 주요 메소드 사용 예시

다음은 TreeMap을 사용해 NavigableMap의 주요 메소드들을 사용하는 예시이다.

import java.util.*;

public class NavigableMapExample {
    public static void main(String[] args) {
        NavigableMap<String, Integer> treeMap = new TreeMap<>();
        
        // TreeMap에 요소 추가
        treeMap.put("apple", 10);
        treeMap.put("banana", 20);
        treeMap.put("cherry", 30);
        treeMap.put("date", 40);
        treeMap.put("elderberry", 50);

        // 상위/하위 탐색 메서드 예시
        System.out.println("Lower entry than 'cherry': " + treeMap.lowerEntry("cherry"));
        System.out.println("Floor entry for 'cherry': " + treeMap.floorEntry("cherry"));
        System.out.println("Ceiling entry for 'cherry': " + treeMap.ceilingEntry("cherry"));
        System.out.println("Higher entry than 'cherry': " + treeMap.higherEntry("cherry"));

        // 서브맵 예시
        NavigableMap<String, Integer> subMap = treeMap.subMap("banana", true, "date", true);
        System.out.println("\nSubMap from 'banana' to 'date': " + subMap);

        // 내림차순 맵 예시
        NavigableMap<String, Integer> descendingMap = treeMap.descendingMap();
        System.out.println("\nDescending Map: " + descendingMap);

        // 첫 번째와 마지막 요소 제거
        Map.Entry<String, Integer> firstEntry = treeMap.pollFirstEntry();
        System.out.println("\nFirst entry removed: " + firstEntry);
        Map.Entry<String, Integer> lastEntry = treeMap.pollLastEntry();
        System.out.println("Last entry removed: " + lastEntry);

        // 현재 TreeMap 상태
        System.out.println("\nCurrent TreeMap: " + treeMap);
    }
}

 

출력 결과

Lower entry than 'cherry': banana=20
Floor entry for 'cherry': cherry=30
Ceiling entry for 'cherry': cherry=30
Higher entry than 'cherry': date=40

SubMap from 'banana' to 'date': {banana=20, cherry=30, date=40}

Descending Map: {elderberry=50, date=40, cherry=30, banana=20, apple=10}

First entry removed: apple=10
Last entry removed: elderberry=50

Current TreeMap: {banana=20, cherry=30, date=40}

 

5. NavigableMap의 탐색과 서브맵 기능

NavigableMap의 가장 큰 장점은 양방향 탐색과 서브맵 기능이다.

• 양방향 탐색은 상위 또는 하위 키를 찾고, 범위를 설정해 조회하는 데 매우 유용하다. 예를 들어, 특정 키보다 작거나 같은 값, 혹은 큰 값들을 쉽게 찾을 수 있다.
• 서브맵 기능은 특정 범위에 해당하는 키-값 쌍들을 쉽게 추출할 수 있으며, 이를 통해 범위 기반 조회나 작업을 효율적으로 수행할 수 있다.

 

6. NavigableMap을 활용하는 경우

1. 범위 기반 탐색

NavigableMap은 키 값의 범위가 중요한 경우에 유용하다. 예를 들어, 날짜를 키로 사용해 일정 범위의 데이터를 가져오는 등의 작업에 적합하다.

2. 정렬된 데이터 관리

키가 항상 정렬된 상태를 유지해야 하는 경우에 유용하다. 이를 통해 데이터를 정렬된 순서로 조회하거나 특정 구간의 데이터만 효율적으로 다룰 수 있다.

3. 우선순위 기반 데이터 관리

내림차순 또는 특정 순서를 유지하며 데이터를 관리하는 데 유용하다. 예를 들어, 우선순위가 높은 작업을 먼저 처리하는 큐로 사용할 수 있다.

 

7. NavigableMap과 SortedMap의 차이점

NavigableMap은 SortedMap의 확장형으로, 추가적인 탐색 기능을 제공한다. SortedMap은 기본적인 정렬과 서브맵 기능을 제공하지만, NavigableMap은 상위/하위 탐색, 내림차순 조회, 첫 번째/마지막 항목 제거와 같은 더 많은 기능을 제공한다.

특징	SortedMap	NavigableMap
정렬	키가 항상 정렬된 상태	키가 항상 정렬된 상태
서브맵 기능	서브맵 제공	서브맵 제공
상/하 탐색	제공 안 함	lower(), floor(), ceiling(), higher() 제공
내림차순 맵	제공 안 함	descendingMap() 제공
요소 제거	제공 안 함	pollFirstEntry(), pollLastEntry() 제공

 

• 관련 글 -> [Java] SortedMap

 

8. 결론

NavigableMap은 정렬된 맵의 기능을 더욱 확장한 인터페이스로, 양방향 탐색과 범위 기반의 서브맵을 제공하여 데이터를 더 효율적으로 관리할 수 있게 해준다. TreeMap은 NavigableMap의 대표적인 구현체로, 이진 탐색 트리 기반의 성능과 정렬된 맵의 장점을 모두 제공한다.