알면 유용한 Java 8, 9 에서 추가, 변경된 Collection 관련 내용

openjdk11 을 사용하였습니다.

1. removeIf

Java 8 에서 Collection 인터페이스에 removeIf 메소드가 추가되었습니다.

removeIf 를 사용하면 Collection 에서 특정 조건의 엘리먼트 삭제 시 코드를 간결하게 작성할 수 있습니다.

 

ArrayList 는 Collection 인터페이스의 default removeIf 를 사용하지 않고 따로 구현하여

 O(n) 의 시간복잡도로 설계된 로직을 사용하기 때문에 ArrayList 의 removeIf 를 사용한다면 성능 이점도 볼 수 있습니다.

 

removeIf 를 사용하지 않으면 다음과 같이 작성할 수 있습니다.

List<String> list = new ArrayList<>(List.of("ABC", "BC", "DC", "AA"));

// iterator 사용
for (Iterator<String> it = list.iterator() ; it.hasNext() ; ) {
    String str = it.next();
    if (str.startsWith("A")) {
        it.remove();
    }
}

// index 값을 사용
int size = list.size();
for (int i=0 ; i < size ; i++) {
    if (list.get(i).startsWith("A")) {
        list.remove(i);
        size--;
        i--;
    }
}

ArrayList 의 remove 메소드는 내부에서 array 의 shift 가 발생하기 때문에 O(n) 의 시간복잡도를 갖습니다.

iterator 도 내부에서 remove 메소드를 사용합니다.

ArrayList 클래스의 내부 클래스 Itr(iterator) 의 remove 메소드

그래서 처음 작성한 코드는 O(n²) 시간복잡도를 가집니다.

 

removeIf 를 사용한다면 다음과 같이 간결하게 코드를 작성할 수 있습니다.

list.removeIf(str -> str.startsWith("A"));

Collection 인터페이스의 default 구현으로 iterator 를 사용하게 되어있습니다.

Collection 인터페이스의 removeIf default 메소드

ArrayList 클래스는 removeIf 를 따로 구현하여 더 효율적인 로직을 사용합니다.

removeIf 는 대략적으로 다음과 같이 진행됩니다.

1. 첫 번째 반복에서 인자로 넘어온 Predicate 를 사용하여 삭제될 대상을 찾습니다.
2. 두 번째 반복에서 삭제될 대상들을 제외하면서 shift 연산을 진행합니다.

그래서 O(n) 의 성능을 가질 수 있습니다.

 

이 외에도 stream 을 사용하여 O(n) 시간복잡도로 특정 엘리먼트를 삭제한  List 를 구할 수 있습니다.

다만 차이점은 removeIf 는 메소드를 호출하는 collection 을 변경하는 것이고  stream 은 새로운 List 를 반환한다는 점 입니다.

// list 는 ArrayList
List<String> result =
        list.stream()
                .filter(not(str -> (str.startsWith("A"))))
                .collect(Collectors.toList());

 

2. List.sort

Java 8 에서 List 인터페이스에 sort 메소드가 추가되었습니다.

이전에 사용하던 Collections.sort 메소드 내부에서 List.sort 메소드를 호출하기 때문에

이전 코드를 변경하지 않아도 그대로 적용되었습니다.

Collections 클래스의 sort 메소드1

Collections 클래스의 sort 메소드2

List.sort 메소드의 default 메소드는 다음과 같이 동작합니다.

1. 새로운 array 를 만들어서 기존의 데이터를 복사합니다.
2. 1번에서 만든 새로운 array 에서 정렬합니다.
3. 새로운 array의 정렬된 데이터를 현재 collection 으로 다시 복사합니다.

default 메소드의 코드는 다음과  같습니다.

List.sort 의 default 메소드

그런데 ArrayList 는 sort 메소드를 구현해서 다르게 동작합니다.

새로운 array 를 만들지 않고 현재 데이터가 저장된 array 그 자리에서 정렬을 진행합니다.

이처럼 ArrayList 의 sort 메소드는 copy 동작을 하지 않아서 더 효율적입니다.

ArrayList.sort

 

3. Multimap 을 지원하는 Map interface 의 메소드

각 키 마다 여러 값을 가질 수 있는 데이터 구조 이름을 Multimap 이라고 부릅니다.

Java 8 이전에는 다른 라이브러리 없이 구현하기가 불편했는데,

Java 8 에서는 이를 지원하는 메소드들이 Map interface 에 추가되었습니다. 

// put(str, i)
multimap.computeIfAbsent(keyStr, x -> new HashSet<>()).add(value);

// remove(str, i)
multimap.computeIfPresent(keyStr, (k1, s) -> s.remove(10) && s.isEmpty() ? null : s);

// contains(str, i)
multimap.getOrDefault(keyStr, Collections.emptySet()).contains(value);

// size()
multimap.values().stream().mapToInt(Set::size).sum();

// values()
multimap.values().stream().flatMap(Set::stream);

 

4. comparator composition

기존에 익명 클래스로 구현하던 Comparator 를 comparator 메소드와 composition 을 활용하여 

