[Java 21] 순차 컬렉션 Sequenced Collections

yammmie·2024년 1월 8일

Java

목록 보기

3/9

컬렉션 프레임워크

자바의 컬렉션은 여러 개의 요소를 묶어 하나로 만든 그룹 객체(컨테이너)를 의미함
이러한 컬렉션을 다루기 편하도록 컬렉션 프레임워크라는 통합된 하나의 구조로 만듦
분리되어 있는 Map도 컬렉션에 속함
- List, Queue, Set은 요소(element)를 갖고 있지만, Map은 키과 값의 쌍으로 이루어져 있기 때문에 설계상 이유로 분리

장점

API의 일관성을 통해 프로그래머가 학습하기 쉬움
설계 시 확장이 용이함
기존에 만들어진 알고리즘 재사용 가능

요약

순서가 있는 컬렉션을 표현하기 위해 추가된 새로운 인터페이스
각 컬렉션에 첫 번째 요소부터 마지막 요소까지 잘 정의되어 있음
첫 번째 요소와 마지막 요소에 접근하고, 요소를 역순으로 처리하기 위한 API 제공

동기

이전 자바의 컬렉션 프레임워크는 순서가 있는 시퀀스를 나타내는 컬렉션에 대한 일반적인 슈퍼 타입의 부재
- 여기서 사용되는 시퀀스는 순서대로 배열된 요소를 의미함
컬렉션 전반에 적용되는 첫 번째와 마지막 요소에 액세스하고 역순으로 반복하는 통일된 연산의 부재

⇒ 반복적인 문제와 불만의 원인

예를 들어 List, Deque 둘 다 순서가 있지만, 그들의 일반적인 슈퍼 타입인 Collection은 그렇지 않음

마찬가지로 Set과 HashSet과 같은 서브타입은 순서가 없지만, SortedSet, LinkedHashSet과 같은 일부 서브타입은 순서가 있음

API가 정의된 요소 순서를 가진 컬렉션을 받고자 한다면, List를 사용하는 것은 SortedSet과 LinkedHashSet을 제외했기 때문에 너무 구체적이었음

관련된 문제는 뷰 컬렉션이 종종 더 약한 의미로 다운그레이드되어야 한다는 것

예를 들어 LinkedHashSet을 Collections::unmodifiableSet으로 감싸면 세트가 생성되고 만남 순서에 대한 정보는 폐기되기 때문

요소의 순서에 대한 지원은 타입 계층 구조 전반에 퍼져있으나 관련 작업은 통일된 방법이 없거나 누락되어 API에서 유용한 특정 개념을 표현하기 어려움

각 컬렉션이 첫 번째와 마지막 요소에 접근하는 방법

많은 구현이 첫번째 또는 마지막 요소를 얻는 것을 지원하지만 각 컬렉션은 고유한 방법을 정의하며 일부는 명확하지 않거나 완전히 누락됨

이중 일부는 List와 같이 마지막 요소를 얻는 것이 불필요하게 번거로움

LinkedHashSet의 마지막 요소를 얻는 유일한 방법은 전체 Set을 반복하는 것

모든 컬렉션은 Iterator, 향상된 for문, stream(), toArray()를 사용하여 순회할 수 있음

컬렉션의 요소를 처음부터 마지막까지 반복하는 것은 간단하고 일관적이지만 역순으로 반복하는 것은 둘 다 아님

역순으로 반복하기

역순으로 반복하는 것은 모든 케이스가 다름

SortedSet을 상속받는 NavigableSet은 역순으로 반복하기 위해 내림차순으로 정렬된 NavigableSet을 리턴하는 descendingSet()을 제공함

for (var e : navSet.descendingSet())
		process(e);

Deque는 descendingIterator를 사용하여 다음과 같이 수행함

for (var it = deque.descendingIterator(); it.hasNext();) {
		var e = it.next();
		process(e);
}

List는 ListIterator를 사용하여 다음과 같이 수행함

for (var it = list.listIterator(list.size()); it.hasPrevious();) {
		var e = it.previous();
		process(e);
}

마지막으로 LinkedHashSet은 역순 반복을 제공하지 않음

LinkedHashSet의 요소를 역순으로 처리하는 유일한 실용적인 방법은 요소를 다른 컬렉션에 복사하는 것

마찬가지로 스트림을 사용하여 컬렉션의 요소를 처리하는 것은 루프를 사용하여 요소를 처리하는 강력하고 효과적인 대안이지만, 스트림을 역순으로 얻는 것은 어려울 수 있음

