Collections

• 컬렉션 구현은 주로 성능에 관련된 개발자의 의도를 전달한다. 컬렉션 사용과 커뮤니케이션을 위한 코드 작성 사이에는 밀접한 관련이 있다.

선형 탐색이 충분히 빠르다면 일반적인 컬렉션을 사용해도 되나, 컬렉션의 크기가 너무 커진다면 키를 통해 원소에 접근하는 것이 나을 수도 있다 생각할 수 있을 것이다.

Collection의 의미

• 여러 값을 가진 객체
  • 컬렉션이 별도의 객체라는 사실은 중요하지 않고, 어떤 객체인가? 또는 컬렉션이 가리키는 객체가 어떤 것인가가 중요하다.
  • 자바에서는 컬렉션을 별도의 객체로 인식하므로, 여러 값을 가진 변수라는 정체성이 희미하다.
  • 컬렉션은 여러 값을 가진 변수이기도 하지만, 객체이기도 하다.
• 인자로 전달 가능한 객체
  • 참조 호출의 효과가 나타나서, 어떤 메소드에서 컬렉션 객체의 값을 변경 (즉 원소 추가나 삭제 등)하면 Caller에서도 그 효과가 나타난다.
  • 컬렉션이 수정되는 곳을 예측하기 어려운 상황을 피하기 위해 몇 가지 convention이 있다.
• 수학적 집합
  • 객체의 모임

Issues

• 컬렉션 사용시 가장 일반적인 인터페이스를 사용해서 선언하고 구체적인 구현 클래스를 사용하는 것이 좋다.

• 크기
  • 배열과는 다르게 컬렉션은 중간에 크기 수정 가능
• 순서
  • 원소의 순서가 의미가 있거나 외부에서 순서에 대한 정보가 필요한 경우 순서 정보를 보전하는 컬렉션을 사용
• Uniqueness
  • 일부 연산의 경우, 어떤 원소가 컬렉션에 속해있는지 여부만 중요한 경우도 있지만, 다른 경우 어떤 원소가 몇 번 나타나는지 중요한 경우도 있다.
• 컬렉션의 선택
  • 성능에 관한 프로그래머의 의도를 전달한다.

성능에 관련된 결정 사항들을 명확히 표현해야 한다. 성능을 좋게 하려면 대부분의 경우, 가독성이나 유연성과 같은 코드의 다른 품질을 희생해야 한다. 중요한 것은 이러한 희생을 최소화하는 것이다.

인터페이스

• 배열: 가장 단순하지만 가장 유연하지 못한 컬렉션. 크기가 고정되어 있고 원소 접근 방법이 빠르다.
• Iterable: 기본적인 컬렉션 인터페이스로, 순차 탐색을 지원
• Collection: 원소 추가, 제거 및 원소가 존재하는지에 대한 함수를 지원
• List: 원소의 순서가 의미가 있으며, 컬렉션 상의 위치를 통해 원소에 접근 가능
• Set: 중복된 원소가 없는 컬렉션
• SortedSet: 중복 원소가 없으며, 원소 간의 순서가 정해진 컬렉션
• Map: 키에 의해 원소를 저장하고 접근하는 컬렉션

배열

가장 단순한 컬렉션 인터페이스로, 다른 컬렉션과의 변환이 복잡하다. 배열의 크기는 선언시 고정된다.

• 단순한 연산의 경우, 다른 컬렉션에 비해 시간, 공간 모든 면에서 효율적이다. 단순한 연산이면서 성능이 중요한 경우 배열을 사용해도 좋다.

Iterable

어떤 변수를 Iterable로 선언하는 것은, 그 변수가 여러 개의 값을 가지고 있음을 말한다. 단, 지원하는 기능은 순차적인 탐색 뿐이며 기본적인 컬렉션 크기를 알아낼 수 있는 메소드는 지원하지 않는다.

Collection

Iterable을 상속하며, 원소 추가 / 삭제 / 검색 / 크기 측정 등의 메소드를 추가로 지원한다.

List

Collection을 기반으로 원소 간에 정해진 순서를 부여한 것이다.

• 따라서 List를 사용하면 컬렉션 상에서의 인덱스를 통해 어떤 원소를 접근할 수 있다. 컬렉션 원소 사이에 순서가 의미가 있는 경우 List를 사용하는 것이 적합하다.

Set

중복 원소를 허용하지 않는 컬렉션이며 원소 간에 순서가 없다.

• Set은 어떤 특정 원소가 몇번 나타나는지에 대한 메소드를 지원하지 않는다.

SortedSet

중복 원소를 허용하지 않으면서 원소 간의 순서가 의미가 있는 컬렉션이다.

Map

키를 통해 원소를 접근하며, 원소 간의 순서는 보장되지 않는다.

구현

어떤 컬렉션 인터페이스에 대한 구현체를 선택하는 것은 성능을 결정하는 중요요소 이다.

• 컬렉션 인터페이스를 구현한 클래스를 선택할 때 고려해야 할 요소는 컬렉션의 크기이다. 수백만 개를 저장할 경우나 2~3개를 저장할 때는 분명히 선택이 달라질 것이다.

• ArrayList
  • 이 구현 클래스를 사용하면서 문제되는 부분은, 크기가 커지면서 성능이 저하되는 contains 메소드나, remove 메소드 등이다. 만약 이 부분이 문제가 된다면 HashSet 을 사용하는 것을 고려해볼 수 있다.
• List
  • 이 인터페이스를 구현한 구현 클래스는 ArrayList 나 LinkedList 이다.
  • ArrayList는 원소 접근이 빠르며, 추가 및 제거가 느리다.
  • LinkedList는 원소 접근은 느리지만 추가 및 삭제가 빠르다.
    • 원소 변경이 잦은 경우 LinkedList 를 사용하는 것도 고려해볼 수 있다.
• Set
  • 이 인터페이스를 구현한 구현 클래스는 HashSet, LinkedHashSet, TreeSet 이다.
  • HashSet은 가장 빠르지만 원소 간의 순서를 보장해주지 않는다.
  • LinkedHashSet은 원소 간의 순서는 보장해주지만, HashSet에 비해 성능이 열세이다.
    • 원소 간의 순서가 필요해지면 이 클래스를 사용하는 것을 고려해볼 수 있다.
  • TreeSet은 Comparator 에 따라 원소를 정렬해주지만, 원소 추가/삭제 시간이 컬렉션의 크기에 따라 커진다.
• Map
  • 이 인터페이스를 구현한 구현 클래스는 HashMap, LinkedHashMap, TreeMap 이다.
  • HashMap은 가장 빠르고 단순한 Map의 구현 클래스이다.
  • LinkedHashMap은 LinkedHashSet과 비슷하게, 원소 간의 순서를 보장해준다.
  • TreeMap은 TreeSet과 비슷하게, 순차 열람이 가능하지만 원소 추가/삭제 시간이 컬렉션의 크기에 따라 커진다.
    • SortedMap의 구현 클래스이다.

검색

• indexOf 메소드에 걸리는 시간은 리스트의 크기에 비례한다. 단, 원소가 정렬되어 있다면 이진 검색을 통해 log2n에 비례하는 시간에 검색을 마칠 수 있다.

정렬

• 이진 검색과는 다르게, 정렬은 배열로 복사되어 정렬된 다음 다시 본래 컬렉션으로 복사하므로 ArrayList나 LinkedList나 속도는 비슷하다.

---