[Java] 자료구조 및 컬렉션 시간복잡도 정리

계속 업데이트 예정

Intro

Java에서 사용하는 Collection 및 여러 자료구조들의 복잡도 요약입니다.
나를 포함한 모두가 기술면접 및 코딩테스트에서 편하게 활용할 수 있길 바라며..ㅎ

Set

중복값을 허용하지 않는 특징을 가짐

HashSet

• 순서없이 저장
• thread-safe 하지 않음
• Null 값의 저장이 가능함
• Hash Table

HashSet<> set = new HashSet<>();

set.add(); // O(1)
set.contains(); // O(1)
next(); // O(h/n), h는 해시 버켓 사이즈 n은 데이터 사이즈

LinkedHashSet

• 순서가 있음
• thread-safe 하지 않음
• Null 값의 저장이 가능함
• Hash Table + LinkedList

LinkedHashSet<> set = new LinkedHashSet<>();

set.add(); // O(1)
set.contains(); // O(1)
next(); // O(1)

TreeSet

• thread-safe 하지 않음
• Null 값의 저장 불가
• 다른 Set Collection에 비해 느림
• Red Black Tree

LinkedHashSet<> set = new LinkedHashSet<>();

set.add(); // O(logn)
set.contains(); // O(logn)
next(); // O(logn)

Map

key , value 형태로 구성된 entry 객체를 저장하는 자료구조

HashMap

• 순서를 구분하지 않음
• Null 값 저장 허용

HashMap<T> map = new HashMap<>();

map.get(); // o(1)
map.containsKey(); // o(1)
map.next(); // O(h/n), h는 해시 버켓 사이즈 n은 데이터 사이즈

HashMap vs HashTable

• HashMap : 동기화 지원 x
• HashTable : 동기화 지원 , Thread-safe

LinkedHashMap

• 순서를 구분
• Null 값 저장 허용
• Thread-safe 아님

Map<T> map = new LinkedHashMap<>();

map.get(); // o(1)
map.containsKey(); // o(1)
map.next(); // O(1)

TreeMap

• Null 값 저장 허용하지 않음
• Thread-safe 아님

Map<T> map = new TreeMap<>();

map.get(); // o(logn)
map.containsKey(); // o(logn)
map.next(); // O(logn)