요소 순서를 정의하는 다양한 컬렉션 중에서 이를 편리하게 지원하는 것은 NavigableSet뿐임

navSet.descendingSet().stream()

이것은 불행한 상황으로, 컬렉션 프레임워크에는 요소 순서가 정의된 컬렉션이라는 개념이 여러 곳에 존재하지만, 이를 대표하는 유형은 단 하나도 없음

컬렉션에 대한 일부 작업은 일관성이 없거나 누락되어 있으며, 역순으로 처리하는 요소는 불편함에서 불가능함까지 다양함

이러한 모든 차이점은 조각난 코드 베이스와 복잡성으로 이어졌고, API에서 유용한 특정 개념을 표현하는 것이 어려워졌기 때문에 우리는 이러한 공백을 메워야 함

기술

기존 컬렉션 계층에 추가된 sequenced collections, sequenced sets, sequenced maps를 위한 새로운 인터페이스

모든 새로운 메소드는 이 인터페이스에 기본 구현으로 선언됨

Sequenced collections

요소들이 정의된 순서를 가지는 컬렉션

여기서 사용되는 “sequenced”는 “특정 순서로 요소를 배열하는 것”을 의미하는 sequence의 과거 분사

첫 번째 요소와 마지막 요소를 가지며, 그 사이의 요소들은 이전 요소와 다음 요소를 가짐

양쪽 끝에서 요소를 추가, 가져오기, 삭제, 그리고 순방향과 역방향 반복 처리까지 지원함

reversed()

interface SequencedCollection<E> extends Collection<E> {
    // new method
    SequencedCollection<E> reversed();

    // methods promoted from Deque
    void addFirst(E);
    void addLast(E);

    E getFirst();
    E getLast();

    E removeFirst();
		E removeLast();
}

새로 추가된 reversed()는 원본 컬렉션의 역순으로 정렬된 뷰를 제공함

원본 컬렉션에 대한 수정 사항은 reverse 뷰에서 볼 수 있으나, 허용된 경우에는 수정 사항은 원본 컬렉션에 기록됨

역순 정렬 뷰는 다른 모든 sequenced 유형에서 일반적인 반복 매커니즘을 사용하여 양방향으로 처리 가능하게 함

향상된 for문, 명시적인 iterator(), forEach(), stream(), parallelStream(), toArray()

예를 들어 LinkedHashSet에서 역순으로 정렬된 스트림을 얻는 것은 이전에는 상당히 어려웠지만 이제는 단순해짐

linkedHashSet.reversed().stream()

reversed()는 SequenceCollection으로 나오면서 이름이 바뀐 NavigableSet::descendingSet임

SequencedCollection의 reversed()를 제외한 모든 메소드

Deque에서 온 것으로 default 메소드이며, deafult 구현을 제공함

그들은 양쪽 끝에서 요소 추가, 가져오기, 삭제를 지원함

void addFirst(E)
void addLast(E)
E getFirst()
E getLast()
E removeFirst()
E removeLast()

add*(E)와 remove*() 메소드들은 선택 사항이며, default 구현에서 UnsupportedOperationException을 던짐

주로 불변 컬렉션의 경우를 위한 것

get*()과 remove*() 메소드들은 컬렉션이 비어있으면 NoSuchElementException을 던짐

SequencedCollection에는 equals()와 hashCode()가 정의되어있지 않음

왜냐하면 그것의 하위 인터페이스 정의가 충돌하기 때문

Sequenced sets

중복 요소가 없는 SequencedCollection

interface SequencedSet<E> extends Set<E>, SequencedCollection<E> {
    // covariant override
    SequencedSet<E> reversed();
}

이 인터페이스는 Set::equals, Set::hashCode에 의해 정의된 equals와 hashCode 메소드에 대해 동일한 요구 사항을 가짐

Set과 SequencedSet은 순서에 관계없이 동일한 요소가 있는 경우에만 equals로 비교

SequencedSet에 역순 정렬 뷰를 제공하는 reversed() 메소드가 정의됨

SequencedCollection::reversed 메소드와의 유일한 차이점은 리턴 타입이 SequencedSet이라는 것

슈퍼 인터페이스 Sequenced Collection의 add*(E) 메서드는 LinkedHashSet, SortedSet에 대해서도 다음과 같은 특수한 경우 동작을 수행함

