자바의 정석 ch11. 컬렉션 프레임워크

1. 컬렉션 프레임워크

• 컬렉션 프레임워크: 데이터 군을 저장하는 클래스들을 표준화한 설계
• 컬렉션: 다수의 데이터, 즉 데이터의 그룹을 의미
• 프레임웍: 표준화된 프로그래밍 방식

1.1 컬렉션 프레임웍의 핵심 인터페이스

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

컬렉션 프레임웍의 모든 컬렉션 클래스들은 List, Set, Map 중의 하나를 구현하고 있으며, 구현은 인터페이스의 이름이 클래스의 이름에 포함되어있어서 이름만으로도 클래스의 특징을 쉽게 알 수 있도록 되어있다.

List인터페이스

중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현하는데 사용

Set인터페이스

중복을 허용하지 않고 저장순서가 유지되지 않는 컬렉션 클래스를 구현하는데 사용

Map인터페이스

키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용. 키는 중복될 수 없지만 값은 중복을 허용함.

Map.Entry인터페이스

Map인터페이스의 내부 인터페이스이다.

1.2 ArrayList

• List인터페이스를 구현하기 때문에 데이터의 저장순서가 유지되고 중복을 허용한다는 특징을 갖는다.
• 기존의 Vector를 개선한 것. 따라서 Vector보다는 ArrayList를 사용하는 것을 권장
• Object배열을 이용해서 데이터를 순차적으로 저장
  ex. 첫 번째로 저장한 객체는 Object배열의 0번째 위치에 저장되고 그 다음에 저장하는 객체는 1번째 위치에 저장된다. 이런식으로 계속 배열에 순서대로 저장되며, 배열에 더이상 저장할 공간이 없으면 보다 큰 새로운 배열을 생성해서 기존의 배열에 저장된 내용을 새로운 배열로 복사한 다음에 저장된다.

