🔥자바스터디🔥 자바의 정석 CH11 컬렉션프레임웍

1. 컬렉션프레임워크

 

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

 

- Collection 인터페이스

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

 

- List 인터페이스

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

 

 

- Set 인터페이스

     중복을 허용하지않고 저장순서가 유지되는 컬렉션을 구현하는데 사용(HashSet, TreeSet 등)

 

- Map 인터페이스

     키와 값을 하나의 쌍으로 묶어서 저장하는 컬렉션을 구현

     키는 중복될수 없지만 값을 중복을 허용한다.

 

- Map.Entry 인터페이스

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

 

1.2 ArrayList

 

     - Object 배열을 이용해서 데이터의 저장순서가 유지되고 중복을 허용한다.

     - 삭제 진행시 데이터의 저장순서가 유지되기 때문에 마지막 데이터를 삭제하는 경우가 아니라면,

       arraycopy가 발생된다. 데이터를 옮기는 작업을 거치기 때문에 데이터가 많을수록 수행시간이 오래걸린다.

 

1.3 LinkedList

 

[배열의 장단점]

    1) 장점

         - 구조가 간단하며 사용하기 쉽고 데이터를 읽어오는데 걸리는 시간이 가장 빠르다.

    2) 단점 

         - 크기를 변경할 수 없다

         - 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.

---

     - 배열의 단점을 보완하기 위해 만들어짐

     - 불연속적으로 존재하는 데이터를 서로 연결한 형태로 구성

     - 삭제하고자 하는 요소의 이전요소가 삭제하고자하는 요소의 다음요소를 참조하도록 변경하면 된다

     - 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경,

             새로운 요소가 그 다음 요소를 참조하도록 변경하면 된다.

     - 링크드 리스트는 이동방향이 단방향이라 이전요소에 대한 접근이 어려워 이를 보완하여 더블 링크드리스트가 만들어졌다

 

ArrayList vs LinkedList 성능 비교

 

  ① 순차적으로 데이터를 추가/삭제 - ArrayList가 빠름

  ② 비순차적으로 데이터를 추가/삭제 - LinkedList가 빠름

  ③ 접근 시간(access time) - ArrayList가 빠름

 

1.4 Stack과 Queue

 

     - Stack : 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO 구조

     - Queue : 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO 구조

  ** 스택과 큐의 활욜

       스택 : 수식계산, 수식괄호검사, 워드프로세서의 undo/redo, 웹브라우저의 뒤로/앞으로

       큐 : 최근사용문서, 잉ㄴ쇄작업 대기목록, 버퍼(buffer)

 

  ** Queue의 변형

 

     1) 덱(Deque)

          - 양쪽 끝에서 저장(offer)과 삭제(poll)가 가능하다.

          - Deque은 인터페이스이며 구현체로는 ArrayDeque, LinkedList이다. (Deque은 Queue의 자손이다)

 

    2) 우선 순위 큐(Priority Queue)

         - 저장 순서에 관계 없이 우선 순위가 높은 것부터 꺼낸다. (제일 작은 값 부터 꺼냄)

         - null은 저장 할 수 없다. (우선 순위를 판단할 수 없기 때문)

         - 우선 순위 큐는 저장 공간으로 배열을 사용하며, 각 요소를 힙(Heap)이라는 자료구조의 형태로 저장한다.

         - 예를 들어, 입력[3, 1, 5, 2, 4] → 출력[1, 2, 3, 4, 5]

 

1.5 Iterator, ListIterator, Enumeration

 

- 컬렉션에 저장된 데이터를 접근하는데 사용되는 인터페이스

 

Iterator

 

   - 컬렉션에 저장된 요소들을 읽어오는 방법을 표준화한 것

   - 컬렉션에 iterator()를 호출해서 Iterator를 구현한 객체를 얻어서 사용. 

   - Iterator는 1 회용이므로 다 사용 했다면 다시 얻어 와야 한다.

   - Iterator의 remove는 단독으로 사용 불가, next와 함께 사용해야한다(읽어온것 삭제)

 