LinkedHashSet

addFirst(E), addLast(E) 메소드에는 LinkedHashSet과 같은 컬렉션에 대한 특수한 경우 의미를 가짐

LinkedHashSet은 요소가 이미 컬렉션에 있는 경우, 해당 항목을 재배치하여 적절한 위치로 이동함

LinkedHashSet의 요소를 재배치할 수 없다는 오랜 결함을 개선함

SortedSet

상대적인 비교를 통해 요소를 위치시키는 SortedSet과 같은 컬렉션은 SequencedCollection 슈퍼 인터페이스에 선언된 addFirst(E), addLast(E)와 같은 메소드와 같은 명시적 위치 지정 작업을 지원할 수 없음

이러한 방법은 UnsupportedOperationException을 던짐

Sequenced maps

항목이 정의된 만남 순서를 갖는 Map

SequencedMap은 SequencedCollection을 확장하지 않으며, 컬렉션 양쪽 끝에 있는 요소를 조작하는 자체적인 방법을 제공함

interface SequencedMap<K, V> extends Map<K, V> {
    // new methods
    SequencedMap<K, V> reversed();
    SequencedSet<K> sequencedKeySet();
    SequencedCollection<V> sequencedValues();
    SequencedSet<Entry<K, V>> sequencedEntrySet();

    V putFirst(K, V);
    V putLast(K, V);

    // methods promoted from NavigableMap
    Entry<K, V> firstEntry();
    Entry<K, V> lastEntry();
    Entry<K, V> pollFirstEntry();
    Entry<K, V> pollLastEntry();
}

새로운 put*(K, V) 메소드들은 SequencedSet::add*(E) 메소드들과 유사한 특별한 경우 의미를 가짐

LinkedHashMap

해당 항목이 Map에 이미 있는 경우 해당 항목의 위치를 변경하는 추가 효과가 있음

SortedMap

이러한 메소드는 UnsupportedOperationException을 던짐

SequncedMap의 다음 메소드는 NavigableMap에서 온 것으로, 양쪽 끝에서 항목을 가져오거나 제거하는 것을 지원함

Entry<K, V> firstEntry()
Entry<K, V> lastEntry()
Entry<K, V> pollFirstEntry()
Entry<K, V> pollLastEntry()

새로운 기능

위에서 정의한 세 개의 새로운 인터페이스는 기존 컬렉션 유형 계층에 깔끔하게 추가됨

자세한 내용은 기존 클래스와 인터페이스를 개조하기 위해 다음과 같이 조정함

List는 지금 SequencedCollection을 바로 위의 슈퍼인터페이스로 가짐
Deque는 지금 SequencedCollection를 바로 위의 슈퍼 인터페이스로 가짐
LinkedHashSet은 SequencedSet을 추가적으로 구현함
SortedSet은 지금 SequencedSet을 바로 위의 슈퍼 인터페이스로 가짐
LinkedHashMap은 추가적으로 SequencedMap을 구현함
SortedMap은 SequencedMap을 바로 위의 슈퍼 인터페이스로 가짐

적절한 곳에서 reversed() 메소드에 대한 공변 오버라이드를 수행함

예를 들어 List::reversed는 SequencedCollection 타입 값이 아닌 List 타입을 리턴하도록 재정의됨

또한 Collections 유틸리티 클래스에 불변 wrappers 세 가지 타입을 새로운 메소드로 추가함

Collections.unmodifiableSequencedCollection(sequencedCollection)
Collections.unmodifiableSequencedSet(sequencedSet)
Collections.unmodifiableSequencedMap(sequencedMap)

다른 대안

Type

새로운 유형을 추가하는 대안은 List 인터페이스를 일반적인 Sequenced Collection 타입으로 변경하는 것

실제로 List는 순서화되어 있지만 정수 인덱스에 의한 요소 접근도 지원함

많은 순서화된 데이터 구조들은 원래 인덱싱을 지원하지 않으므로 반복하는 것을 지원해야 함

이렇게 되면 인덱싱된 접근은 O(1)이 아닌 O(n)의 성능을 갖게 되어 LinkedList의 오류가 지속됨

Deque는 이미 올바른 연산 집합을 지원하기 때문에 일반 시퀀스 타입으로 유망해보임

그러나 그것은 null-returning 연산(offer, peek, poll), Stack 연산(push, pop), Queue에서 상속된 연산을 포함한 다른 연산들로 복잡함

