HackerRank의 Maximum Subarray Sum 풀다가 TreeSet 간단히 정리.

  • NavigableSet 구현체이므로 (SortedSet에는 없는) navigation methods를 추가로 제공.
  • 주어진 대상과 근접한 값을 찿아내는 lower, floor, ceiling, higher 같은 것들이 그 메서드.

ordering

  • 이렇게 근접한 것을 빠르게 찾아내기 위해 원소들을 정렬상태로 유지함.
  • 정렬에는 2가지 방법 사용.
  • 기본 연산(add, remove, contains)에 대해 log(n) 보장.
  • 정렬 상태 유지를 생각하면 어쩌면 당연.

synchronization

Note that this implementation is not synchronized.

  • 만약, 여러 스레드가 동시에 이 컬렉션에 접근하고,
  • 한 개 이상의 스레드가 이를 수정하려 한다면,
  • synchronized 처리가 필요함.
  • 아래와 같이 “wrapped”로 만드는 것도 방법.
  • 만약 이렇게 한다면 생성 시점에 하는 것이 가장 좋음.
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

fail-fast behavior

  • 당연하게도(?) iterator가 반환하는 iterator는 fail-fast.
  • 즉, iterator가 만들어지고 난 뒤, iterator 자신의 remove 메서드를 통하지 않고 수정된다면, ConcurrentModificationException 예외 던져짐.

Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

  • 주의할 것은, 동기화되지 않은 동시 수정 시 fail-fast 보장이 실패할 수 있음.
  • 문서에서는 단지 버그를 감지하는 메커니즘으로만 사용하라고 함.
  • 이 예외에 의존해서 정확성(correctness)을 기대하는 것은 X.