컬렉션 프레임워크

컬렉션은 다수의 데이터, 프레임워크는 표준화 된 프로그래밍 방식을 의한다.
즉, 컬렉션 프레임워크란 데이터 군을 저장하는 클래스들을 표준화한 설계를 뜻한다.

컬렉션 프레임워크의 핵심 인터페이스와 특징은 다음과 같다.

인터페이스	특징	구현 클래스
List	순서가 있으며, 중복된 요소를 허용	ArrayList, LinkedList, Vector, Stack
Set	순서가 없으며, 중복된 요소를 허용하지 않음	HashSet, LinkedHashSet, TreeSet
Map	순서가 없으며, 키-값 쌍을 저장함, 각 키는 중복된 요소를 허용하지 않고 값은 중복을 허용함.	HashMap, LinkedHashMap, TreeMap, Properties

선택 기준

Collection 선택 기준
│
├── List
│   │   ├── 순차적 추가/삭제 → ArrayList
│   │   └── 중간 요소 빈번 조작 → LinkedList
│   │   
│   │
│   └── 중복 요소 필요?
│       └── O → List에서는 중복 요소 허용
│
├── Set
│   │
│   ├── 정렬 필요?
│   │   ├── O → TreeSet
│   │   └── X
│   │       ├── 입력 순서 유지?
│   │       │   ├── O → LinkedHashSet
│   │           └── X → HashSet
│   │
│   └── 중복 요소 필요?
│       └── X → Set에서는 중복을 허용하지 않음
│
└── Map
    ├── 처음부터 키값 쌍 필요?
    │   └── O → Map 사용
    │
    ├── 정렬 필요?
        ├── O → TreeMap
        └── X
            ├── 입력 순서 유지?
                ├── O → LinkedHashMap
                └── X → HashMap    

List 인터페이스

List는 중복과 저장순서를 유지하는 컬렉션을 구현하는데 사용된다.

List와 Array과 차이점은 주요 차이점은 다음과 같다.

1. 크기 유연성

• 배열: 고정된 크기
• List: 동적으로 크기 조정 가능

2. 제네릭 지원

• 배열: 기본적으로 제네릭 미지원
• List: 제네릭을 완전히 지원하여 타입 안전성 제공

ArraysList

ArrayList는 데이터의 저장순서를 유지하고 중복을 허용한다.
단, 중간에 요소를 추가/삭제할 때 메모리 재할당이 발생하기 때문에 속도가 느리다.

용량을 변경해야 하는 경우, 데이터를 복사해야 하므로 효율성이 떨어진다.

LinkedList

LinkedList는 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성되어 있다.

각 요소(노드)는 데이터와 다음 노드를 가리키는 참조로 구성되어 있어,
ArrayList와 달리 삽입/삭제 시 메모리 재할당 없이 빠르게 수행할 수 있다.

그래서 무엇을 선택해야 하는가?

		// 제네릭을 사용하여 타입 지정
        ArrayList<String> a1 = new ArrayList<>(2_000_000);  // 추가할 데이터의 개수를 고려해 크기 지정.
        LinkedList<String> ll = new LinkedList<>();

        System.out.println("= 순차적으로 추가하기 =");
        System.out.println("ArrayList :" + add1(a1) + "ms");
        System.out.println("LinkedList :" + add1(ll) + "ms");
        System.out.println();

        System.out.println("= 중간에 추가하기 =");
        System.out.println("ArrayList :" + add2(a1) + "ms");
        System.out.println("LinkedList :" + add2(ll) + "ms");
        System.out.println();

        System.out.println("= 중간에서 삭제하기 =");
        System.out.println("ArrayList :" + remove2(a1) + "ms");
        System.out.println("LinkedList :" + remove2(ll) + "ms");
        System.out.println();

        System.out.println("= 순차적으로 삭제하기 =");
        System.out.println("ArrayList :" + remove1(a1) + "ms");
        System.out.println("LinkedList :" + remove1(ll) + "ms");
    }

    // 순차적으로 리스트에 요소를 추가하는 메서드
    public static long add1(List<String> list){
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1_000_000; i++) {
            list.add(i + ""); // 요소를 끝에 추가
        }
        long end = System.currentTimeMillis();
        return end - start;  // 소요 시간 리턴
    }

    // 중간에 요소를 추가하는 메서드 (500번째 위치에 추가)
    public static long add2(List<String> list){
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10_000; i++) {
            list.add(500, "X"); // 중간에 삽입
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

    // 순차적으로 리스트에서 요소를 삭제하는 메서드 (끝에서부터 삭제)
    public static long remove1(List<String> list){
        long start = System.currentTimeMillis();
        for(int i = list.size() - 1 ; i >= 0; i--) {
            list.remove(i); // 끝에서부터 하나씩 삭제
        }
        long end = System.currentTimeMillis();
        return end - start;
    }

    // 중간에서부터 요소를 삭제하는 메서드 (0번부터 삭제)
    public static long remove2(List<String> list) {
        long start = System.currentTimeMillis();
        for(int i = 0 ; i < 10_000; i++) {
            list.remove(i); // 앞에서부터 삭제
        }
        long end = System.currentTimeMillis();
        return end - start;
    }
}

