[JAVA] 자바 컬렉션 프레임워크

1️⃣ Collection Framework

자바의 컬렉션은 다수의 요소를 하나의 그룹으로 묶어 효율적으로 저장하고 관리할 수 있는 기능을 제공하는 일종의 컨테이너(자료구조)이다. 일반 배열은 크기가 고정되어있는데 반해, 컬렉션 프레임워크는 가변적인 크기를 갖는다. 또한 데이터 삽입, 탐색, 정렬 등 편리한 API를 다수 제공한다.

👍 장점

• List, Queue, Set, Map 등의 인터페이스를 제공하고 구현 클래스를 제공하여 일관된 API를 사용 할 수 있다
• 가변적인 저장 공간 제공
• 개발자가 자료구조, 알고리즘을 구현하기 위한 코드를 직접 장성하지 않고 이미 구현된 컬렉션 클래스를 목적에 맞게 선택 사용하면 됨

📌 구성요소

인터페이스

각 컬렉션을 나타내는 인터페이스가 있으며, 클래스는 이 인터페이스를 구현하는 방식으로 작성되어 상세 동작은 달라도 동일한 조작법으로 사용할 수 있음

클래스

위 인터페이스의 구현으로 같은 List라 하더라도 ArrayList, LinkedList 등으로 상세 구현이 달라짐

알고리즘

컬렉션이 제공하는 연산, 검색, 정렬, 셔플 등에 대한 메소드

2️⃣ 종류

• List: 인데스 순서로 요소를 저장하며, 중복된 데이터를 저장할 수 있다
• Queue: 데이터가 저장된 순서대로 출력되는 FIFO 구조의 선형 자료구조
• Set: 순서가 없으며, 데이터를 중복하여 저장 할 수 없다. 집합 연산(합집합, 교집합, 차집합 등)을 지원한다.
• Map: Key-Value 쌍으로 데이터를 저장하며, Key는 중복될 수 없다. 순서는 존재하지 않는다. (컬렉션 상속을 받지 않는다.)

iterable

• iterable 인터페이스는 하위 클래스가 추상 메서드 iterator()를 구현하도록 함
• iterable을 상속받은 Collection의 하위 클래스들은 모두 iterator() 메서드를 가지고 있게 된다

iterator

Iterator 인터페이스는 자바 컬렉션 프레임워크에 표준화된 컬렉션에 저장된 요소를 읽어오는 방법이다
Collection 인터페이스에는 iterator를 반환하는 iterator() 메서드가 정의되어 있다

• boolean hasNext(): 읽어올 요소가 있는지 확인
• Object next(): 다음 요소 읽어오기
• void remove(): 읽어온 요소 삭제(next로 읽어온 후 사용해야 함)

ListIterator 인터페이스도 있으며, 이는 양방향 탐색을 지원한다. List 인터페이스를 구현한 List 컬렉션 클래스에서만 listIterator() 메서드를 통해 사용이 그낭하다.

Comparator와 Comparable

Comparator와 Comparable은 인터페이스로, 컬렉션 정렬에 필요한 메서드를 정의한다.
Comparator의 int compare(Object o1, Object o2);와 Comparable의 int compareTo(Object o);는 형태가 조금 다르지만 기본적으로 두 객체를 비교하는 메서드이다. 두 객체가 같으면 0, 비교하는 값보다 작으면 음수 크면 양수를 반환한다.

Comparable을 구현한 클래스는 기본적으로 오름차순 정렬되어있으며, Comparator를 구현하여 내림차순 등 다른 정렬 기준을 제공할 수 있다.

Comparator를 구현한 클래스는 그 자체가 정렬자가 되어야 하기 때문에 이 기능만 사용하고 싶을 경우 익명 클래스를 만들어 사용하기도 한다.

🚃 List

ArrayList와 LinkedList

• ArrayList는 배열로 구현되어있어 탐색에는 유리하나 요소의 삽입/삭제에서는 효율이 떨어진다. 중간 객체를 삭제 시 그 다음 객체부터 맨 마지막 객체까지 모두 앞으로 1 인덱스씩 옮겨야 하기 때문이다.

• LinkedList는 요소들이 주소값으로 연결되어 있어 요소의 삽입/삭제에는 유리하나 탐색의 효율이 떨어진다. 중간 객체를 삭제 시 그 이전 객체와 다음 객체를 연결시켜주기만 하면 되나, 탐색을 위해서는 인덱스로 접근하는 것이 아니라 계속해서 다음, 다음 객체로 이동하며 탐색해야 하기 때문이다.

Vector와 ArrayList의 차이

• Thread-safe: Vector O | ArrayList X
• 동기 비동기: Vector 동기 | ArrayList 비동기
• 초기 용량 및 증설: Vector 10 & 2배 | ArrayList 10 & 1.5배
• 반복자: Vecotr Enumeratio & iterator 둘 다 사용 가능 | ArrayList iterator만 가능
• Vector: 컬렉션 프레임웤 이전에 나와 소스 코드 호환을 위해 남아있는 것. ArrayList를 쓰자

🔑 Map

HashMap

Map 인터페이스를 구현하는 대표적인 클래스다

