(오키) 자바의정석, 챕터 11 - Collections Framework

11-1~2 컬렉션프레임웍과 핵심 인터페이스

  • 컬렉션(collection) : 여러 객체를 모아 놓은것
  • 프레임웍(framework) : 표준화, 정형화 된 체계적인 프로그래밍 형식
  • collection framework: 컬렉션을 다루기 위한 표준화된 프로그래밍 형식, java.util 패키지에 포함, JDK1.2 부터 표준화
  1. List: 순서 유지 O, 중복 허용 O (ArrayList, LinkedList, Stack, Vector 등)
  2. Set: 순서 유지 X, 중복 허용 X (HashSet, TreeSet 등)
  3. Map: 키(key)와 값(value)의 쌍(pair), 순서 유지 X, 키 중복 허용 X, 값 중복 허용 O
    (HashMap, TreeMap, Hashtable, Properties)

11-3~6 Collection - List, Set

List와 Set은 Collection 인터페이스를 가진다.

Collection 인터페이스의 주요 메서드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
boolean add(Object o);  // (추가)
boolean add(Collection c);

boolean remove(Object o); // (삭제)
boolean removeAll(Collection c);
boolean retainAll(Collection c) ; //포함된 객체만 남기고 다른 객체 삭제
void clear(); // 전체 삭제

boolean contains(Object o); // 포함 여부 확인 (검색)
boolean contains(Collection c);

boolean isEmpty(); // 비어 있는지 확인 
int size(); // 저장된 객체수 확인

Iterator iteraotr(); // iterator 반환

Object[] toArray(); // 객체배열로 반환
Object[] toArray(Object[] a); // 지정된 배열에 Collection 객체를 저장해서 반환한다?

11-4 List 인터페이스 - 순서 O, 중복 O

구현체: ArrayList, LinkedList, Vector <- Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//추가
void add(int index, Object element);
boolean addAll(int index, Collection c);
Object set (int index, Object element);

//검색
Object get(int index); // 읽기
int indexOf(Object o);
int lastIndexOf(Object o);

//삭제
Object remove(int index);

//정렬
void sort(Comparator c);
List subList(int fromIndex, int toIndex);

11-5 Set 인터페이스 - 순서 X, 중복 X

구현체: HashSet, SortedSet <- TreeSet
주요 메서드: Collection 과 동일

1
2
3
4
boolean addAll(Collection c); // 합집합
boolean containsAll(Collection c); // 포함 확인 (부분 집합)
boolean removeAll(Collection c); // 차집합
boolean retailAll (Collection c); // 교집합 (포함된 객체만 남기고 나머지는 삭제)

11-6 Map 인터페이스 - 순서X, 중복(키X, 값O)

구현체: Hashtable, HashMap <- LinkedHashMap (순서 O), SortedMap <- TreeMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 추가
Object put(Object key, Object value);
void putAll(Map t);

//삭제
Object remove(Object key);
void clear();

//검색
boolean containsKey(Object key);
boolean containsValue(Object value);
Object get(Object key);
boolean isEmpty();
int size();

Set entrySet(); // 저장된 모든 객체를 key, value 의 객체로 반환
Set keySet(); // Map 에 저장된 모든 key 객체를 반환
Collection values(); // Map 에 저장된 모든 value 객체를 반환

11-7 ArrayList

  • 내부적으로 Array 잡음
  • thread-safe X

11-8 ArrayList 의 메서드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//생성자
ArrayList();
ArrayList(Collection c);
ArrayList(int initialCapacity);

// 추가
boolean add(Object o);
void add(int index, Object element);
boolean addAll(Collection c);
boolean addAll(int index, Collection c);

//삭제
boolean remove(Object o);
Object remove(int index);
boolean removeAll(Collection c);
void clear();

//검색
int indexOf(Object o); // 못 찾으면 -1
int lastIndexOf(Object o);
boolean contains(Object o);
Object get(int index); // 특정 위치 객체 읽기
Object set(int index, Object element); // 특정 위치 객체 변경

//이외
List subList(int fromIndex, int toIndex);
Object[] toArray();
Object[] toArray(Object[] a);
boolean isEmpty();
void trimToSize(); // 빈공간 제거
int size(); // 저장된 객체 반환

ch 11-12 LinkedList - 배열의 장단점

우선 배열, ArrayList 에 대한 장단점

  • 장점: 배열의 구조 간단, 데이터를 읽는 데 걸리는 시간이 짧다

