[Java]ArrayDeque

ArrayDeque란?

위위 사진은 ArrayDeque의 상속, 확장 구조 및 설명이다. 아래 접은 글은 번역이다.

 

"Deque 인터페이스의 크기 조정 가능한 어레이 구현. 어레이 데크에는 용량 제한이 없으며 필요에 따라 확장되어 사용량을 지원합니다. 외부 동기화가 없는 경우 여러 스레드에 의한 동시 액세스를 지원하지 않습니다. null 요소는 사용할 수 없습니다. 이 클래스는 스택으로 사용할 때 Stack보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠릅니다.
대부분의 ArrayDeque 작업은 상각된 상수 시간으로 실행됩니다. 제거, 제거 첫 번째 발생, 제거 마지막 발생, 포함, 반복기.remove() 및 대량 작업은 모두 선형 시간으로 실행됩니다.
이 클래스의 반복기 메서드에 의해 반환되는 반복기는 실패 속도가 빠릅니다. 반복기 생성 후 언제든지 데크가 수정되는 경우, 반복기의 자체 제거 방법을 제외하고 어떤 방식으로든 반복기는 일반적으로 동시 수정기를 던집니다.예외 따라서 동시 수정에 직면했을 때, 반복자는 미래에 결정되지 않은 시간에 임의의 비결정론적 행동을 위험하기 보다는 빠르고 깨끗하게 실패한다.
일반적으로 말해서, 동기화되지 않은 동시 수정이 있을 때 확실한 보장이 불가능하기 때문에 반복자의 페일패스트 동작은 보장할 수 없다는 점에 유의한다. Fail-Fast 반복기 동시 수정 실행최선의 노력을 바탕으로 한 예외입니다. 따라서, 정확성을 위해 이 예외에 의존하는 프로그램을 쓰는 것은 잘못된 것일 수 있다: 반복자의 fail-fast 동작은 버그를 감지하는 데만 사용되어야 한다.
이 클래스와 해당 반복기는 수집 및 반복기 인터페이스의 모든 선택적 방법을 구현합니다.
이 클래스는 Java Collection Framework의 구성원입니다. "

 

중요한 특징을 간략하게 요약해보자면,

• 사이즈에 제한이 없다.
• 외부 동기화 안됨. 즉 멀티 쓰레드에서 동시 접속 안됨.
• null 요소는 저장되지 않음.
• 스택으로 사용할 때 Stack보다 빠르며, 대기열로 사용할 때는 LinkedList보다 빠르다.

여러가지 특징이 있지만, 맨 아래  밑줄친 문장이 ArrayDeque를 쓰는 이유라고 볼 수 있을 것 같다.

 

한 가지 더 덧붙혀 말하자면, 

 

공식 문서에서

Using the Deque interface is the most convenient approach for LIFO data structures as it provides all the needed stack operations

라고 하였다.

 

즉, LIFO 구조를 만들기 위해 적합한 클래스는 Deque 인터페이스를 구현하는 ArrayDeque 클래스 라는 말.

 

근데 위의 특징을 보면 ArrayDeque는 Thread-Safe하지 않다는 단점이 있다. 그럼 멀티쓰레드 환경에선 문제가 있다.

 

그래서 pop(), push(), peek() 등에 synchronized를 이용해 ArrayDeque을 구현하면 된다.

 

예를 들자면 아래와 같이

    public synchronized void push(T element) {
        this.arrayDeque.push(element);
    }

Stack보다 ArrayDeque가 빠른 이유는 뭘까? 왜 ArrayDeque를 추천하는 것일까?

첫째, Stack의 내부를 보면 모든 메소드에 synchronized가 있기 때문에 단일 스레스 환경에서는 성능이 떨어진다.

 

둘째, Stack는 

 

 

Vector 클래스를 상속받았기 때문에 LIFO 구조를 유지하는 것이 아니라 중간에서 데이터를 삭제하고 삽입하는 것이 가능하다.

 

셋째는, Stack 클래스를 만들 때 초기 용량을 설정할 수 없다.

 

이런 단점을 보완하기 위해서 LIFO 구조를 만들 때 ArrayDeque을 사용한다고 볼 수 있겠다.

동작 방식 살펴볼까?

위에서 말했다시피 크기에 제한이 없고, 배열의 최초 크기는 16인 것을 알 수 있다.

생성자를 통해서 배열의 초기 크기도 지정할 수 있다.

 

그런데 최초 크기인 16을 넘어가면 어떻게 될까? 궁금해서 grow, newCapacity 메서드를 보았다.

 

코드가 장황하지만, grow의 아래의 로직과

int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

newapacity의 아래 로직을 보니

        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
            ? oldCapacity + jump
            : MAX_ARRAY_SIZE;

정리하자면 용량이 초과하면 자동으로 용량을 늘려준다.

• 기존 용량이 64보다 작으면 기존용량 + jump(기존용량 + 2)로 늘려준다. 즉, 거의 2배로 늘려준다.
• 기존 용량이 64보다 크면 기존 용량 + jump(원래 용량 / 2)로 늘려준다. 즉, 1.5배로 늘려준다.

 

출처 :

www.baeldung.com/java-lifo-thread-safe