결과값 

= 순차적으로 추가하기 =
ArrayList :78ms
LinkedList :158ms

= 중간에 추가하기 =
ArrayList :1625ms
LinkedList :17ms

= 중간에서 삭제하기 =
ArrayList :1396ms
LinkedList :193ms

= 순차적으로 삭제하기 =
ArrayList :7ms
LinkedList :24ms

위 코드와 실행 결과를 보면 ArrayList와 LinkedList의 강점은 다르다.

순차적으로 추가/삭제 할 경우에는 ArrayList가 LinkedList보다 빠르다.

그러나, 중간 데이터를 추가/삭제 할 경우에는 LinkedList가 ArrayList보다 빠르다.

그렇다면, 접근 시간은 같을까?

public static void main(String[] args) {
        ArrayList al = new ArrayList(1_000_000);
        LinkedList ll = new LinkedList();
        add(al);
        add(ll);

        System.out.println("=접근 시간 테스트=");
        System.out.println("ArrayList : " + access(al));
        System.out.println("LinkedList : " + access(ll));
    }

    public static void add(List list) {
        for (int i = 0; i < 100_000; i++) {
            list.add(i + "");
        }
    }

    public static long access(List list) {
        long start = System.currentTimeMillis();
        for (int i = 0; i < 10_000; i++) { list.get(i);}
        long end = System.currentTimeMillis();
        return end - start;
    }
    
   결과값
   
=접근 시간 테스트=
ArrayList : 0
LinkedList : 234

LinkedList는 위 글에서 설명한 것처럼 불연속적으로 존재하므로, 차례대로 노드를 따라가야 원하는 값을 얻을 수 있다.

즉, 저장해애햐는 데이터의 개수가 많을 수록 접근 시간도 길어진다는 것이다.

결론

데이터의 개수가 변하지 않으면 ArrayList를, 데이터 개수의 변경이 잦다면 LinkedList를 쓰자

Set 인터페이스

Set은 중복을 허용하지 않는 컬렉션을 구현하는데 사용된다.

HashSet

HashSet은 중복된 요소를 저장하지 않는다.
그러나 저장순서를 유지하지 않는다.

Set<String> basicSet = new HashSet<>();
basicSet.add("Apple");
basicSet.add("Banana");
basicSet.add("Apple"); // 중복 무시됨
System.out.println(basicSet.size()); // 2

HashMap의 요소 저장 과정은 다음과 같다.
1. 객체의 hashCode() 메서드로 해시값 계산
2. 해시값을 기반으로 버킷(Set의 데이터를 저장하는 배열) 결정
3. 같은 버킷에 이미 요소가 존재하면 equals() 메서드로 비교

주의점으로는 사용자 정의 Entity 클래스를 저장할 경우, 같은 요소가 저장될 수 있다.
이유는 add메서드가 equals()와 hashCode()를 호출하기 떄문에 오버라이딩 해야 한다.

public boolean equlas(Object obj){
	Student s  = (Student)obj;
    return age == s.age && name == s.name
}

public int hashCode() {
	return Objects.hahs(value)
}

LinkedHashSet

중복은 방지하되, 입력 순서를 유지하는 클래스다.

Set<String> orderedSet = new LinkedHashSet<>();
orderedSet.add("First");
orderedSet.add("Second");
orderedSet.add("First"); // 중복 무시
// 입력 순서 그대로 유지
orderedSet.forEach(System.out::println);

TreeSet

이진 검색 트리 형태로 데이터를 저장하는 클래스이다.
주로 정렬/검색/범위 검색에 높은 성능을 보여준다.

TreeSet은 요소를 삽입할 때마다 자동으로 정렬된다.

// 정렬과 범위 검색이 필요한 경우
TreeSet<Integer> sortedSet = new TreeSet<>();
sortedSet.add(5);
sortedSet.add(3);
sortedSet.add(7);

// 자동 정렬
System.out.println(sortedSet); // [3, 5, 7]

// 범위 검색 기능
System.out.println(sortedSet.headSet(5)); // [3]
System.out.println(sortedSet.tailSet(5)); // [5, 7]

Map 인터페이스

Map은 키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션을 구현하는데 사용된다.

HashMap

Map의 특징과 더불어 해싱을 사용하므로, 많은 양 데이터를 검색하는데 있어서 뛰어난 성능을 가진다.
(해싱 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%85%8C%EC%9D%B4%EB%B8%94)

TreeMap

이진 검색 트리 형태로 키값쌍을 저장하는 클래스이다.
TreeSet과 동일하게 검색/정렬에 좋은 성능을 보여준다.

단순 검색 같은 경우 HashMap을, 범위 검색이나 정렬이 필요한 TreeMap을 쓰자

---

참고자료

• 자바의 정석
• https://akcoding.com/java-tutorial/java-collections-framework/