[한권떼기] 자바의정석 챕터11. 컬렉션 프레임워크

**자바의 정석(남궁성 저)를 읽고 정리한 글입니다.

 

 

컬렉션 프레임워크

데이터 군을 저장하는 클래스들을 표준화한 설계

Vector, Set과 같이 다수의 데이터를 저장할 수 있는 클래스를 컬렉션 클래스라고 함



https://static.javatpoint.com/images/java-collection-hierarchy.png, https://www.javatpoint.com/java-map

컬렉션 프레임워크에서는 List, Set, Map이 있는데 이 때 List와 Set은 Collection 클래스를 상속받았으나 Map은 상속받지 않았음

 

List: 순서O, 중복O ex. 대기자 명단 -> 구현클래스: ArrayList, LinkedList, Stack, Vector ...

Set: 순서X, 중복X ex. 정수집합 -> 구현클래스: HashSet, TreeSet ...

Map: 키와 값의 쌍으로 이루어짐. 순서X, 키는 중복X 값은 중복O -> 구현클래스: HashMap, TreeMap, Hashtable, Properties ...

 

 

List

ArrayList

기존의 Vector(thread-safe O)를 ArrayList(thread-safe X)로 개선함.

배열에 순서대로 저장되고, 저장 공간이 더 이상 없으면 사이즈가 더 큰 새로운 배열을 생성해 기존 배열의 내용을 복사 (처리시간이 많이 소요됨)

만약 크기가 충분하지 않으면 2배로 크기를 증가시킴

 

장점

데이터를 읽어오고 저장하는 효율이 좋음.

단점

용량 변경 시 새로운 배열 생성이 필요.

비순차적인 데이터 삭제시 다른 데이터들을 빈 곳에 옮기는 식으로 복사가 이루어짐.

 

LinkedList

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

각 노드들이 연결되어있고, 노드는 다음 요소에 대한 주소값과 데이터를 갖고 있음

DoubleLinkedList: 이전, 다음 요소에 대한 주소값을 모둔 가진 LinkedList

DoublyCircularLinkedList: 첫번째 요소의 이전 요소와 마지막 요소를 연결한 LinkedList

 

장점

데이터 삭제시 복사 과정 없이 참조값만 변경하면 됨.

단점

순차적인 추가/삭제는 ArrayList가 더 빠름.

데이터를 읽는 것이 느림.

데이터가 많을수록 접근성이 떨어짐.

 

Stack과 Queue

Stack

LIFO(선입후출)로 되어있음

순차적으로 데이터를 추가하므로 ArrayList로 구현

ex. 웹에서의 뒤로가기, 수식괄호검사

Queue

FIFO(선입선출)로 되어있음

데이터의 추가/삭제가 쉬운 LinkedList로 구현

ex. 버퍼, 대기목록

PriorityQueue: 우선순위가 높은 것부터 꺼내는 Queue. 힙을 사용함.

DeQue: 양쪽 끝에 추가/삭제가 가능한 클래스

 

Arrays

배열을 다루는 데에 유용한 메소드가 정의되어있는 클래스

parallel로 시작하는 메소드들은 여러 쓰레드가 작업을 나누어 처리하도록 하는 동시성처리가 이루어짐

 

 

 

Set

HashSet

Set 인터페이스를 구현한 대표적인 컬랙션

순서를 유지하지 않음

HashSet의 add 메소드는 set에 중복된 데이터가 있는지 확인하는 데에 해시코드를 사용하므로, equals()와 hashCode()의 오버라이딩이 필요

equals()와 hashCode()?
equals(): 참조값이 가리키는 객체의 내부 값이 동일한지 확인하기 위한 메소드
hashCode(): 객체 내부의 값의 해시값을 구하기 위한 메소드
equals() 내부에서 보통은 hashCode() 메소드로부터 얻은 값과 비교하여 동일한 값을 가진 객체인지 판단합니다.
뿐만 아니라 hashCode() 호출은 해싱을 사용하는 곳에서 사용되는 메소드에서도 이루어집니다.
따라서 값이 다른 객체라면 다른 hashCode()값을 반환하여 해싱의 성능을 향상시키는 것이 좋습니다.

 

TreeSet

이진 검색 트리라는 자료구조의 형태를 가진 클래스

정렬, 검색, 범위검색에서 좋은 성능을 가짐

데이터가 정렬된 위치게 저장되므로 저장 순서를 유지하지 않음

이진검색트리(Binary Search Tree)?
모든 노드가 최대 두 개의 자식노드를 가지고, 부모 노드 값은 기준으로 왼쪽 자식노드에는 작은 값, 오른쪽 자식 노드에는 큰 값이 옵니다.
범위 검색과 정렬에 유리하고, 중복된 값을 저장할 수 없습니다.
순차적으로 저장하지 않기때문에 노드의 추가 및 삭제에는 시간이 걸립니다.

 

 

Map

HashMap과 Hashtable

Hashtable(thread-safe O)은 이전에 사용하던 버전으로, 새로 만들어진 HashMap(thread-safe X)을 사용하는 것을 권장

키-값의 구조로 묶어 하나의 데이터로 저장

해싱을 사용하기 때문에 많은 양의 데이터를 다루기에 적합

 

TreeMap

이진검색트리의 형태로 키와 값의 쌍으로 이루어진 데이터

검색과 정렬에 적합함

검색의 경우엔 HashMap이 TreeMap보다 더 성능이 좋고, 범위검색이나 정렬의 경우에는 TreeMap이 더 좋음

 

해싱과 해시함수

해싱이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법

해시함수를 통해 나온 값을 토대로 데이터가 있는 곳을 빠르게 찾아갈 수 있어 다량의 데이터 환경에서도 효율이 좋음

HashMap의 크기를 적절하게 지정하고, 중복된 해시코드의 값을 최소화하는 것이 좋음 (ex. 객체의 주소를 사용)