offer: 큐 요소 추가 시, 큐가 꽉 차 있으면 false 리턴

peek: 큐 요소 제거 시, 큐가 비어 있으면 null 리턴

poll: 큐 맨 앞 요소 검색 시, 큐가 비어 있으면 null 리턴

이러한 연산은 Queue에는 적합하지만 다른 컬렉션에는 덜 적합함

만약 Deque가 일반 시퀀스 타입으로 용도 변경된다면, List는 Queue이면서 Stack 연산을 지원하므로 API가 혼란스러울 것

Naming

위에서 설명한 것과 유사한 의미를 갖는 컬렉션을 나타내기 위해 다양한 플랫폼에서 일반적으로 사용됨

순서화된 용어는 충분히 구체적이지 않음

양방향으로 반복하고, 양쪽 끝에서 작업이 가능해야 함

Queue와 같은 순서화된 컬렉션은 확실히 비대칭이기도 함

이 제안의 이전 버전에서 사용된 리버서블(reversible)이라는 용어는 양끝이 있다는 개념을 바로 재현하지는 않음

아마도 더 큰 문제는 변형된 Map의 이 ReversibleMap으로 명명될 것이라는 것인데, 이는 키별 및 값별로 검색을 지원한다고 오해할 수 있음

Add, put, 그리고 UnsupportedOperationException

위에서 설명한 바와 같이 SortedSet::addFirst, SortedMap::putLast 같은 명시적 위치 지정 API는 UnsupportedOperationException을 던짐

왜냐하면 요소의 순서는 상대적 비교에 의해 결정되기 때문

일부 컬렉션이 SequencedCollection 작업을 모두 구현하지 못하게 하는 불균형성은 불쾌해보일 수 있음

그럼에도 불구하고 SortedSet, SortedMap을 SequencedCollection에 포함시켜 다른 방법보다 더 광범위하게 사용할 수 있기 때문에 가치가 있음

이런 불균형은 또한 컬렉션 프레임워크의 이전 디자인(설계) 결정과 동일함

예를 들어 Map::keySet 메소드는 리턴된 구현이 addition(추가)를 지원하지 않아도 Set을 리턴함

또는 구조적인 라인을 따라 인터페이스를 재배열하여 addtion(추가) 연산을 별도로 유지 가능

그러면 매우 얇은 의미(예: AddableCollection)를 가진 새로운 인터페이스 타입이 생겨 실제로는 유용하지 않고 타입 계층 구조를 어지럽힘

역사

이 제안은 2021년 Reversible Collections 제안의 점진적인 발전

이 제안의 주요 변경 사항은 이름 바꾸기(renaming), Sequenced Map 인터페이스 추가, 불변 wrapper 메소드 추가

Reversible Collection 제안은 차례로 Tagir Valeev의 2020 OrderedMap/OrderedSet 제안을 기반으로 함

세부적으로 큰 차이가 있지만, 그 제안의 몇 가지 기본 개념은 여전히 존재함

지난 몇 년 동안 우리는 List 또는 Set을 결합하는 맥락에서 많은 요청과 제안을 받았음

반복되는 주제는 유일한(unique) 요소를 포함하는 List이거나, 순서를 유지하는 Set 또는 Map

이러한 요청에는 4152834, 4245809, 4264420, 4268146, 6447049, 8037382가 포함됨

https://bugs.openjdk.org/browse/JDK-4152834

https://bugs.openjdk.org/browse/JDK-4245809

https://bugs.openjdk.org/browse/JDK-4264420

https://bugs.openjdk.org/browse/JDK-4268146

https://bugs.openjdk.org/browse/JDK-6447049

https://bugs.openjdk.org/browse/JDK-8037382

이러한 요청 중 일부는 Java 1.4에서 LinkedHashSet, LinkedHashMap을 도입하면서 부분적으로 해결됨

이러한 클래스는 일부 사용 케이스를 만족하지만, 이러한 클래스의 도입은 위에서 설명한 대로 컬렉션 프레임워크에서 제공하는 추상화(abstractions)와 연산(operations)에 결함을 남김

위험과 가정

메소드 명명

높은 상속 계층에서 도입된 새로운 메소드는 기존 클래스의 메소드와 충돌할 수 있음

예를 들어 getFirst(), reversed()와 같은 메소드를 정의하지만, SequencedCollection에 정의된 getFirst(), reversed()와 다른 리턴 타입을 가진 List 인터페이스의 사용자 지정 구현이 있다면, Java 21로 업그레이드할 때 소스 비호환성을 생성함