예: int arr -> 1, 2, 3, 4, 5 이면 n번째 arr 주소 + 4 byte * n

  • 단점1: 크기 변경시 데이터 복사가 일어남
  • 단점2: 비순차적 데이터 추가 삭제에 시간이 많이 걸린다, 맨끝에 하는것 제외

LinkedList는 배열의 단점 보완, 단점은 데이터를 읽는 시간이 더 걸린다.
구현에 따라 Double LinkedList, Circular Double LinkedList가 있다.

ch11-15 Stack and Queue

Stack: LIFO 구조, 마지막 저장 제일 먼저 꺼낸다, push, pop
자바에서 Stakc이란 클래사가 있음 

1
2
3
4
5
6
7
Stack s = new Stack();

boolean empty();
Object pop(); // 비었을때는 EmptyStackException 발생
Object push(Object item);
int search(Object o); // 못찾으면 -1, index가 1부터 시작
Object peek();

Queue: FIFO 구조, 제일 먼저 저장 제일 먼저 꺼낸다, offer, poll
자바에서 Queue는 인터페이스 이다. 구현체로 new 해야함, API 문서 보면 많은 구현체가 있음
(LinkedList, Abstract Queue, ArrayBlockingQueue, ArrayDeque, PriorityQueue 등등)

1
2
3
4
5
6
7
8
9
10
Queue q = new LinkedList();

boolean offer(Object o); // 추가
boolean add(Object o); // 저장 공간 부족하면 IllegalStateException 발생

Object poll(); // 꺼내기, 비어 있으면 null 반환
Object remove(); // 비어 있으면 NoSuchElementException 발생

Object peek(); // 비어 있으면 null 반환
Object element(); // peek 비어 있으면 NoSuchElementException 발생

ch11-19 스택과 큐 의 활용

스택: 수식계산, 수식괄호 검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로
큐: 최근사용문서, 인쇄 작업 대기목록, 버퍼(buffer)

ch11-22~24 Iterator, ListIterator, Enumeration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Collection {
    //...
    public Iterator iteartor();
    //...    
}

boolean hasNext(); // 읽어올 요소가 남아 있는지 확인
Object next(); // 다음 요소를 읽어 온다

List list = new ArrayList();
Iterator it = list.iterator();

while(it.hasNext()) {
    System.out.println(it.next());
}

ch11-24 Map 과 Interator

Map 에서 바로 interator() 호출 안되고 keySet(), entrySet(), values() 를 호출해야 된다.

1
2
3
Map map = new HashMap();
//...
Iterator it = map.entrySet().iterator();

ch11-25 Arrays - 배열을 다루기 편리한 메서드(static) 제공

  1. 배열의 출력 - toString()
  2. 배열의 복사 - copyOf(), copyOfRange()
  3. 배열 채우기 - fill(), setAll()
  4. 배열의 정렬과 검색 - sort(), binarySearch()
1
2
3
4
5
6
7
8
9
int[] arr = new int[5];
Arrays.fill(arr, 9);
Arrays.setAll(arr, (i) -> (int) (Math.randome()*5)+1)

int[] arr = { 3, 2, 0, 1, 4};
int index = Arrays.binarySearch(arr, 2); // 정렬되어 있을때만 호출 가능, 아니면 잘못된 결과

Arrays.sort(arr);
int idx = Arrays.binarySearch(arr, 2);

ch11-30 Comparator 와 Comparable

  • 객체 정렬에 필요한 메서드 (정렬 기준 제공)를 정의한 인터페이스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public interface Comparator {
    int compare(Object o1, Object o2);  // o1, o2 두 객체를 비교 
                                        // 양수 왼쪽 큼, 0, 같음, 음수: 오른쪽 큼
    boolean equals(Object obj);         // equals를 오버라이딩 하라는 뜻
}

public interface Comparable {
    int compareTo(Object o);            // 주어진 객체(o)를 자신과 비교
}

public final class Integer extends Number implements Comparable {
    //...
    public int compareTo(Integer anotherInteger) {
        int v1 = this.value;
        int v2 = anotherInteger.value;

        return (v1 < v2 ? -1 : (v1==v2? 0 : 1));
    }
}

Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER);

public static final Comparator<String> CASE_INSENSITIVE_ORDER = new CaseInsensitiveComparator();