ListIterator

 

   - Iterator의 접근성을 향상시킨 것이 ListIterator이다. (단방향 →양방향)

   - listIterator()를 통해서 얻을 수 있다.(List를 구현한 컬렉션 클래스에 존재)

 

Map과 Iterator

 

   - Map은 Collection의 자손이 아니므로 Iterator()가 없다.

   - 그래서 Map은 keySet(), entrySet(), values()를 호출한 다음, Iterator()를 호출해야 한다.

 

1.6 Arrays

 

배열의 복사 - copyOf() 배열전체, copyOfRange() 배열의 일부를 복사해서 새로운 배열을 반환

 

배열 채우기

    - fill()  : 배열의 모든 요소를 지정된 값으로 채운다

    - setAll()  : 배열을 채우는데 사용할 함수형 인터페이스를 매개변수로 받는다

 

배열의 정렬과 검색 

    - sort()는 배열을 정렬할 때 사용하고 binarySearch()는 배열에 저장된 요소를 검색할 때 사용한다.

    - binarySearch()는 배열에서 지정된 값이 저장된 위치(index)를 찾아서 반환하는데,

      반드시 배열이 정렬된 상태이어야 올바른 결과를 얻는다.

      검색한 값과 일치하는 요소들이 여러 개 있다면, 이 중에서 어떤 것의 위치가 반환될지는 알 수 없다.

 

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

 

배열을 List로 변환 - asList(Object... a) : 배열을 List에 담아서 반환(반환한 List의 크기변경 불가)

 

parallelXXX(), spliterator(), stream()

 

1.7 Comparator와 Comparable

      

- 객체를 정렬 하는데 필요한 메서드를 정의한 인터페이스이다. (정렬 기준 제공)

 

Comparable - 기본 정렬 기준을 구현하는데 사용.

Comparator - 기본 정렬 기준 외에 다른 기준으로 정렬하고자 할 때 사용.

 

- compare()와 compareTo()는 두 객체의 비교 결과를 반환 하도록 구현 해야 한다.

   비교하는 두 객체가 같으면 0, 왼쪽이 크면 양수, 왼쪽이 작으면 음수를 반환

   (리턴 값이 음수일 때 자리 교환이 발생함)

- Arrays.sort()는 배열을 정렬할 때 Comparator를 지정하지 않으면 객체 배열에 저장된 객체가 구현한 Comparable에 의해 정렬된다.

- String의 Comparable 구현은 문자열이 사전 순으로 정렬 되도록 작성되어 있다.

  String의 오름차순 정렬(사전 순서)은 공백, 숫자, 대문자, 소문자의 순으로 정렬되는 것을 의미

- String은 대소문자를 구분하지 않고 비교하는 Comparator를 상수 형태로 제공한다.

   이 Comparator를 이용하면 문자열을 대소문자 구분 없이 정렬 할 수 있다.

- 정렬(sort)는 두 대상을 비교하여 자리 바꿈을 반복 하는 것이다.

   (정렬 방법은 변경 되지 않으며 정렬 기준만 달라지기 때문에 정렬 기준만 전달하면 된다.)

 

 

1.8 HashSet / 1.9 TreeSet

 

1) HashSet

 

- HashSet은 저장 순서를 유지 하지 않으며 중복을 허용하지 않는다.

- 내부적으로 HashMap을 이용해서 만들어졌으며 Set 인터페이스를 구현한 대표적인 컬렉션 클래스이다.

- 저장 순서를 유지하려면 LinkedHashSet 클래스를 사용하면 된다.

- Set은 정렬 할 수 없기 때문에 Set의 모든 요소를 List에 담아서, Collections.sort()로 정렬한다.

 

2) TreeSet

 

- TreeSet은 이진 탐색 트리라는 자료 구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.

- 내부적으로 TreeMap을 이용해서 만들어졌으며 범위 검색과 정렬에 유리하다.

- HashSet 보다 데이터 추가, 삭제에 시간이 더 걸림

[이진 탐색 트리(binary search tree)]

 

- 모든 노드가 최대 두 개의 자식 노드를 갖는다.