공변 오버라이드

특히 List와 Deque에서 reverse() 메소드의 공변 오버라이드를 제공하며, 하나는 List를 리턴하고, 하나는 Deque를 반환함

두 인터페이스를 모두 구현하는 사용자 지정 컬렉션은 컴파일러가 다른 인터페이스보다 하나를 선택할 수 없기 때문에 Java 21로 업그레이드할 때 컴파일 타임 에러 발생

예시

JDK에는 LinkedList와 내부 클래스 sun.awt.util.IdentityLinkedList의 두 가지 컬렉션 예시가 있음

LinkedList 클래스는 LinkedList 자체에 새로운 reversed() 공변 오버라이드를 도입하여 해결됨

내부의 IdentityLinkedList 클래스는 더 이상 필요하지 않으므로 제거됨

이전 버전의 제안은 SequencedMap 인터페이스의 keySet(), values(), entrySet() 메소드에 대한 공변 오버라이드를 도입했으나, 분석 후 이 접근 방식이 너무 큰 비호환성 위험을 도입했다고 판단하여 기본적으로 기존 서브클래스를 무효화함

기존의 메소드를 공변 오버라이드로 조정하는 대신 SequencedKeySet(), SequencedValues(), SequencedEntrySet()을 SequencedMap에 새로운 메소드를 도입하는 것을 선택함

돌이켜보면 Java 6에서도 기존의 keySet() 메소드를 공변 오버라이드로 수정하는 대신 navigableKeySet() 메소드를 도입하여 유사한 접근 방식을 취했을 수 있음

호환성 위험에 대한 전체 분석은 CSR, JDK-8266572(Sequenced Collections)에 첨부된 보고서를 참조할 것

https://bugs.openjdk.org/browse/JDK-8266572

결론

Sequenced Collections는 Java Collections의 중요한 도약을 의미함

Java는 정의된 요소 순서로 컬렉션을 처리하는 통합된 방법에 대한 오랜 결점을 해결함으로써 프로그래머들이 보다 효율적으로 작업할 수 있도록 지원함

새로운 인터페이스는 보다 명확한 구조와 일관된 동작을 정의하여 보다 강력하고 가독성 좋은 코드를 제공함

NavigableSet

자바 6에서 추가됨
SortedSet을 확장한 인터페이스

객체 생성

자바에서 제공하는 NavigableSet 인터페이스의 대표적인 구현 클래스는 TreeSet
TreeSet 객체를 생성한 후에 NavigableSet 타입 변수에 할당할 것

NavigableSet<String> animalSet = new TreeSet<>(Arrays.asList("Lion", "Dog", "Cat", "Tiger"));
// [Cat, Dog, Lion, Tiger]

역순으로 접근: descendingIterator, descendingSet

SortedSet은 정렬된 원소를 역순으로 반복하는 것이 곤란했음
- SortedSet은 List의 하위 타입이 아니므로 인덱스를 이용한 접근이 불가능
- 역순으로 정렬하는 새로운 SortedSet을 생성

Set<String> reverseAnimalSet = new TreeSet<>(Collections.reverseOrder());
reverseAnimalSet.addAll(animalSet);

for(String animal : reverseAnimalSet)
		System.out.println(animal);

NavigableSet에서는 SortedSet의 단점을 보완하여 descendingIterator, descendingSet 메소드 제공

descendingIterator

역순 Iterator 리턴

for(Iterator<String> iterator = animalSet.descendingIterator(); iterator.hasNext();)
		System.out.println(iterator.next());

descendingSet

역순으로 정렬된 새로운 Set 리턴

NavigableSet<String> reverseAnimalSet = animalSet.descendingSet();
System.out.println(reverseAnimalSet);

공변 오버라이딩 covariant override

자바 5에 구현된 공변 메소드 오버라이드 접근 방식은 오버라이드된 메소드의 실제 리턴 타입의 하위 타입을 리턴할 수 있도록 하여 클라이언트 측 타입 캐스팅을 제거하는 데 도움이 됨
하위 클래스에서 메소드를 재정의할 때 리턴 타입이 달라질 수 있음을 의미함
- 자바 5 이전에는 하위 클래스에서 리턴 타입이 변경되는 경우 함수를 재정의하는 것이 허용되지 않았음
- 하지만 이제 리턴 타입은 하위 타입 클래스만 가능함