• Key는 중복될 수 없으나, Value는 중복이 가능하다
• 여기서 Key는 원시 타입은 사용할 수 없고 참조형만 사용 가능하다.
• 요소의 저장 순서를 유지하지 않는다.
• HashMap은 키와 값에 Null을 허용하지만 HashTable은 허용하지 않는다.
• iterator()를 직접 호출할 수 없으며, keySet(), entrySet()과 같은 메서드를 이용해 Set 형태로 반환된 컬렉션에서 iterator()를 호출해야 한다.
• Hash Algorithm을 사용하여 검색 속도가 매우 빠르다

• LinkedHashMap은 입력된 순서대로 데이터가 출력될 수 있고, TreeMap은 입력된 key가 정렬된 형태로 데이터가 출력될 수 있다
• HashTable은 기존 코드와의 호환성을 위해서만 남아있어 HashMap을 쓰는 것이 좋다

Hash Function, Hash Collision

Map을 처음 공부할 때 key-value 형태로 되어있고 key값은 중복되지 않는다. 해당 key값을 이용하여 O(1)의 속도로 값을 찾을 수 있다. 이렇게 배웠다. 근데 key가 중복되지 않는 거랑 성능이 O(1)이 되는 것이 어떻게 가능한지 이해할 수 없었다. key값을 어떻게 찾길래?가 궁금했다고 할 수 있다.

자 만약 좌석이 100개인 영화관에 1번부터 500까지의 번호를 가진 사람들이 랜덤하게 100명이 온다고 하자. 이때 315번을 가진 사람이 왔다. 이 사람을 몇번 좌석에 앉혀야 우리가 이 사람을 다시 찾아야 할 때 한 번에 찾을 수 있을까? 제일 좋은건 15번에 앉히는 거다. 다시 말해 n % 100의 값에 앉히는 것이다. 여기서 n % 100이 Hash Function이 되고, 그 값이 다시 Hash code가 된다.

근데 문제는 저 상황에서 15번이나 215번과 같이 Hash code가 같은 사람이 오면 어떻게 해야 할까? 이게 Hash collision이다. Key는 중복되지 않지만, Hash Function을 거친 Hash Code는 중복될 수 있다. 이때 이 해시 충돌을 방지하는 방법에는 옆칸에 앉히거나 해시 코드를 다시 재해싱하는 방법 등등이 있지만, 15번의 무릎에 앉히는 것도 한 방법이 된다. 그러니까 LinkedList로 관리하는 것이다.

315번이 영화관에 있다면, 일단 15번에 가서 315번인지 확인하고 아니라면 그 LinkedList만 탐색하면 바로 315번을 찾을 수 있는 것이다.

Hash Code, Equals

위에서 살펴본 것처럼 HashMap에 저장 될 때는 HashCode를 생성 후 이 HashCode에 해당하는 데이터를 확인한다. 만약 아무 데이터도 없다면 바로 저장하면 되고, 데이터가 있다면(해시 충돌) equals()함수를 통해 객체 비교를 진행 후 데이터의 저장 여부를 결정하게 된다.

그런데 hashCode를 내 기준으로 만들어야 할 때가 있다. 이럴 경우 hashCode() 함수를 오버라이딩 할 수 있는데, 오버라이딩 한 hash 함수 기준으로 같다고 판단되어야 할 객체가 다르다고 판단 될 수 있다. 왜냐? equals는 객체가 같은지 비교하기 때문이다. 따라서 hashCode()를 오버라이딩 할 경우 equals도 적절히 오버라이딩 해주어야 한다.

• ==는 원시타입의 경우 값을 비교하지만, 참조타입의 경우 주소값을 비교한다.
• String의 euqals()는 값을 비교한다. 따라서 같은 문장인지 비교가 필요할 경우에는 equals()를 사용해야 한다.
• equals()와 hashCode()는 모두 최상위 클래스인 Object의 메소드다. 이때 equals()함수 내부는 ==으로 구현되어 있어 객체의 주소값을 비교하게 된다.

TreeMap

• Binary Search Tree의 형태(레드 블랙 트리)로 저장

🎰 Set

주요 메소드로 add, iterator, size, remove, clear 등이 있다.

HashSet

HashMap을 사용하여 구현되어 있다.

Hasing

• O(1)
• 충돌 발생 가능
• 해싱테이블은 꽉 차게 쓰지 않는다 (충돌 방지), 75% 정도 쓰면 테이블 확장

TreeSet

• Binary Search Tree(RBT)를 사용한다

• 비교 대상 객체에 Comparable이나 Comparator 인터페이스를 구현 해야 TreeSet에 추가될 수 있다 (JDK의 많은 클래스들이 이미 Comparable을 구현해 놓았다)

• first() 최소값 <-> last() 최대값, higher(value) 입력값보다 큰 데이터 중 최소값 <-> lower(value) 입력값보다 작은 데이터 중 최대값

Binary Search Tree

• 유일한 키, 중복된 키를 허용하지 않는다.
• log2n을 보장하기 위해 쓰는 것이다
• 트리가 너무 망가지며 중간값을 다시 만들어줘야 한다

🚴🏻‍♀️ Queue

메소드	예외 발생	값 리턴
euqueue	add	offer(실패시 false)
dequeue	remove	poll(실패시 null)
peek	element	peek(실패시 null)