- 부모 보다 작은 값은 왼쪽, 큰 값은 오른쪽에 저장한다.

- 중복된 값을 저장하지 못한다.

- 범위 검색과 정렬에 유리하다.

- 데이터가 많아질 수록 데이터 추가, 삭제에 시간이 더 걸린다. (부모 보다 큰지 작은지를 비교하는 횟수가 증가하기 때문)

 

1.10 HashMap과 Hashtable

 

- HashMap은 Map 인터페이스를 구현하였으며 데이터를 키와 값의 쌍(entry)으로 저장한다.

- HashMap(동기화 X)은 HashTable(동기화 O)의 새로운 버전이다.

- 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 뛰어난 성능을 보인다.

- HashMap은 Entry라는 내부 클래스를 정의하고 다시 Entry 타입의 배열을 선언하고 있다.

- 저장 순서를 유지하려면, LinkedHashMap클래스를 사용하면 된다.

 

해싱(Hashing)?

 

- 해싱(Hashing)은 해시 함수(hash function)를 이용해서 해시 테이블(hash table)에 데이터를 저장하거나 검색하는  기법

- 해시 함수(hash function)는 키를 전달하면 데이터가 저장된 위치(index)를 알려준다.

 

* 해시 코드(hash code) = 배열의 인덱스(index)

 

① 키로 해시 함수를 호출해서 해시코드를 얻는다.

② 배열에서 해시코드(해시 함수의 반환 값)와 일치하는 연결리스트(Linked List)를 찾는다.

③ 연결리스트(Linked List)에서 키와 일치하는 데이터를 찾는다.

 

- 해싱에서 데이터를 저장하는 공간을 해시 테이블(Hash Table)이라 한다. (배열과 연결 리스트(Linked List)가 조합된 형태)

 

** 해시 함수는 같은 키에 대해 항상 같은 해시 코드를 반환 해야 한다. 서로 다른 키 일지라도 같은 값의 해시 코드를 반환할 수도 있다.

 

1.11 TreeMap

 

- TreeMap은 이진 탐색 트리의 구조로 키와 값의 쌍으로 이루어진 데이터를 저장한다.

- HashMap보다 데이터 추가, 삭제에 시간이 더 걸린다.

- 다수의 데이터에서 개별적인 검색은 TreeMap보다 HashMap이 빠르다. 

- Map이 필요할 때는 주로 HashMap을 사용하고, 범위 검색이나 정렬이 필요한 경우에 TreeMap을 사용한다.

 

1.12 Properties

 

- Properties는 HashMap의 구버전인 Hashtable을 상속 받아 구현한 것으로 key와 value를 String으로 저장한다.

   즉, Properties는 (String, String)의 형태로 저장한다.

 

- 주로 애플리케이션의 환경 설정에 관련된 속성을 저장 하는데 사용되며 파일로부터 편리하게 값을 읽고 쓸 수 있는 메서드를 제공한다.

 

1.13 Collections

 

- Collections 클래스는 컬렉션를 위한 static 메서드를 제공한다.

 

1) 컬렉션 채우기, 복사, 정렬, 검색 – fill(), copy(), sort(), binarySearch() 등의 메서드는 Arrays에서 이미 배웠으므로 설명을 생략한다.

2) 컬렉션의 동기화 – synchronizedXXX()

    - synchronizedXXX()는 동기화 처리를 한다.

3) 변경 불가(readOnly) 컬렉션 만들기 –  unmodifiableXXX() 

    - unmodifiableXXX()는 저장된 데이터를 변경 할 수 없는 컬렉션을 만든다.

4) 싱글톤 컬렉션 만들기 – singletonXXX()

    - singletonXXX()는 단 하나의 객체만을 저장하는 컬렉션을 만든다.

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

    - checkedXXX()는 한 종류의 객체만 저장하는 컬렉션을 만든다.

 

- 컬렉션에 저장할 요소의 타입을 제한하는 것은 제네릭으로 간단히 처리할 수 있지만 이러한 메서드들을 제공하는 이유는 호환성 때문이다.