[Java] 컬렉션

자바의 컬렉션과 동작원리에 대해 알아보자

Array

int[] arr = new int[N];

• 동일한 타입 + 고정된 크기 + 연속적인 저장
• 변수는 메모리 주소를 저장하며, 실제 데이터는 일련의 메모리 공간에 할당되어 저장
• 데이터 조회
  • 인덱스를 통한 조회 -> O(1)
  • 값을 탐색할때 -> O(N)

List

• 자바에서는 List 인터페이스를 상속받은 여러 자료구조가 존재함
• 동일한 타입 + 가변 크기 + 연속적 저장
• 구현체 종류 : Vector, ArrayList, LinkedList, Stack

Vector & ArrayList

List<Integer> v = new Vector<>();
List<Integer> al = new ArrayList<>();

• 내부적으로 가변 배열을 저장하는 방식
• 내부 배열이 가득 차면 기존 배열 데이터를 새로운 크기의 배열에 복사하는 방식을 씀
  • 데이터 추가/삭제시 내부 배열또한 덮어쓰기 방식으로 데이터를 이동시켜야함
• 두 컬렉션의 차이점
  • Vector는 synchronized로 동기화되어 thread safe하므로, ArrayList의 성능이 더 좋음
  • Vector는 배열 증가시 기존배열의 2배로 증가하고, ArrayList는 1.5배로 증가함
  • default capacity는 10
• 정리
  • 장점 : 배열 사용으로 데이터 접근 속도가 빠름 -> O(1)
  • 단점 : 중간 데이터 추가/삭제시 내부 배열 복사가 일어나 비효율적 -> O(n)

LinkedList

List<Integer> ll = new LinkedList<>();

• 내부적으로 노드를 연결한 구조로 되어있음
  • 각 노드는 데이터와 다음 노드 주소를 저장
  • 단방향으로 노드들이 연결되므로 이전 노드 접근은 안됨
  • But!!! 자바의 LinkedList는 내부적으로 이중연결리스트로 구현되어있음
• 정리
  • 장점 : 중간 데이터 추가/삭제시 시간이 빠름 -> O(1)
  • 단점 : 인덱스가 없으므로 데이터 접근 시간이 느림 -> O(n)

DoubleLinkedList

자바에는 이중연결리스트를 구현한 컬렉션은 없음

• 양방향으로 노드가 이전 노드와 다음 노드의 주소를 저장함
• 탐색시 두 방향으로 탐색이 가능해서 연결리스트보다 탐색속도가 반으로 줄어듬
  • 맨 앞 노드부터 오른쪽 방향
  • 맨 뒤 노드부터 왼쪽 방향
• 정리
  • 장점 : 단방향 연결리스트의 탐색속도 단점을 보완
  • 단점 : 이전 노드 주소를 저장함으로써 메모리 낭비

Map

• key-value 두 데이터를 쌍으로 저장하는 자료구조
• 데이터 조회시 O(1)
• 구현체 종류 : Hashtable, HashMap, ConcurrentHashMap,LinkedHashMap, TreeMap

Hashtable & HashMap

Map<Integer> ht = new Hashtable<>();
Map<Integer> hm = new HashMap<>();

• 해시코드를 사용하여 중복을 제거함
• 저장 순서를 보장하지 않는다.
• 내부적으로 버킷 배열이 존재하여 데이터를 저장
  • 버킷 배열의 크기는 16배수로 증가함
  • 버킷 인덱스 = (데이터의 해시코드) % 버킷길이
  • 버킷의 임계값(load factor) 75%가 차면 버킷 크기를 2배로 늘림
• 자바는 해시 충돌 전략으로 분리연결법을 사용한다
  • 개방주소법
    • 충돌 발생시 비어있는 인덱스를 찾아 저장하는 방식
    • 해시코드 탐색시 O(1)
    • 버킷 사이즈가 커질수록 해시코드 탐색이 어려워짐
    • 데이터 추가/삭제시 해시코드 재정렬이 필요함
  • 분리연결법
    • 연결리스트나 트리 같은 자료구조를 사용하여 다음 노드를 추가하는 방식
    • 해시코드 탐색시 O(1) + 리스트에서 탐색시 O(n)
    • 메모리를 많이 소비함
• 두 컬렉션의 차이점
  • Hashtable는 synchronized로 동기화되어 thread safe하므로, HashMap이 더 빠르다.
  • Hashtable은 key로 null을 허용하지 않지만, HashMap은 하나의 null을 허용한다

ConcurrentHashMap

Map<Integer> chm = new ConcurrentHashMap<>();

• HashMap에 동기화처리를 하여 멀티스레드 환경에서 사용할 수 있도록 함
• Hashtable은 synchronized가 메소드 전체에 붙어있는 반면, ConcurrentHashMap은 코드블럭에 붙임
  • 따라서 조회시엔 block이 걸리지 않고, 변경시에만 block됨

LinkedHashMap

Map<Integer> lhm = new LinkedHashMap<>();

• HashMap과 동일하지만, 저장 순서를 보장한다.
  • 순서를 유지하기 위해 이중연결리스트를 사용함
  • 때문에 HashMap보다 많은 메모리를 사용하며, 성능이 떨어진다.

TreeMap

Map<Integer> tm = new TreeMap<>();

• key가 정렬된 HashMap
  • 정렬을 위해 Red-Black 트리가 사용된다
  • 따라서 데이터 삽입시 내부적으로 정렬이 일어난다 -> O(logN)
  • 조회시에도 트리에서 key를 탐색해야 한다 -> O(logN)

Set

• 중복된 요소를 저장하지 않는 자료구조
• 저장순서를 유지하지 않음
• 구현체 종류 : HashSet, LinkedHashSet, TreeSet

HashSet

Set<Integer> hs = new HashSet<>();

• 내부에서 HashMap으로 중복을 제거한다
  • key : 저장하려는 데이터
  • value : dummy object
  • 사실상 value는 필요없으므로 HashSet 객체 생성시 더미는 싱글톤으로 동작한다.

Queue + Stack

Queue

Queue<Integer> q = new LinkedList<>();

• 선입선출 자료구조
• 앞쪽(front)으로는 삭제(poll), 뒤쪽(rear)로는 삽입(offer)을 수행
• 적절한 사용 : 메시징 큐, 실시간 대기열
• 구현체 종류 : LinkedList, PriorityQueue

Stack

List<Integer> s = new Stack<>(); 
Vector<Integer> s = new Stack<>(); 
Stack<Integer> s = new Stack<>(); 

• 후입선출 자료구조
• 뒤쪽(top)에서 데이터 삽입(push),삭제(pop)가 일어난다
• 적절한 사용 : jvm stack 메모리, memento 패턴 등
• List -> Vector 인터페이스의 구현체이다

Deque

Queue<Integer> d = new ArrayDeque<>(); 
Deque<Integer> d = new ArrayDeque<>(); 

• Double Ended Queue
• 큐의 양쪽으로 데이터를 넣고 뺄 수 있는 자료구조
• Queue 와 Deque 인터페이스의 구현체이다.