컬렉션 프레임워크 (Collections Framework)

라이브러리 (Library) : 책. 다른 사람이 미리 만들어 놓은 것을 가져다 쓰기만 하면 됨. 기능만 제공하는 것.

프레임워크 (Framework) : 라이브러리 + 정형화된 체계적인 프로그래밍 방식. 표준화된 프로그래밍 방식. 생산성과 유지보수에 뛰어나다.

컬렉션 프레임워크는 다수의 데이터를 다루기 위해 다양하고 풍부한 클래스들을 제공한다.

 

1. 컬렉션 프레임워크의 핵심 인터페이스 

(0) Collection 인터페이스 : 

컬렉션 클래스에 저장된 데이터를 읽고 추가하고 삭제하는 등 컬렉션 다루는데 가장 기본적인 메소드 정의. 

 

(1) Collection 인터페이스의 List 인터페이스

 : List와 Set을 구현한 클래스들은 서로 많은 공통 부분이 있어서 공통 부분을 다시 뽑아 Collection 인터페이스 정의. 하지만 Map은 전혀 다른 형태로 컬렉션 다루기 때문에 상속 계층도 포함되지 못함.

 - 순서가 있는 데이터 집합. 중복 허용

 - ArrayList, LinkedList, Stack, Vector ...

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=baekmg1988&logNo=20194514561

1) 메소드

 - 추가 : void add(int index, Object element), boolean addAll(int index, Collection c)

 - 읽기 : Obejct get(int index)

 - 객체 인덱스 반환 : int indexOf(Object o) 나 int lastIndexOf(Obejct o) (순방향, 역방향)

 - 삭제 : Object remove (int index) (삭제된 객체 반환)

 - 변경 : Object set(int index, Object element) : index에 element 저장.

 - 정렬 : void sort(Comparator c)

 - 부분 떼어내기 : List subList(int fromIndex, int toIndex)

 

2) ArrayList : 

Vector는 동기화 된 것, ArrayList는 동기화 안된 것. 가장 많이 사용함.

 - 생성자로 ArrayList() : 크기가 10인 ArrayList 생성, ArrayList(Collection c) : 주어진 컬렉션이 저장된 ArrayList생성. ArrayList(int initialCapacity)로 배열 길이 처음에 저장해 줄수도 있음.

 - toArray() 메소드로 ArrayList에 저장된 모든 객체들을 객체 배열로 반환함. 

 - trimToSize()로 빈공간 제거 가능.

 - ArrayList에 저장된 첫번째 객체 부터 삭제하는 경우 배열 복사 발생 하지만 ArrayList에 저장된 마지막 객체부터 삭제하는 경우는 배열 복사 발생하지 않음. 빠르고 다 지워짐.

 

3) LinkedList : 배열의 단점 보완. 크기 변경 할수 없고, 비 순차적인 데이터 추가 삭제시간이 많이 걸린다는 단점 보완.

불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성. 기차에 비유 가능. 따라서 변경에 유리.

 - LinkedList의 단점 :  이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉽지만 이전 요소 접근은 어려움. 데이터의 접근성이 나쁨. (5번째 요소 까지 가려면 한번에 가는것이 아닌 타고타고 건너야 한다.)이 점을 보완한 것이 doubly LinkedList이다. 참조변수 하나 더 추가해 이전 요소 참조 가능하게 한 것일 뿐 나머지는 동일. (더 많이 사용됨. 접근과 이동이 쉬우므로)

 

4) ArrayList와 LinkedList 비교

 - 순차적으로 데이터를 추가 / 삭제 하는 경우 ArrayList가 빠름.  만일 ArrayList의 크기가 충분하지 않으면, 새로운 크기의 ArrayList를 생성하고 데이터 복사하는 일이 발생하므로 순차적으로 데이터 추가해도 ArrayList보다 LinkedList가 빠를 수 있다. 삭제하는 것은 역순으로 빠르게 삭제하므로, ArrayList의 경우 요소들의 재배치 필요하지 않기 때문에 상당히 빠름.

 - 중간 데이터를 추가 / 삭제하는경우에는 LinkedList가 빠름.

 - 읽는 접근시간 :  ArrayList가 빠름. 인덱스가 n인 데이터 주소는 배열에서 배열의 주소 + n*데이터타입의 크기인 반면, LinkedList는 불연속적인 요소들이 연결된 것이라 차례대로 따라가야만 원하는 값을 얻을 수 있음. 접근시간이 LinkedList는 데이터 개수 많아 질 수록 길어지는 단점.

 