간결하고 명확하게 구현할 수 있게 되었습니다.

예시를 통해 변화를 느껴보겠습니다.

 

문제: Student instance 들을 lastName 순으로 정렬하고 만약 같으면 firstName 으로 정렬하는데,

firstName 이 null 이면 먼저 오게 정렬하세요

 

Java 8 이전에 사용하던 코드

Collections.sort(students, new Comparator<Student>() {
    @Override
    public int compare(Student s1, Student s2) {
        int r = s1.getLastName().compareTo(s2.getLastName());
        if (r != 0) {
            return r;
        }
        String f1 = s1.getFirstName();
        String f2 = s2.getFirstName();
        if (f1 == null) {
            return f2 == null ? 0 : -1;
        } else {
            return f2 == null ? 1 : f1.compareTo(f2);
        }
    }
});

Comparator 메소드 , composition 을 이용한 코드

students.sort(comparing(Student::getLastName)
              .thenComparing(Student::getFirstName,
                      nullsFirst(naturalOrder())));

 

5. Map, Set 의 랜덤화된 순회 순서

Java 9 에서 추가된 Map, Set 을 구현한 Collection 들은 순회의 순서가 매 JVM 실행마다 달라집니다.

Set.of, List.of, Map.of 는 Java 9 에서 나온 static 메소드 입니다.
이 메소드들은 기존에 있는 HashMap, HashSet 과 같은 Collection 을 생성하는게 아닌
ImmutableCollections.java 파일에 새롭게 정의된 Collection 들을 생성합니다.

그런데 Java 9 이전부터 HashMap 이나 HashSet 의 순회 순서는 달라질 수 있다고 알려져 있었고 문서도 명시되어 있었습니다.

HashMap.java 파일에는 다음과 같이 문서화 되어있습니다.

This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

그럼 Java 9 에서 추가된 Collection 들과 그 이전 Collection 들은 무슨 차이가 있는지

테스트를 통하여 알아보겠습니다.

 

먼저 기존에 사용하던 Collection 을 사용해서 결과를 확인해보겠습니다.

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(3);
set.forEach(System.out::println);

1
2
3

코드를 실행한 결과는 입력 순서와 동일했고 여러 번 실행해도 결과는 동일했습니다.

다른 데이터로 테스트를 해보겠습니다.

Set<Integer> set = new HashSet<>();
set.add(1000);
set.add(2000);
set.add(3000);
set.forEach(System.out::println);

2000
1000
3000

이번에는 데이터를 입력한 순서대로 결과가 나오지 않았습니다.

하지만 이 코드를 여러 번 수행하면 같은 결과가 나옵니다.

 

위 2개의 결과로 다음을 알 수 있습니다.

1. 입력에 따라서 순회 순서는 달라집니다.
2. 동일한 코드를 여러 번 실행 시 결과는 같습니다.

 

그러면 Java 9 에서 추가된 Collection 을 사용해서 결과를 확인해보겠습니다.

Set<Integer> set = Set.of(1, 2, 3);
set.forEach(System.out::println);

 

위 코드 실행 결과는 매번 달라집니다.

 

코드를 확인해보면 ImmutalbeCollections 클래스 안에는 SALT 값이 있습니다. 

ImmutableCollections 클래스 변수

그래서 다음 index 를 가져올 때 이 SALT 값을 사용합니다. 

그런데 static 변수이기 때문에 한 번 실행할 때 할당되고 변하지 않습니다.

그래서 jvm 을 실행할 때마다 순회 순서는 변하지만 한 번 실행된 이후부터는 순회 순서가 동일합니다. 

java library 개발자가 말하기를,
다른 프로그래머들이 개발 과정에서 map , set 의 순회 순서에 의존적인 로직을
알아낼 수 있을 정도로 구현하기 위하여 SALT 값을 static 으로 구현했다고 합니다.

그리고 기존 Collection(HashMap, HashSet ..) 들 또한 이처럼 수정한다면 
순서에 의존하는 다른 Java 어플리케이션들이 깨질 수 있기 때문에
기존 Collection 에는 적용하지 않았다고 합니다.

기존의 Map, Set 을 구현한 Collection들은 성능이나 보안을 위해 내부 구현이 변경되면
순회의 순서가 변경될 수 있다고 합니다.

 

결론

1. removeIf 를 사용하여 간결하게 구현할 수 있습니다. ArrayList 의 removeIf 를 사용하면 O(n) 의 성능을 가질 수 있습니다.

2. ArrayList.sort 메소드를 사용하면 추가적인 copy 없이 정렬을 하도록 최적화되어있습니다.

3. Multimap 을 지원하는 method 들이 추가되었습니다.

4. Comparator 메소드와 composition 을 사용하면 간결하고 명확한 Comparator 를 구현할 수 있습니다.

5. Java 9 부터 추가된 Map, Set Collection 들은 매 jvm 실행마다 순회 순서가 달라집니다.

 

 

출처

Collections Refueled by Stuart Marks