Arrays.sort(strArr, new Descending());
class Descending implements Comparator {
    public int compare(Object o1, Object o2) {
        if( o1 instanceof Comparable && o2 instanceof Comparable) {
            Comparable c1 = (Comparable) o1;
            Comparable c2 = (Comparable) o2;
            return c1.compareTo(c2) * -1;
        }
        return -1;
    }
}

ch11-34 HashSet - 순서 X, 중복 X

  • HashSet : Set 인터페이스를 구현한 대표적인 컬렉션 클래스
  • TreeSet: 범위 검색과 정렬에 유리, HashSet 보다 데이터 추가, 삭제에 시간이 더 걸림
  • boolean add(Object o)는 저장할 객체의 equals()와 hashCode()를 호출
  • equals()와 hashCode()가 오버라이딩 되어 있어야 함
1
2
3
4
5
6
7
8
9
10
11
12
13
class Person {
    String name;
    int age;
    //..
}
public boolean equals(Object obj) {
    if(!(obj instanceof Person)) return false;
    Person tmp = (Person) obj;
    return name.equals(tmp.name) && age==tmp.age;
}
public int hashCode() {
    return Objects.hash(name, age);
}

ch11-39 TreeSet - 범위 탐색, 정렬

  • 이진 탐색 트리(binary search tree)로 구현. 범위 탐색과 정렬에 유리
  • 노트가 최대 2개의 하위 노드를 가지고 있음 (LinkedList의 변형) 나무 모양

ch11-41 TreeSet - 데이터 저장 과정 boolean add(Object o)

  • Tree 형태로 만들어짐
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TreeSet(); // 기본 생성자
TreeSet(Collection c);
TreeSet(Comparator comp); // 주어진 정렬 기준으로 TreeSet 생성

Object first();
Object last();

Object ceiling(Object o);
Object floor(Object o);
Object higher(Object o);
Object lower(Object o);

SortedSet subSet(Object fromElement, Object toElement); // 범위 검색
SortedSet headSet(Object toElement); // 지정 된 객체보다 작은 것을 반환
SortedSet tailSet(Object fromElement); // 지정된 객체보다 큰것을 반환

ch11-46 HashMap과 Hashtable - 순서 X, 중복 (키X, 값O)

  • Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
  • 해시 함수(hash function)로 해시 테이블(Hash table)에 데이터를 저장, 검색
  • 키(key) -> 해시함수(hash function) -> 해시코드(hash code) = 배열 index

ch11-48 HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HashMap(); 
HashMap(int initialCapacity);
HashMap(int initialCapacity, float loadFactor);
HashMap(Map m);

Set entrySet();
Set keySet();
Collection values();

Object put(Object key, Object value);
void putAll(Map m);
Object remove(Object key);
Object replace(Object key, Object value);
boolean replace(Object key, Object oldValue, Object newValue);

ch11-52~54 Collections - 컬렉션을 위한 메서드(static)를 제공

  • 컬렉션 채우기, 복사, 정렬, 검색 - fill(), copy(), sort(), binarySearch() 등
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 동기화 버전
static Collection synchronizedCollection(Collection c);
static List       synchronizedList(List list);
static Set        synchronizedSet(Set s);
static Map        synchronizedMap(Map s);
static SortedSet  synchronizedSortedSet(SortedSet s);

List syncList = Collections.synchronizedList(new ArrayList(...)); // 동기화 되지 않은

// 변경 불가 (readonly) 버전
static Collection unmodifiedCollection(Collection c); 
//....

// 싱글톤 컬렉션 만들기 
static List singletonList(Object o); // 객체 1개만 저장
static Set singleton(Object o);
static Map singletonMap(Object key, Object value);

// 한 종류의 객체만 저장 하는 컬렉션 만들기
static Collection checkedCollection(Collection c, Class type);
static List       checkedList(List list, Class type);
static Set        checkedSet(Set s, Class type);
//....

List list = new ArrayList();
List checkedList = checkedList(list, String.class);
checkedList.add("abc");
checkedList.add(new Integer(3)); // 에러

// 여러 메서드 등
import static java.util.Collections.*;
List list = new ArrayList();
addAll(list, 1,2,3,4,5);
rotate(list,2);
swap(list,0,2);
shuffle(list);
sort(list);
binarySearch(list,3);
max(list);
min(list);
fill(list,9);
nCopies(list.size(), 2);

List newList = nCopies(list.size(), 2);
disjoint(list, newList); // 공통 요소가 없으면 true
copy(list, newList);
replaceAll(list, 2, 1);

Enumeration e = enumeration(list);
ArrayList list2 = list(e);