(2) Collection 인터페이스의 Set 인터페이스
 : 순서 유지 하지 않는 데이터 집합. 중복 허용하지 않음.

 - HashSet, TreeSet ...

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=baekmg1988&logNo=20194515468

1) 메소드 : Collection 인터페이스와 동일. (contains()로 포함되있는지 확인 가능)

2) HashSet 

 : 가장 대표적인 컬렉션. 저장 순서 유지 하고자 한다면 LinkedHashSet 사용.

- boolean removeAll(Collection c) : 차집합. 주어진 컬렉션에 저장된 모든 객체와 동일한 것들을 HashSe에서 삭제.

- boolean retainAll(Collection c) : 교집합. 주어진 컬렉션에 저장된 객체와 동일한 것만 남기고 삭제.

 * HashSet은 객체를 저장하기 전에 기존에 같인 객체가 있는지 확인. 같은 객체 없으면 저장하고 있으면 저장하지 않는다. -> HashSet의 add 메소드는 equals()와 hashCode()로 중복인지 확인함.

3) TreeSet

: 이진 검색 트리 (binary serach tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션.

중복된 데이터의 저장을 허용하지 않으며, 정렬된 위치에 저장하므로 저장순서를 유지하지도 않음.

LinkedList처럼 여러 노드가 서로 연결된 구조로, 각 노드에 최대 2개 까지 연결 가능.  

범위검색, 정렬에 유리

binary search tree, 이진 검색 트리는 이진 트리 (binary tree)의 한 종류이다. binary search tree는 부모보다 작은 값은 왼쪽, 큰값은 오른쪽에 저장한다. 따라서 첫 번째 저장되는 값은 루트가 되고, Comparable을 구현한 것을 통해서 정렬한다. 따라서 TreeSet에 저장되는 객체가 Comparable을 구현하던가 , TreeSet에게 Comparable을 제공해 비교할 방법을 알려줘야 한다. 아니면 예외 발생. 

이렇게 저장하므로써, 왼쪽노드 -> 부모노드 -> 오른쪽 노드 순으로 읽으면 오름차순으로 정렬 가능.

이렇게 정렬된 상태를 유지하기 때문에, 단일 값 검색과 범위 검색 (3과 7사이 범위 검색 등..)이 매우 빠름.

저장 위치 찾아 저장하기에 삭제하는 경우 LinkedList보다 데이터의 추가 / 삭제 시간은 더 걸림. 대신 배열과 LinkedList에 비해 검색과 정렬기능 뛰어남.

 - 생성자 TreeSet(Comparator comp)를 제공 할 수 있다. 안주면 저장 객체의 Comparable을 이용함.

 - 쓸일있으면 메소드 추가 하겠음.

* 트리 순회 (Tree traversal) : 이진트리의 모든 노드를 한번씩 읽는 것을 트리 순회라고 함.

A. pre order (전위 순회) : 부모노드 -> 자식 왼쪽 노드로 읽는 방법.

B. in order (중위 순회) : 자식 왼쪽 노드 -> 부모노드 -> 오른쪽 노드 순으로 읽는 것. 

C. post order (후위 순회) : 자식 오른쪽 노드 -> 부모노드.

D. 레벨 순회 : 부모부터 자식으로 내려오면서 왼쪽부터 쭉 읽는것. (순서대로 읽는것)

 -> 이진검색트리를 중위순회하면 오름차순으로 정렬됨.

 

(3) Map 인터페이스

 : key와 value의 쌍으로 이루어진 데이터 집합. 순서 유지 x. 키는 중복 허용 x, 값은 중복 허용.

 - HashMap, LinkedHashMap, TreeMap, Hashtable ...

출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=baekmg1988&logNo=20194516618

Hashtable과 HashMap의 차이는 동기화 차이. HashTable은 동기화 되어 있고 HashMap은 동기화 되어 있지 않다.

TreeMap과 HashMap이 핵심.

 

1) 메소드 :

 - 검색 : containsKey(Object key), containsValue(Object value)로 key와 value 객체에 일치하는 객체 있는지 확인 가능.

 - Map을 Set으로 : Set entrySet() : 키와 값을 묶은 것을 set으로 반환함.

 - Map에서 키를 Set으로 따로 뽑음 : Set keySet()

 - value 객체를 Collection으로 따로 뽑음 : Collection values() (값은 중복 허용하기 때문에 Set으로 안뽑음)

 - 추가 : Object put(Object key, Object value), void putAll(Map t)

 - 제거 : Object remove(Object key)

 - 가져오기 : Object get(Object key)

 