public class ArrayList extends AbstractList {
	implements List, RandomAccess, Cloneable, java.io.Serializable {
    ...
    transient Object[] elementData; //Object배열(elementData라는 이름의 Object배열을 멤버변수로 선언하고 있다는 것을 알 수 있다.)
}

1.3 LinkedList

배열

• 장점
  배열은 가장 기본적인 형태의 자료구조로 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다.
• 단점
  크기를 변경 할 수 없다.
  비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
  
  

링크드 리스트(배열의 단점을 보완)

• 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성
• 링크드 리스트의 각 요소(노드)들은 자신과 연결된 다음 요소에 대한 참조값(주소값)과 데이터로 구성
  

class Node {
	Node next; //다음 요소의 주소
    Object obj; //데이터
}

• 이동방향이 단방향. 다음 요소에 대한 접근은 쉽지만 이전 요소에 대한 접근은 어려움
  
  

더블 링크드 리스트(링크드 리스트 보완)

• 링크드 리스트보다 각 요소에 대한 접근과 이동이 쉬움

class Node {
	Node next; //다음 요소의 주소
    Node previous //이전 요소의 주소
    Object obj; //데이터
}

결론

• 순차적으로 추가/삭제하는 경우에는 ArrayList가 빠르다.
• 중간 데이터를 추가/삭제하는 경우에는 LinkedList가 빠르다.
• 다루고자 하는 데이터의 개수가 변하지 않는 경우에는 ArrayList가 최상의 선택
• 데이터 개수의 변경이 잦다면 LinkedList를 사용하는 것이 더 나은 선택

1.4 Stack과 Queue

PriorityQueue

• Queue인터페이스의 구현체 중 하나
• 저장한 순서에 관계없이 우선순위가 높은 것부터 꺼냄
• Null은 저장할 수 없음
  
  

Deque(Double-Ended Queue)

• 양쪽 끝에 추가/삭제 가능
• 스택 + 큐를 하나로 합쳐놓은 것
  
  

1.5 Iterator, ListIterator, Enumeration

• 컬렉션에 저장된 요소를 접근하는데 사용되는 인터페이스
• Enumeration은 Iterator의 구버전
• ListIterator는 Iterator의 기능을 향상시킨 것

Iterator

public interface Iterator {
	boolean hasNext();
    Object next();
    void remove();
}

public interface Collection {
	...
    public Iterator iterator();
    ...
}

• 공통 인터페이스를 정의해서 표준을 정의하고 구현하여 표준을 따르도록 함으로써 코드의 일관성을 유지하여 재사용성을 극대화하는 것이 객체지향 프로그래밍의 중요한 목적 중 하나
  
  

ListIterator와 Enumeration

• Enumeration: Iterator의 구버전
• ListIterator: Iterator에 양방향 조회기능추가(List를 구현한 경우만 사용가능)
• Enumeration과 Iterator는 메서드이름만 다를 뿐 기능은 같고, ListIteraotr는 Iterator에 이전방향으로의 접근기능을 추가한 것일 뿐임

[Enumeration인터페이스의 메서드]

[ListIterator의 메서드]

• Iterator는 단반향으로만 이동→컬렉션의 마지막 요소에 다다르면 더 이상 사용할 수 없음
• ListIterator는 양방향으로 이동하기 때문에 각 요소간의 이동이 자유로움

1.6 Arrays

배열의 복사 - copyOf(), coprtOfRange()

• copyOf(): 배열 전체 복사해서 새로운 배열을 만들어 반환
• copyOfRange(): 배열 일부를 복사해서 새로운 배열을 만들어 반환(copyOfRange에 지정된 범위의 끝은 포함 X)
  
  

배열 채우기 - fill(), setAll()

• fill(): 배열의 모든 요소를 지정된 값으로 채움
• setAll(): 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받음. 이 메서드를 호출할 때는 함수형 인터페이스를 구현한 객체를 매개변수로 지정하던가 아니면 람다식을 지정해야함.

int[] arr = new int[5];
Arrays.fill(arr, 9); //arr = [9, 9, 9, 9, 9]
Arrays.setAll(arr, i -> (int)(Math.random() * 5) + 1); //arr = [1, 5, 2, 1, 1]

ex. 람다식: i -> (int)(Math.random() * 5) + 1

배열의 정렬과 검색 - sort(), binarySearch()

• sort(): 배열을 정렬할 때 사용
• binarySearch(): 배열에 저장된 요소를 검색할 때 사용
  
  

문자열의 비교와 출력 - equals(), toString(), deepEquals(), deepToString()

• toString(): 배열의 모든 요소를 문자열로 편하게 출력 가능. 일차원 배열에만 사용할 수 있음
• deepToString(): 배열의 모든 요소를 문자열로 편하게 출력 가능. 배열의 모든 요소를 재귀적으로 접근해서 문자열을 구성하므로 2차원+3차원 이상의 배열에 대해서도 동작.
• equlas(): 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환. 일차원 배열에만 사용가능. (다차원 배열 비교에는 deepEquals()를 사용)
• 문자열을 비교하는 것이 아니라 '배열에 저장된 배열의 주소'를 비교하게 된다.
  
  

배열을 List로 변환 - asList(Object... a)

• asList()는 배열을 List에 담아서 반환
• asList()가 반환한 List의 크기를 변경할 수 없음. 즉, 추가 또는 삭제가 불가능함.

List list = Arrays.asList(new Integer[] (1, 2, 3, 4, 5)); //List = [1, 2, 3, 4, 5]
List list = Arrays.asList(1, 2, 3, 4, 5); //List = [1, 2, 3, 4, 5]
list.add(6); // 오류 발생(크기 변경 불가함)

//크기를 변경할 수 있는 List가 필요할 시
List list = new ArrayList(Arrays.asList(1, 2, 3, 4, 5)); //변경 가능한 ArrayList생성

parallelXXX(), spliterator(), stream()

• 보다 빠른 결과를 얻기 위해 여러 쓰레드가 작업을 나누어 처리하도록 함
• spliterator()는 여러 쓰레드가 처리할 수 있게 하나의 작업을 여러 작업으로 나누는 Spliterator를 반환하며, stream()은 컬렉션을 스트림으로 변환
  
  

1.7 Comparator와 Comparable

• Arrays.sort()는 Character클래스의 Comparable의 구현에 의해 배열이 정렬되었던 것.
• Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있으며, Comparable을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Integer와 같은 wrapper클래스와 String, Date, File과 같은 것들이며 기본적으로 오름차순, 즉 작은 값에서부터 큰 값의 순으로 정렬되도록 구현되어 있음.
• Comparable: 기본 정렬기준(오름차순)을 구현하는데 사용
• Comparator: 기본 정렬기준 외에 다른 기준으로 정렬하고자 할 때 사용(내림차순으로 정렬 or 다른 기준에 의해 정렬되도록 하고 싶을 때)
  
  

1.8 HashSet

• Set인터페이스를 구현한 가장 대표적인 컬렉션
• Set인터페이스의 특징대로 중복된 요소를 저장하지 않음
  

import java.util.*;

class HashSetEx1 {
	public static void main(String[] args) {
		Object[] = objArr = ("1", new Integer (1), "2", "2", "3", "3", "4", "4", "4");
        Set set = new HashSet();
        
        for (int i = 0; i < objArr.length; i++) {
        	set.add(objArr[i]); //HashSet에 objArr의 요소들을 저장
        }
        //HashSet에 저장된 요소 출력
        System.out.println(set);
        //{1, 1, 2, 3, 4}
        //"1"은 String인스턴스, new Integer(1)은 Integer인스턴스로 서로 다른 객체로 여기기 때문에 중복으로 간주하지 않음
    }
}

• 순서를 유지하지 않기 때문에 저장한 순서와 다를 수 있음
• 중복 제거 + 저장한 순서 유지를 위해서는 LinkedHashSet를 사용해야함
  
  

1.9 TreeSet

• 이진 검색 트리라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스
• 이진 검색 트리: 정렬, 검색, 범위검색에 높은 성능을 보이는 자료구조
  TreeSet: 이진 검색 트리의 성능을 향상시킨 '레드-블랙 트리'로 구현
• Set인터페이스를 구현했으므로 중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않아도 됨
  

class TreeNode {
	TreeNode left; //왼쪽 자식노드
    Object element; //객체를 저장하기 위한 참조변수
    TreeNode right; //오른쪽 자식노드
}

데이터를 저장하기 위한 Object타입의 참조변수 하나
두 개의 노드를 참조하기 위한 두 개의 참조변수 선언

• 부모노드의 왼쪽에는 부모노드의 값보다 작은 값의 자식노드, 오른쪽에는 큰 값의 자식노드를 저장
  

<이진 검색 트리>

• 모든 노드는 최대 두 개의 자식노드를 가질 수 있다.
• 왼쪼 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식노드의 값은 부모노드의 값보다 커야한다.
• 노드의 추가 삭제에 시간이 걸린다.(순차적으로 저장하지 않으므로)
• 검색(범위검색)과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다.
  
  

1.10 HashMap과 Hashtable

• Hashtable보다는 새로운 버전인 HashMap을 사용하는 것을 권함
• Map을 구현했으므로 Map의 특성, 키와 값을 묶어서 하나의 데이터로 저장한다는 특징을 가짐
• 키와 값을 각각 Object 타입으로 저장((Object, Object)의 형태로 저장하기 때문에 어떠한 객체도 저장할 수 있지만 키는 주로 String 대문자 또는 소문자로 통일해서 사용)
  • 키: 컬렉션 내의 키 중에서 유일해야 함(HaspMap에 저장된 데이터를 하나의 키로 검색했을 때 결과가 단 하나이어야 함)
  • 값: 키와 달리 데이터의 중복을 허용
• 해싱을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보임

해싱과 해시함수

• 해싱: 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법
• 저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 됨

1. 검색하고자하는 값의 키오 해시함수 호출
2. 해시함수의 계산결과인 해시코드를 이용해서 해당 값이 저장되어 있는 링크드 리스트 찾기
3. 링크드 리스트에서 검색한 키와 일치한 데이터 찾기

• 배열의 n번째 요소의 주소 = 배열의 시작주소 + type의 size * n
• 하나의 서랍에 하나의 데이터만 저장되어 있는 형태가 더 빠른 검색결과를 얻을 수 있다.

int hashFunciton(String key) {
	return Integer.parseInt(key.substring(0, 1));
}

1.11 TreeMap

• 이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터를 저장(검색과 정렬에 적합한 컬렉션 클래스)
  
  

1.12 Properties

• HaspMap의 구버전인 Hashtable을 상속받아 구현한 것으로, (String, String)의 형태로 저장하는 단순화된 컬렉션 클래스
• setProperty() : 데이터를 저장하는데 사용. 단순히 Hashtable의 put메서드를 호출. 기존에 같은 키로 저장된 값이 있는 경우 그 값을 Object타입으로 변환하며, 그렇지 않을 때는 null을 반환

Object setProperty(String key, String value)

• getProperty(): Properties에 저장된 값을 읽어옴. 읽어오려는 키가 존재하지 않으면 지정된 기본값을 반환.

string getProperty(String key)
String getProperty(String key, String defaultValue)

• list메서드를 이용하면 Properties에 저장된 모든 데이터를 화면 또는 파일에 편리하게 출력

void list(PrintStream out)
void list(PrintWriter out)

1.13 Collections

• 컬렉션과 관련된 메서드(fill(), copy(), sort(), binarySearch() 등) 제공

컬렉션 동기화

변경불가 컬렉션 만들기

싱글톤 컬렉션

• 인스턴스를 new연산자가 아닌 메서드를 통해서만 생성할 수 있게 함으로써 생성할 수 있는 인스턴스의 개수를 제한하는 기능을 제공

static List singletonList(Object c)
static Set singleton(Object c) //singletonSet이 아님
static Map singletonMap(Object key, Object value);

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

총정리