Java 의 SortedMap, NavigableMap | 이영수 개발 블로그

주제

Java 에선, 대부분의 경우는 HashMap 을 사용한다.
Hashing 을 통해 O(1) 을 기대할 수 있고, O(1) 이므로 정렬이 크게 필요한 경우가 없기 때문이다.

하지만, 특정 요구사항에 따라 MAP 에서 키를 정렬해서 처리해야하는 경우도 존재한다.

특정 범위의 데이터를 한번에 조회
만료 처리
근접한 요소 탐색

이때 사용할 수 있는게 SortedMap, NavigableMap 이다.

SortedMap

Java 1.2 에서 나온 인터페이스

SortedMap 은 키가 정렬된 상태로 유지되는 Map 이다.
-> 정렬이 되었으므로, 범위 연산이 가능해진다.

headMap(toKey) : toKey 미만 모든 엔트리 View 반환
tailMap(fromKey) : fromKey 이상 모든 엔트리 View 반환
subMap(fromKey, toKey) : fromKey 이상 ~ toKey 미만 모든 엔트리 View 반환
firstKey() : 최솟값 키
lastKey() : 최대값 키

왜 O(log n)?
TreeMap 내부는 Red-Black Tree 로 구현되어있다.
균형 트리이므로, 최대 log n 번 비교하면 결과를 보장한다.

엔트리 view?
원본 Map 에서 조건에 맞는 요소들만 반환한 값이다. 복사가 아니라, 참고다.
즉, view 에 put 나 remove 하면 원본에서도 반영된다.

headMap, tailMap 이 없다면?

특정 시간이 지나면, 데이터를 삭제하는 로직을 작성한다고 가정하면?

List<Map.Entry<LocalDateTime, Task>> expired = new ArrayList<>();
  for (var entry : timeTable.entrySet()) {
      if (entry.getKey().isAfter(checkTime)) {
          break;
      }
      expired.add(entry);
  }
 
for (var entry : expired) {
  timeTable.remove(entry.getKey());
}

Iterator<Map.Entry<LocalDateTime, Task>> it = timeTable.entrySet().iterator();
  while (it.hasNext()) {
      Map.Entry<LocalDateTime, Task> entry = it.next();
      if (entry.getKey().isAfter(checkTime)) {
          break;
      }
      process(entry);
      it.remove();
}

보일러 플레이트 코드가 필요하다.
(순회 도중 삭제를 하면 예외 발생하므로, 순회가 끝난후 처리)

headMap 을 사용한다면?

timeTable.headMap(checkTime).clear();

로 위의 코드와 동일하게 동작한다.
즉, 코드를 간결하게 유지할 수 있다.

###NavigableMap

Java 1.6 에서 나온 인터페이스
SortedMap 에서 부족한 기능들을 보완해주는 인터페이스이다.

headMap, tailMap 에 매개변수 추가 ( true 면 등호(=) 포함, false 면 미포함 )
floorKey, ceilingKey : 근접 탐색 제공 (key 이하/이상 중에 가장 작은/큰 키)
firstEntry, lastEntry : 최소, 최대키에 대한 엔트리

참고

주제