2) Map.Entry 인터페이스 

Map인터페이스의 내부 인터페이스. (inner interface). 인터페이스 안에 인터페이스 정의 가능함.

Map에 저장되는 key-value 쌍을 다루기 위해 내부적으로 Entry 인터페이스 저장해 놓음.

객체지향적으로 설계하기 위한 것이므로 Map인터페이스를 구현하는 클래스는 Map.Entry 인터페이스도 구현해야함.

 

3) HashMap 메소드

 - Object get(Object key)로 값 객체 반환하는데, Object getOrDefault (Object key, Object defaultValue)로 저징된 키의 값 반환. 키를 못찾았으면 기본값으로 지정된 객체 반환.

 - Object replace(Object key, Object value), boolean replace(Object key, Object oldValue, Object newValue)로 키의 값을 지정된 객체로 대체하거나, 지정된 키와 객체(oldValue)가 일치 하는 경우에만 새로운 객체(newValue)로 대체.

 * 주의할점 : 키 값을 같은것 여러번 넣는다고 에러 발생 X. value는 마지막 입력값으로 변경.

 

4) 해싱과 해싱함수

해싱이란 해시함수(hash function)을 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있음.

해싱 : 해시함수를 이용해 저장하고 읽어오는것. 

key -> hash function -> hash code(배열의 index)로 인덱스에 맞는 곳으로 이동 -> LinkedList에서 key와 일치하는 data를 찾는다.

* Hash function은 같은 key에 대해서 항상 같은 hash code를 반환해야 한다. 저장하고 읽어올 때 모든 같은 값이 나와야 하기 때문이다. 하지만 서로 다른 key라도 같은 hash code를 가질 수 있다. (배열의 index는 같을 수 있기 때문)

HashTable은 배열 + LinkedList 조합된 형태. 배열의 장점인 접근성과 LinkedList의 장점인 변경 유리함을 합쳐 놓은 것.

 

5) TreeMap

: 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터 저장. 검색과 정렬에 적합. 

검색에 관한한 대부분의 경우에서 HashMap이 TreeMap보다 더 뛰어나기에 HashMap쓰자. 다만 범위 검색이나 정렬의 경우 TreeMap 쓰자.

2. Iterator, ListIterator : Collection 인터페이스에 저장되어 있는 데이터를 읽음. (Map은 못씀)

 - Enumeration은 Iterator의 구버전. 안씀.

 - 컬렉션 클래스에 대해서 iterator() 호출해 Iterator객체를 얻은 다음 주로 while문을 이용해 컬렉션 클래스의 요소 읽어올 수 있음.

(1) 메소드 : 

 - boolean hasNext() : 읽어올 요소가 남아있는지 확인.

 - Object next() : 다음 요소를 읽어 옴.

 - void remove() : next()로 호출한 다음 remove() 호출 해야하는 선택적 기능. next()로 읽어온 요소 삭제함.

 (2) * Iterator객체는 일회용이다! (Stream과 같네.. )

한번 다 썼으면 다시 객체를 새로 얻어와야한다.(Iterator는 변수가 있어서 다음 읽어올 것을 가리키고 있기 때문에 끝까지 가고 나면 더이상 읽을 것이 없어 다시 얻어와야 한다.) 

 - Map인터페이스를 구현한 컬렉션 클래스는 key와 value 쌍으로 저장하고 있기 때문에, iterator 직접 호출 할 수 없고, 대신 keySet()이나 entrySet()과 같은 메소드 통해서 키와 값을 각각 Set의 형태로 얻어 온 후 iterator()를 호출해야 얻을 수 있음.

Iterator it = map.entrySet().iterator();

(3) ListIterator 

: Iterator를 상속 받아 기능 추가한 것. 컬렉션 요소에 접근 할 때, 단방향이 아닌 양방향으로 이동가능.

but ArrayList, LinkedList같이 List인터페이스를 구현한 컬렉션에서만 사용 가능.

