Collection 정리 - Implementations

Implementations

관련 글

java docs - https://docs.oracle.com/javase/tutorial/collections/implementations/index.html

상위 목록(collection 정리) - https://jurogrammer.tistory.com/172

서론

구현체는 collections를 저장하는데 사용되는 data objects를 의미합니다. 이 구현체들은 앞서 말한 interfaces를 구현했죠.

종류

다음 구현체들에 대해 설명할 예정입니다.

• General-purpose implementations
  • 일상적으로 사용할 수 있는 구현체들입니다.
• Special-purpose implementations
  • 특수한 상황에서 사용하는 구현체들입니다.
  • 일반적이지 않은 성능적인 특징, 제한적인 사용 그리고 동작을 보여줍니다.
• Concurrent Implementations
  • high concurrency를 지원하는 구현체들입니다.
  • 단일 스레드의 성능을 낮추는 대신, 동시성을 지원해줍니다.
  • java.util.concurrent 패키지에 일부 있습니다.
• Wrapper implementations
  • 기능을 제한하거나 추가하기 위한 구현체입니다.
  • General-purpose implementations를 조합하여 사용합니다.
• Convenience implementations
  • 작은 구현체로, static factory methods를 통해 사용가능합니다.
  • 특별한 collections를 위해 편리하고 효율적인 구현체들을 제공합니다.
  • 예시로, singleton sets같은 것이 있습니다.
• Abstract implementations
  • skeletal implementaions입니다.
  • custom implemenations의 생성을 효율화시켜 줍니다.

General-purpose implementaions 요약 테이블

• SortedSet, Sorted Map interface는 table에 row에 표기가 되지 않았습니다.
  • 각각 Set, Map row에 표기되어 있는 TreeSet, TreeMap 구현체를 지닙니다.
• 일반적인 목적의 Queue 구현체는 2가지가 있습니다.
  • LinkedList
    • List의 구현체이기도 합니다.
    • FIFO를 지원해줍니다.
  • PriorityQueue
    • table에서 생략되었습니다.
    • elements를 element의 값에 따라 정렬합니다.

특징

각각의 general-purpose implementations는 각각 구현한 인터페이스에서 optional operation을 제공해줍니다.

• 모두 null elements, keys, values를 지원합니다.
• 모두 동기화되있지 않습니다.(None are synchronized, (thread-sfafe)
• fail-fast interator를 지닙니다.
  • iteration을 돌 동안, 잘못된 concurrent modification감지하고 곧바로 exception을 발생시키죠.
• 모두 Serializable과 public clone method를 지원해줍니다.

general-purpose implementations이 unsynchronized로 구현된 이유

• 주로 동기화가 도움이 되지 않은 환경에서 컬렉션을 사용하기 때문.
• 환경의 종류
  • single-threaded로만 사용
  • read-only로만 사용
  • 자체적으로 동기화 기능을 지닌 아주 큰 데이터 object를 사용.
• API 설계 관점에서 봤을 때, 사용하지 않을 미래를 위해 동기화로 인한 오버헤드를 부담하는 것은 좋지 않기 때문에 Vector와 HashTable은 legacy라 부를 수 있음. 또한, 필요치 않은 동기화는 특정 상황에서 deadlock을 야기시킬 수 있기에 더욱 문제가 됨.

thread-safe collections가 필요하다면.

• synchronization wrappers를 이용하도록 하는 것이 좋음(wrapper implementaions에 자세히 설명)
• 어떠한 collection도 synchronized collection으로 변경해줌.
• 또는 java.util.concurrent 패키지에서 concurrent 구현체도 제공해줌.
  • BlockingQueue 인터페이스의 구현체들
    • Queue를 extends함.
  • ConcurrentMap interface의 구현체들
    • Map을 extends함

interface관점으로 생각하라.

• 이 섹션에 programming example이 없는 이유이기도 함.
• 구현체를 특정지어서 해당 구현체에 종속적되도록 프로그램을 만들지 말고, 인터페이스에 의존하라는 뜻.
• 어차피 구현체의 선택은 성능에만 영향을 줌. 즉, 상황에 따라 적절한 구현체를 선택할 수 있도록 인터페이스에 의존.

마무리

앞으로 구현체에 대해 설명할 것이며, 구현체의 성능은 각 operations별로 시간복잡도를 이용하여 표현할 것입니다.

명심해야 할 것은! 정렬에 대한 성능 지표엔 한계가 존재합니다. 즉, 실제 측정에서 일반적으로 느리다고 생각한 것이 빠를 수 있죠. 따라서, 의심스러울 땐 성능을 측정하세요!