개발 *´꒳`*/Java

[Java] List와 Map의 구조와 스레드 안전성

winterlove 2024. 8. 8. 18:02

0. Thread Safe란?

멀티스레드 환경에서 여러 스레드가 동시에 함수, 변수, 객체 접근하여도 일관성, 정확성을 유지할 수 있는 특성

스레드란?
프로세스 내에서 실행되는 가장 작은 단위의 실행 흐름.
동일 프로세스 내에서 메모리, 자원을 공유하며 독립적으로 실행될 수 있다.

동시성 문제

  • 데이터 레이스 : 여러 스레드가 동시에 접근하여 읽기/쓰기 작업 시 예상치 못한 결과 발생
  • 데드락 : 두 개 이상 스레드가 서로 자원을 점유한 상태에서 다른 스레드 자원을 기다리며 영원히 대기
  • 라이브락 : 스레드들이 서로 방해하지 않기 위해 끊임없이 상태를 바꾸며 진행하지 못하는 상황
  • 자원 고갈 : 하나 이상 스레드가 자원을 독점해 다른 스레드가 필요자원을 얻지 못하는 상황

안정 보장법

  • Synchronization(동기화) : synchronized를 메서드, 블록에 동기화하여 한 번에 하나 스레드만 접근할 수 있도록 한다.
  • Lock : ReentrantLock을 통해 동기화 블록보다 유연한 락을 제공
  • Concurrent Collections(동기화 컬렉션) : java.util.concurrent 패키지를 통해 멀티 스레드 환경에서 안전하게 사용

 

1. List란?

배열과 같이 객체가 일렬로 늘어져있는 구조이다.
객체를 인덱스로 관리하기에 저장 시 자동으로 인덱스가 부여되며 추가/삭제/검색 등의 기능을 제공한다.
순서가 있으며 중복을 허용하고 크기가 오버 시 자동으로 할당되어 늘어나는 가변적인 구조다.

  • ArrayList : List 인터페이스를 구현한 클래스, Vector가 개선된 것으로 많이 사용
    • 내부적으로 배열을 사용하여 요소 저장
    • 인덱스 기반으로 빠르게 접근 가능하나 추가/삭제 시 배열 재조정 필요하기에 느리다.
    • 평균적으로 O(1)의 시간 복잡도를 가지나 추가, 삭제 시 O(n)의 복잡도를 가지며 전체 요소 이동한다.
    • 데이터가 연속적으로 존재하여 데이터 순서 유지
    • 저장 용량 초과 시 자동으로 용량을 늘림
    • 비동기 클래스
  • LinkedList : 불연속적으로 존재하며 서로 연결, 각 노드가 자신과 연결된 이전, 이후 요소의 주소값을 갖고 있다.
    • 이중 연결 리스트
    • 추가/삭제가 빠르나 인덱스 기반으로 접근은 느리다.
    • 평균적으로 O(1)의 시간 복잡도를 가지나 임의 접근 시 O(n)의 복잡도를 가지며 리스트를 순회한다.
    • 비동기 클래스
  • Verctor
    • ArrayList와 유사하지만 synchronized(스레드안전) 보장
    • 동기화 메서드를 사용하므로 멀티 스레드 환경에서 안전
  • CopyOnWriteArrayList : Java1.5부터 사용 가능하며 순회 시 락이 필요 없어 매우 빠름
    • 스레드 안전한 ArrayList의 구현 (1.5 이전에는 synchronized를 이용해 동시성 제어가 필요했음)
    • 쓰기 작업 일어날 때마다 배열 복사. List를 읽기 위해 전달 시 원본이 아닌 복사본을 만들어 전달
    • 읽기 작업이 빈번하고 쓰기 작업이 드문 경우에 유용함

 

2. Map이란?

Key - Value 쌍으로 이루어진 요소들의 집합이다.
저장 순서를 유지하지 않는다.
Key는 실질적인 값(Value)을 찾기 위한 이름 역할이며 Key가 중복될 수 없다. (Value는 허용)
Key값이 중복하여 put 하는 경우, Value값을 갱신

  • HashMap
    • 해시 테이블 기반으로 한 구현
    • 순서 보장 X
    • key, value에 하나씩 null을 허용
    • 해시 테이블을 사용해 데이터를 저장하여 평균 O(1)의 시간 복잡도
    • 메모리 사용량이 높을 수 있음, 해시 충돌이 빈번한 경우 추가적인 메모리 오버헤드 발생할 수 있음
    • 비동기 클래스
  • LinkedHashMap
    • HashMap과 유사하지만 입력된 순서대로 순서 유지
    • 요소 간 연결 위한 추가 메모리 사용
    • 순서가 중요한 데이터 저장 시 유용
    • 비동기 클래스
  • TreeMap
    • 이진 검색 트리(레드-블랙 트리) 기반의 구현
    • 삽입, 삭제, 조회 등의 연산 모두 O(log n)의 시간 복잡도
    • 입력된 Key순으로 정렬
    • 비동기 클래스
  • Hashtable
    • HashMap과 유사하지만 스레드 안전 보장하지만 동시에 접근 시 성능 저하
    • 단일 스레드 환경에서는 HashMap보다 느림
    • 동기화(Synchronized) 메서드를 사용하므로 멀티스레드 환경에서 안전
    • key, value에 null을 허용하지 않음 ( HashMap은 한 개씩은 허용, Key null 하나 Value null 하나 )
    • 해시 테이블 기반하여 데이터 저장하기에 평균 O(1)의 시간 복잡도로 작업 수행
    • Java 1.2 이후로는 ConcurrentHashMap을 주로 사용함
  • ConcurrentHashMap
    • 스레드 안전한 HashMap의 구현
    • 높은 동시성으로 여러 스레드가 동시에 접근하여 수정할 수 있음 (Hashtable, HashMap보다 높은 동시성)
    • 동시성 높이기 위해 Concurrent Locking(분할잠금) 메커니즘 사용 (병렬처리가 가능하다)
    • 높은 동시성에서도 좋은 성능 발휘
    • key,value에 null을 허용하지 않음
    • 대규모 멀티스레드, 캐시 구현, 실시간 데이터 처리 시 유용

 

최종 정리

List
ArrayList 동적 배열 기반, 빠른 인덱스 접근, 삽입 및 삭제 시 성능 저하
LinkedList 이중 연결 리스트 기반, 빠른 삽입 및 삭제, 느린 인덱스 접근
Vector 동적 배열 기반, 동기화 제공, 성능 저하로 ArrayList 선호
CopyOnWriteArrayList 동적 배열 기반, 읽기 성능 우수, 쓰기 성능 저하, 쓰기 연산 시 배열 복사하여 사용
Map
HashMap 빠른 조회와 삽입, 순서 없으며 null O, 비동기화
LinkedHashMap 삽입, 접근 순서 유지, null O, 비동기화
TreeMap 키 순서로 정렬, null O  
정렬 키를 유지하는 레드-블랙 트리 기반
Hashtable 순서X, null X, 동기화된 해시 테이블,
멀티 스레드 환경에서 안전하나 성능저하 있을 수 있음
ConcurrentHashMap 순서X, null X, 높은 동시성 제공하는 해시 테이블
세분화된 잠금으로 성능 유지

 

저작자표시 비영리