Map과 Deque 시간 복잡도

Map 시간 복잡도

Map은 해시 테이블로 구현된 HashMap과 LinkedHashMap이 있습니다.

Map은 키와 값을 하나의 쌍으로 저장하는 방식을 사용하고 엘리먼트 추가, 삭제, 조회 모두 O(1)이 소요되는 효율적인 자료형입니다. 물론 최악의 경우에는 키 충돌이 발생해 O(n)이 될 수 있지만 분할 상환 분석에 따라 시간 복잡도는 여전히 O(1)입니다. 하지만 기본적으로 HashMap은 입력 순서가 보장되지 않습니다.

 

이를 보완하기 위해 연결 리스트를 함께 사용하여 입력 순서를 유지한 LinkedHashMap이 있습니다.

덕분에 한결 편리하게 Map을 사용할 수 있습니다. 심지어 코틀린에서는 Map의 기본 자료형은 LinkedHashMap을 사용하여 입력 순서를 보장합니다.

 

Map을 사용한 연산의 시간 복잡도는 아래와 같습니다.

연산	HashMap	LinkedHashMap
추가	O(1)	O(1)
삭제	O(1)	O(1)
조회	O(1)	O(1)

 

연결 리스트를 추가로 활용하는 LinkedHashMap이지만 HashMap과 실제 속도 차이가 크지 않습니다. 물론 LinkedHashMap이 살짝 더 느리지만 사실상 동일한 성능이라고 봐도 무방합니다. 오히려 LinkedHashMap이 조회 속도는 HashMap 보다 살짝 더 빠릅니다.

 

Deque 시간 복잡도 

 

 

Deque 자료형은 양쪽에서 삽입과 삭제를 할 수 있는, 스택과 큐의 연산을 모두 갖고 있는 자료형입니다.

Deque의 구현체로는 ArrayDeque와 LinkedList가 있습니다. 실제로는 동적 배열로 구현된 ArrayDeque가 좀 더 널리 사용됩니다. 

 

Deque를 이용한 연산의 시간 복잡도는 아래와 같습니다.

연산	ArrayDeque	LinkedList
삽입	O(1)	O(1)
추출	O(1)	O(1)

 

Deque의 구현체인 ArrayDeque는 자바에서 스택과 큐를 대체하는 역할을 하는 매우 중요한 자료형입니다.

자바의 Stack 자료형은 성능에 문제가 있어 실제로는 사용을 지양해야 합니다. 만약 스택을 구현할 때는 모두 ArrayDeque를 사용하는 것을 권장합니다.

 

Deque는 Queue를 상속받는 인터페이스이기 때문에 기본적으로 삽입과 추출 연산이 중심입니다. 조회나 삭제도 편의를 위해 제공하지만 삽입과 추출 연산이 중심입니다. Deque 자료구조가 지원하는 함수들은 아래와 같이 있습니다.

 

그렇다면 Deque를 구현하는 ArrayDeque와 LinkedList 모두 O(1)의 시간 복잡도를 가지지만 왜 ArrayDeque를 주로 사용할까요? 이 이유도 실제 속도에 있습니다. 지금부터 ArrayDeque와 LinkedList의 실제 속도를 비교해 보겠습니다.

 

동적 배열로 구현된 ArrayDeque는 엘리먼트 삽입마다 노드를 생성해야 하는 LinkedList 보다 엘리먼트 삽입 속도가 빠릅니다. 아래 코드로 확인해 봅시다.

Deque<Integer> arrayDeque = new ArrayDeque<>();
// ArrayDeque<Integer> 1억 개 삽입
for (int i = 0; i < 100000000; i++)
    arrayDeque.offer(1);
    
Deque<Integer> linkedList = new LinkedList<>();
// LinkedList<Integer> 1억 개 삽입
for (int i = 0; i < 100000000; i++) 
    linkedList.offer(1);

 

삽입 작업의 실행 속도는 아래와 같습니다.

• ArrayDeque<Integer> 1억 개 삽입 : 2274밀리초
• LinkedList<Integer> 1억 개 삽입 : 17228밀리초

별도의 노드를 생성해야 하는 LinkedList가 ArrayDeque 보다 8배 가까이 느린 것을 알 수 있습니다.

그렇다면 객체 생성이라는 비싼 작업이 수반되지 않는 추출 시간은 어떨까요? 노드 생성을 하지 않기 때문에 LinkedList와 ArrayDeque가 비슷한 속도임을 예상할 수 있습니다. 아래 코드로 확인해 봅시다.

// ArrayDeque<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++)
    arrayDeque.poll();
    
// LinkedList<Integer> 10만 개 추출
for (int i = 0; i < 100000; i++)
    linkedList.poll();

 

추출 작업의 실행 속도는 아래와 같습니다.

• ArrayDeque<Integer> 10만 개 추출 : 8밀리초
• LinkedList<Integer> 10만 개 추출 : 6밀리초

실제로 추출 작업에 있어서는 두 자료구조가 매우 빠른 속도로 큰 차이를 보이지 않았습니다.

 

하지만 삽입에는 속도 차이가 많이 나기 때문에 코딩 테스트나 실무에서는 동적 배열로 구현된 ArrayDeque를 더 널리 사용한다고 합니다. 같은 이유로 List의 구현체도 동적 배열로 구현된 ArrayList를 LinkedList 보다 훨씬 더 널리 사용한다고 합니다. 

 

특별한 이유가 없다면, ArrayList와 ArrayDeque를 활용하도록 합시다.