->boolean hasPrevious() 메소드로 이전 요소 읽어 올 수 있다. (잘 사용 하진 않음)

 

3. Arrays 클래스

 : 배열 다루는 유용한 메소드들 정의되어 있음. static method 제공. 

(1) toString() : 배열 출력

(2) 배열 복사 - Arrays.copyOf(arr, arr.length), Arrays.copyOfRange(arr, int start, int to)

(3) 배열 채우기 - Arrays.fill(arr, 값) : 배열의 모든 요소를 지정된 값으로 채움.  Arrays.setAll() : 배열 채우는데 사용할 함수형 인터페이스를 매개변수로 받음.

(4) 정렬 - Arrays.sort() , 검색 - Arrays.binarySearch() : 배열에서 지정된 값이 저장된 위치(index) 찾아서 반환. 반드시 배열이 정렬된 상태여야만 올바른 결과를 얻음. linear Search가 아닌 이진검색(Binary Search)로 O(logN)

(5) 배열 비교 - Arrays.equals() , 배열 출력 - Arrays.toString(), Arrays.deepToString() (2차원 배열 이상)

(6) 배열을 List로 : Arrays.asList() (ArrayList의 toArray()와 반대네..)

 

4. Collections 클래스

: Arrays 클래스가 배열과 관련된 메소드를 제공하는 것 처럼, Collections는 컬렉션과 관련된 메소드 제공함. 

fill(), copy(), sort(), binarySearch()와 같은 메소드는 두 클래스에 모두 포함되어 있음.

Collection 인터페이스와 Collections 클래스는 다름. (Collection인터페이스는 List, Set 인터페이스의 부모 인터페이스)

 

(1) 컬렉션의 동기화 
멀티쓰레드 프로그래밍에서는 하나의 객체를 여러 쓰레드가 동시에 접근 할 수 있기 때문에 일관성을 유지하기 위해서는 공유되는 객체에 동기화가 필요함. 

Vector, Hashtable같이 구 버전의 클래스들은 자체적으로 동기화 처리가 되어있는데, 멀티쓰레드 프로그래밍이 아닌 경우 불필요한 기능이 되어 성능을 떨어뜨리는 요인이됨.

따라서 ArrayList, HashMap같은 컬렉션은 동기화를 자체적으로 하지 않고, 필요한 경우에만 Collections 클래스의 동기화 메소드를 이용해 동기화 처리 가능. 

 - Collections.synchronizedList(new ArrayList()); 같이 Collections.synchronized(+컬렉션이름) 통해서 생성 가능.

 

(2) 변경불가 컬렉션 만들기

수정불가. 즉, 읽기전용으로 만들어야 할 때가 있다. 주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다 보면 데이터 손상될 수 있는데, 이를 방지하기 위함.

- Collections.unmodifiableList(List list) 같이 Collections.unmodifiable(+컬렉션이름)통해 생성 가능.

 

(3) 싱글톤 컬렉션 만들기

 단 하나의 객체만 저장하는 컬렉션 만들고 싶은 경우, 매개변수로 저장할 요소 지정하면, 해당 요소를 저장하는 컬렉션 반환함. 그리고 반환된 컬렉션은 변경 불가.

 - static List singletonList(Object o) / static Set singleton(Object o) / static Map singletonMap(Object key, Object value)  (Set의 경우 메소드 이름 주의)

 

(4) 한 종류의 객체만 저장하는 컬렉션 만들기

 컬렉션에 지정된 종류의 객체만 저장할 수 있또록 제한하고 싶을 때, 아래 메소드 사용

Collections.checked(+컬렉션이름) ( Collection c, Class type)

Class type에 지정한 한가지 type만 저장 가능. 다른 타입 넣으면 ClassCastException 발생.

 

(5) Collections 클래스의 메소드

 - Collections.sort() : 배열(array)는 Arrays.sort()사용, 컬렉션은 Collections.sort()사용

 - Collections.addAll(컬렉션, 값들) :컬렉션에 값 추가

 - Collections.rotate(컬렉션, num) : 컬렉션을 오른쪽으로 num만큼 이동.

 - Collections.swap(컬렉션, index1, index2) : index1, index2 교환 

.. shuffle(), 

등등.. 메소드들이 있다.

 

Reference: 

자바의 정석 3rd Edition (도우 출판)