컬렉션 인터페이스나 클래스 내의 각 메서드에 붙은 주석들은 자바독에서 설명하는 내용들을 추려서 그대로 옮겨왔습니다. 그리고 이 게시글에서는 내용이 너무 길어지기도 하고 자바의 범위를 벗어나므로, 여기서 등장하는 자료구조나 알고리즘에 대해서는 따로 설명하지는 않습니다. 자료구조에 대한 기본적인 배경지식이 없다면 이해가 힘들 수 있습니다. 예제를 실행해보고 결과를 이해하기 힘들다면 인터넷에서 자료구조에 대한 게시글을 간단하게 보고 오시는 것을 추천해 드립니다.

컬렉션은 한번에 이해하려고 하기 보다는 리스트(List), 셋(Set), 큐(Queue), 맵(Map)의 특징을 간략하게 파악하고 예제를 살펴보면서 대략적인 감을 잡는 것으로 시작하는게 좋습니다. 인터페이스에서 소개하는 메서드를 다 보는게 아니라 add(), get(), set(), remove() 같은 필수적인 단일 연산(검색, 추가, 삭제, 변경)을 먼저 보고, 나머지 기능들은 눈으로만 훑어보면서 '아~ 이런 기능들이 있구나!'라고만 생각하시고 나중에 필요할 때 다시 살펴봐도 괜찮습니다. 구현도 대표적인 자료구조(ArrayList, HashSet, HashMap)를 먼저 살펴보고 할만하면 나머지 자료구조를 살펴보는 식으로 진행하면 부담을 좀 덜 수 있습니다. 이제는 잘 사용되지 않는 Stack, Vector는 설명만 잠시 보고 넘어가셔도 괜찮습니다.

Collection

자바에서 컬렉션(collection)은 여러 개의 요소를 묶어서 하나로 만든 그룹 객체(혹은 컨테이너)를 말합니다. 자바에서는 아래 다이어그램에서 볼 수 있듯이 컬렉션을 다루기 편하도록 컬렉션 프레임워크(collections framework)라는 통합된 하나의 구조로 만들었는데, 이로 인해서 API의 일관성을 통해 개발자들이 학습하기 쉽고, 설계 시 확장이 용이하며, 기존에 만들어진 알고리즘을 재사용 할 수 있게 되었습니다.

위의 다이어그램을 보면 리스트, 큐, 셋, 맵 같이 우리가 흔하게 들어본 자료구조의 이름들이 보입니다. 얼핏 보기에는 Collection 인터페이스를 구현하는 게 컬렉션인가 싶지만 분리되어 있는 TreeMap, HashMap 등도 컬렉션에 속합니다. 이렇게 분리된 이유는 리스트, 큐, 셋은 요소(element)를 가지고 있는데 반해서 맵은 키와 값의 쌍(pair)으로 이루어져 있기 때문입니다. 즉, Map이 Collection을 상속하거나 Collection이 Map을 상속하면 인터페이스가 부자연스러워지므로 설계상의 이유로 분리한 것입니다.

Collection 인터페이스

public interface Collection<E> extends Iterable<E> {
    // === 질의 연산(query opertions) ===
    // 이 컬렉션의 요소 수를 반환합니다. 컬렉션에 요소 수가 Integer.MAX_VALUE개를 넘어가면 Integer.MAX_VALUE를 반환합니다.
    int size();

    // 컬렉션이 비어 있으면 참을 반환합니다.
    boolean isEmpty();

    // 컬렉션에 어떤 요소가 들어가 있으면 참을 반환합니다. 좀 더 자세히 말하면, 컬렉션에서 Objects.equals(o, e)가 참인 요소가 적어도 하나 존재하면 참을 반환합니다.
    boolean contains(Object o);

    // 이 컬렉션의 모든 요소가 들어간 배열을 반환합니다. 순서가 있는 컬렉션의 경우 이 메서드는 같은 순서로 요소를 반환해야 합니다.
    // 반환된 배열은 컬렉션을 참조하지 않으며 새로 할당된 배열이므로 배열의 요소를 변경해도 원래 컬렉션의 요소는 변경되지 않습니다.
    Object[] toArray();

    // === 수정 연산(modification operations) ===
    // 호출 후 컬렉션에 성공적으로 추가한 경우 true를 반환합니다. 만약에 컬렉션이 중복을 허용하지 않고 추가하려는 요소가 이미 컬렉션에 있다면 false를 반환합니다.
    boolean add(E e);

    // 제거하려는 요소가 컬렉션에 있는 경우 이 컬렉션에서 하나를 제거합니다. 좀 더 자세히 말하면, Objects.equals(o, e)가 참인 요소를 하나만 제거합니다. 호출 후 컬렉션에서 성공적으로 요소를 제거한 경우 true를 반환합니다.
    boolean remove(Object o);

    // === 대량 연산(bulk operations) ===
    // 이 컬렉션이 컬렉션 c의 모든 요소를 포함하고 있으면 참을 반환합니다.
    boolean containsAll(Collection<?> c);

    // 이 컬렉션에 컬렉션 c의 모든 요소를 추가합니다.
    boolean addAll(Collection<? extends E> c);

    // 이 컬렉션에서 컬렉션 c 내의 요소와 같은 요소들을 모두 제거합니다. 호출이 끝나면 이 컬렉션에는 컬렉션 c와 서로 일치하는 요소가 하나도 없게 됩니다.
    boolean removeAll(Collection<?> c);

    // 주어진 조건에 맞는 요소들을 제거합니다.
    default boolean removeIf(Predicate<? super E> filter) { ... }

    // 컬렉션 c에 있는 요소들만 유지(retain)합니다. 즉, 이 컬렉션에서 컬렉션 c에 없는 요소들을 모두 제거합니다.
    boolean retainAll(Collection<?> c);

    // 컬렉션을 비웁니다. 즉, 컬렉션의 모든 요소를 제거합니다.
    void clear();

    // === 비교와 해싱(comparison and hashing) ===
    // 해당 객체와 이 컬렉션을 비교하여 동등성(equality)을 확인합니다.
    // 주의할 점은 List와 Set처럼 서로 다른 자료구조를 비교할 때는 같은 요소가 들어가 있는 것 같아도 false를 반환하게 됩니다. 예를 들어서 List.equals(o) 메서드를 살펴보면 먼저 객체 o가 리스트여야 한다는 조건이 있으므로 List 인터페이스를 구현하지 않은 객체가 넘어온다면 false를 반환하게 됩니다.
    boolean equals(Object o);

    // 이 리스트의 해시 코드 값을 반환합니다.
    int hashCode();

    // 이 컬렉션을 소스로 하는 순차 스트림을 반환합니다. 마찬가지로 병렬 스트림을 반환하는 parallelStream()도 있습니다.
    default Stream<E> stream() { ... }

    ...
}

Iterable

Iterable

iterable의 사전적 의미는 '반복할 수 있는'을 의미합니다. 이 인터페이스를 구현한 클래스는 아래와 같이 개선된 for문(enhanced for loop, 또는 for-each문)을 사용해 반복할 수 있습니다.

// Collection 인터페이스는 Iterable 인터페이스를 상속받음
List<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);

for (Integer num : nums) {
	System.out.println("num = " + num);
}

이를 아래와 같이 작성할 수도 있습니다. 이터레이터를 이용하면 세부적으로 어떻게 구현되어 있는지 몰라도 편리하게 순회할 수 있습니다.

...
// Iterator를 사용해서 순회하는 방법
Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
	System.out.println("next: " + it.next());
}

// forEach()를 사용해서 순회하는 방법 (이 방법도 내부적으론 iterator를 사용한다)
nums.forEach(n -> System.out.println("next: " + n));

이 인터페이스의 내부를 살펴보면 다음과 같습니다. 개선된 for문을 사용할 때 iterator() 메서드를 호출하여 이터레이터를 얻어오고 다음 요소가 있는지 확인한 후(hasNext()), 있으면 다음 요소를 가져오는(next()) 식입니다.

public interface Iterable<T> {
    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }
    ...
}

Iterator

그러면 Iterator는 무엇일까요? 내부를 살펴보면 위에서 잠시 살펴봤던 hasNext()와 next()가 보입니다. 개선된 for문에서는 Iterable.iterator()로 Iterator 인터페이스를 구현한 클래스의 객체를 가져와서 hasNext()와 next()를 번갈아 가며 호출합니다.

public interface Iterator<E> {
	// 반복할 요소가 더 있으면 true를 반환한다. 즉, next()를 호출해서 더 꺼내올 요소가 있으면 true를 반환한다.
    boolean hasNext();

	// 다음 요소를 반환한다.
    E next();
    ...
}

예제 살펴보기

이해를 돕기 위해서 예제를 최대한 단순하게 만들었습니다. 다음 예제를 실행시키고 결과를 살펴봅시다.

class SimpleList<T> implements Iterable<T> {
    private T[] data;

    public SimpleList(T[] data) {
        this.data = data;
    }

    @Override
    public Iterator<T> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<T> {
        int cursor;

        @Override
        public boolean hasNext() {
	        System.out.println("hasNext()");
            return cursor != data.length;
        }

        @Override
        public T next() {
	        System.out.println("next()");
            return data[cursor++];
        }
    }
}

public class IteratorExample {
    public static void main(String[] args) {
        SimpleList<String> list = new SimpleList<>(new String[]{"a", "b", "c"});

        for (String s : list) {
            System.out.println(s);
        }
    }
}

List

인터페이스: List

순서가 있는 컬렉션이며 시퀀스(sequence)라고도 부릅니다. 인덱스를 사용하여 요소에 접근하거나 검색할 수 있으며, 보통 Set과는 다르게 컬렉션 내의 중복을 허용합니다.

public interface List<E> extends Collection<E> {
    // === 수정 연산(modification operations) ===
    // 컬렉션 c의 모든 요소를 리스트의 지정 위치에 추가합니다. 기존의 위치에 있던 요소와 그 뒤에 있던 요소는 오른쪽(뒤쪽)으로 밀려납니다.
    boolean addAll(int index, Collection<? extends E> c);

    // === 대량 연산(bulk operations) ===
    // 이 리스트의 각 요소에 해당 연산자를 적용합니다.
    default void replaceAll(UnaryOperator<E> operator) { ... }

    // 주어진 Comparator를 통해 이 리스트를 정렬합니다.
    default void sort(Comparator<? super E> c) { ... }

    // === 위치 접근 연산(positional access operations) ===
    // 이 리스트에서 지정 위치에 있는 요소를 반환합니다.
    E get(int index);

    // 이 리스트에서 지정 위치에 있는 요소를 주어진 요소로 변경합니다.
    E set(int index, E element);

    // 주어진 요소를 이 리스트의 지정 위치에 삽입합니다. 기존의 위치에 있던 요소와 그 뒤에 있던 요소는 오른쪽(뒤쪽)으로 밀려납니다.
    void add(int index, E element);

    // 이 리스트에서 지정 위치에 있는 요소를 제거합니다. 삭제된 요소의 뒤에 있던 요소들은 왼쪽(앞쪽)으로 이동합니다. 삭제된 요소가 반환됩니다.
    E remove(int index);

    // === 검색 연산(search operations) ===
    // 이 리스트의 앞부터 시작하여 주어진 요소를 찾은 뒤 그 요소의 첫 번째 인덱스를 반환합니다. 더 자세히 말하면, Objects.equals(o, get(i))가 참인 가장 낮은 인덱스 i를 반환합니다. 만약 리스트에 해당 요소가 없으면 -1을 반환합니다. 
    int indexOf(Object o);

    // indexOf()와는 반대 방향(즉, 뒤에서 앞으로)으로 탐색을 시작합니다. 찾은 요소의 첫 번째 인덱스를 반환합니다. 더 자세히 말하면, Objects.equals(o, get(i))가 참인 가장 높은 인덱스 i를 반환합니다. 만약 리스트에 해당 요소가 없으면 -1을 반환합니다.
    int lastIndexOf(Object o);

    // === 뷰(View) ===
    // 이 리스트에서 from(포함)부터 to(제외)까지인 부분 리스트의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 요소를 변경하면 원본 리스트에도 영향을 미칩니다.
    List<E> subList(int fromIndex, int toIndex);

    // 컬렉션 coll의 요소를 모두 포함하는 변경 불가능 리스트(ImmutableCollections)를 반환합니다. 컬렉션 coll에는 null인 요소가 들어가면 안되며, 들어갔을 때는 NullPointerException 예외가 발생합니다. 원본 컬렉션이 수정되어도 반환된 리스트는 변경되지 않습니다.
    static <E> List<E> copyOf(Collection<? extends E> coll) { ... }

    ...
}

리스트 초기화 하기

자바 9부터는 정적 팩토리 메서드인 List.of()를 사용하여 리스트를 쉽게 만들 수 있습니다. 하지만 이 리스트는 변경할 수 없는 컬렉션(ImmutableCollections)이므로 새로운 요소를 추가하거나 제거, 변경할 수 없습니다. 변경하려고 시도하면 UnsupportedOperationException 예외가 발생하니 주의합시다. 그리고 인수(argument)로 null을 넘기는 것은 허용되지 않습니다.

// 자바 8 이전 (요소를 추가, 제거할 수는 없지만 요소는 set()으로 변경 가능)
List<Integer> nums = Arrays.asList(1, 2, 3, 4);
// 자바 9 이후 (변경 불가)
List<Integer> nums = List.of(1, 2, 3, 4);

특정 리스트 구현(예를 들어 ArrayList)이 필요한 경우에는 아래와 같이 생성자로 넘길 수도 있습니다. 이렇게 하면 추가는 가능하지만 리스트가 2개가 필요하게 됩니다.

// 자바 8 이전
List<Integer> nums = new ArrayList<>(Arrays.asList(1, 2, 3, 4));
// 자바 9 이후
List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4));

한 개의 리스트를 사용하려면 개발자가 다음과 같이 추가할 수는 있지만, 요소가 조금이라도 많아지면 상당히 번거롭습니다.

List<Integer> nums = new ArrayList<>();
nums.add(1);
nums.add(2);
nums.add(3);
nums.add(4);

이중 중괄호 초기화(double brace initialization)

혹시나 이런 코드를 마주칠 기회가 있을지도 모르겠다 싶어서 소개하며, 이 부분을 건너뛰어도 아무런 지장이 없습니다. 비공식적으로 개발자 사이에서 이중 중괄호 초기화(double brace initialization)라고 부르는 방법을 사용해서 아래와 같이 줄일 수도 있지만 문제를 떠안기 쉬우므로 사용은 권장하지는 않습니다. 사실 이는 ArrayList를 상속하는 익명 클래스가 만들어지고(바깥쪽 중괄호), 인스턴스 초기화 블럭(instance initialization block, 안쪽 중괄호)을 사용해서 초기화 하는 방법입니다.

// 뒤에서 살펴볼 맵(Map)이나 셋(Set)도 마찬가지 방법으로 초기화 가능
List<Integer> nums = new ArrayList<>() {{
    add(1);
    add(2);
    add(3);
    add(4);
}};

이 코드의 문제점은 위에서도 언급했지만 이중 중괄호를 사용할 때마다 익명 클래스를 생성한다는 점입니다. 따라서 추가 클래스 파일(.class)이 만들어지며 런타임에 JVM이 추가로 클래스를 로드해야 하므로 부하가 걸립니다. 그리고 인스턴스 초기화 블럭은 거의 사용되지 않는 기능이라서 유지보수 시에 대부분의 개발자가 이런 코드를 보고 혼란스러울 수 있습니다. 마지막으로 생성된 익명 클래스는 자신을 둘러싸는 객체를 가리키는 숨겨진 참조를 가지고 있어서, 아래 예시에서 SomeHeavyObject 객체를 따로 참조하지 않는 것 같아도 가비지 컬렉션이 일어나지 않으므로 메모리 누수가 일어날 수 있습니다.

class SomeHeavyObject {
    // ...
    private int someField = 10;

    public List<Integer> someMethod() {
        return new ArrayList<>() {{
            add(someValue);
            ...
            // add(SomeHeavyObject.this.someField);
        }};
    }
}

public class DoubleBraceInitializationExample {

    public static void main(String[] args) throws Exception {
        List<Integer> list = new SomeHeavyObject().someMethod();

        // 내부 클래스의 this$0은 외부 클래스의 객체를 참조할 때 사용되는 숨겨진 필드이다. 리플렉션을 사용하여 이를 가져왔다.
        Field field = list.getClass().getDeclaredField("this$0");
        // 익명 클래스의 인스턴스에서 this$0 필드의 값이 어떤 클래스인지 가져온다.
        // class com.company.SomeHeavyObject
        System.out.println(field.get(list).getClass());
    }
}

구현: ArrayList

ArrayList는 크기가 부족하면 자동으로 증가하는 동적 배열이라고 생각하면 됩니다. List 인터페이스를 구현하며 내부적으로 배열을 사용합니다.

이 클래스는 동기화되지 않는다는 점을 제외하면 Vector와 거의 똑같습니다. 따라서 동기화가 필요한 경우에는 외부에서 따로 동기화를 해주거나 CopyOnWriteArrayList 혹은 Collections.synchronizedList(List<T>) 정적 메서드로 동기화된 List를 얻는 방법이 있습니다(하지만 여전히 주의가 필요하며, 궁금하시다면 자바독을 참고해주세요).

public class ArrayListExample {
    // 참고로 size(), isEmpty(), get(), set()의 시간 복잡도는 O(1)이다.
    // n개의 요소를 추가할 때는 O(n)이고, 다른 연산들도 얼추 말하자면 O(n)이다.
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();

        Random r = new Random();
        // 리스트의 끝에 요소를 추가한다.
        for (int i = 0; i < 10; i++)
            numbers.add(r.nextInt(10));

        System.out.println("numbers = " + numbers);
        // 현재 ArrayList의 크기를 반환한다.
        System.out.println("numbers.size() = " + numbers.size());

        System.out.println("\n요소를 가져오거나 변경하기:");
        // 인덱스 5(6번째)에 있는 요소를 가져온다.
        System.out.println("numbers.get(5) = " + numbers.get(5));
        // 인덱스 5(6번째)에 있는 요소를 변경한다.
        numbers.set(5, 10);
        System.out.println("numbers.get(5) = " + numbers.get(5));

        System.out.println("\n4번째 요소 제거하기:");
        // 현재 ArrayList에서 인덱스 3(4번째)에 있는 요소를 삭제한다.
        numbers.remove(3);
        // numbers = [0, 1, 2, 4, 5, 6, 7, 8, 9]
        System.out.println("numbers = " + numbers);

        System.out.println("\n오름차순 정렬:");
        numbers.sort(Comparator.naturalOrder());
        System.out.println("numbers = " + numbers);

        System.out.println("\n내림차순 정렬:");
        numbers.sort(Comparator.reverseOrder());
        System.out.println("numbers = " + numbers);

        System.out.println("\n컬렉션 비우기:");
        numbers.clear();
        System.out.println("numbers = " + numbers);

        System.out.println("\n컬렉션이 비어있는지 확인하기:");
        System.out.println("numbers.isEmpty() = " + numbers.isEmpty());
    }
}

구현: LinkedList

LinkedList는 더블 링크드 리스트(doubly linked list, 또는 이중 연결 리스트)를 구현한 것입니다. List 인터페이스와 Deque 인터페이스를 구현합니다.

ArrayList와 마찬가지로 동기화가 필요한 경우에는 외부에서 따로 동기화를 해줘야 합니다.

public class LinkedListExample {  
    // LinkedList는 List 인터페이스를 구현하므로 ArrayList 예제에서 봤던 메서드를 모두 사용할 수 있다.
    // 물론 Deque 인터페이스도 구현하므로 Deque에서 선언된 메서드도 사용할 수 있다.
    public static void main(String[] args) {
        LinkedList<String> books = new LinkedList<>();
        books.add("클린 코드");
        books.add("객체지향의 사실과 오해");
        books.add("오브젝트");
        books.add("실용주의 프로그래머");

        // 앞에 요소를 추가하기
        books.addFirst("이펙티브 자바");
        System.out.println("books = " + books);

        // 뒤에 요소를 추가하기
        books.addLast("자바 ORM 표준 JPA 프로그래밍");
        System.out.println("books = " + books);

        // 특정 요소들이 포함된지 확인하기
        if (books.containsAll(Arrays.asList("객체지향의 사실과 오해", "실용주의 프로그래머"))) {
            System.out.println("books에 \"객체지향의 사실과 오해\", \"실용주의 프로그래머\"가 들어가 있습니다.");
        }

        // 특정 요소들만 남기기
        books.retainAll(Arrays.asList("이펙티브 자바", "자바 ORM 표준 JPA 프로그래밍"));
        System.out.println("books = " + books);
    }
}

구현: Vector

ArrayList와 마찬가지로 크기가 부족하면 자동으로 증가하는 동적 배열이지만, ArrayList와는 반대로 동기화가 됩니다. 단일 스레드 환경에서는 이 때문에 성능에 큰 영향을 미치므로 ArrayList나 LinkedList를 사용할 것을 권장합니다. 자바독에서는 스레드 안전(thread-safe)한 구현이 필요가 없다면 Vector 대신에 ArrayList를 사용하는 것이 좋다고는 하지만, 실제로는 설계 결함이 있어서 자주 사용되지는 않습니다. 스레드 안전한 구현이 필요한 경우에는 CopyOnWriteArrayList를 대신 사용합니다.

이 클래스는 List 인터페이스를 구현합니다.

public class VectorExample {
    public static void main(String[] args) {
        List<String> clothes = new Vector<>();
        clothes.add("티셔츠"); // 0
        clothes.add("코트"); // 1
        clothes.add("스웨터"); // 2
        clothes.add("티셔츠"); // 3

        // clothes = [티셔츠, 코트, 스웨터, 티셔츠]
        System.out.println("clothes = " + clothes);

        System.out.println("\n존재 여부 확인하기:");
        // 리스트 내에 특정 요소가 포함되어 있는지 확인한다.
        if (clothes.contains("코트")) {
            System.out.println("리스트 내에 코트가 있습니다.");
        }

        System.out.println("\n검색 예시:");
        // 앞에서부터 찾으므로 결과는 0이 나온다.
        System.out.println("numbers.indexOf(\"티셔츠\") = " + clothes.indexOf("티셔츠"));
        // 뒤에서부터 찾으므로 결과는 3이 나온다.
        System.out.println("numbers.lastIndexOf(\"티셔츠\") = " + clothes.lastIndexOf("티셔츠"));

        System.out.println("\n삽입 예시:");
        clothes.add(1, "슬랙스"); // 인덱스 1(2번째 위치)에 슬랙스를 삽입한다.
        // clothes = [티셔츠, 슬랙스, 코트, 스웨터, 티셔츠]
        System.out.println("clothes = " + clothes);
    }
}

구현: Stack

Stack은 후입선출(LIFO) 스택을 구현한 것입니다. 하지만 Vector를 상속해서 구현한 것이므로 Vector에서 설명한 문제를 그대로 가지고 있으며, 마찬가지로 잘 사용되지 않습니다.

스택 자료구조가 필요하다면 Stack 대신에 Deque를 사용합시다.

public class Stack<E> extends Vector<E> {
    // 주어진 요소를 스택의 맨 위(top)에 푸시합니다.
    public E push(E item) { ... }

    // 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환합니다.
    public synchronized E pop() { ... }

    // 스택의 맨 위에 있는 요소를 가져오지만 제거하지는 않습니다.
    public synchronized E peek() { ... }

    // 스택이 비어 있는지를 확인합니다. 비어 있으면 true를 반환합니다.
    public boolean empty() { ... }

    // 주어진 요소 o가 스택의 맨 위(top)로부터 얼만큼 떨어져 있는지를 반환합니다. 비교 시에는 equals() 메서드를 사용하며, 스택의 맨 위 요소는 거리가 1입니다.
    public synchronized int search(Object o) { ... }
}

예시를 간단하게만 살펴봅시다.

public class StackExample {
    public static void main(String[] args) {
        Stack<String> names = new Stack<>();
        names.push("홍길동");
        names.push("김철수");
        names.push("홍길순");
        names.push("김영희"); // TOP

        // "김철수"는 스택의 맨 위(top)로부터 2만큼 떨어져 있지만, 맨 위를 1로 치므로 foundPos는 3이 된다.
        int foundPos = names.search("김철수");
        System.out.println("foundPos = " + foundPos);

        System.out.println("\n맨 위에 있는 요소 확인하기:");
        System.out.println("names.peek() = " + names.peek());
        System.out.println("names = " + names);

        System.out.println("\n맨 위에 있는 요소 제거하기:");
        System.out.println("names.pop() = " + names.pop());
        System.out.println("names = " + names);

        System.out.println("\npop()을 사용하여 스택 비우기:");
        while (!names.empty()) { // clear()를 사용해도 됨
            System.out.println("names.pop() = " + names.pop());
        }
        System.out.println("names = " + names);
    }
}

Set

인터페이스: Set

셋(set)은 중복을 허용하지 않는 컬렉션이며 이름 그대로 수학의 집합을 옮겨온 것입니다. 더 구체적으로 말해서, e1.equals(e2)가 참인 e1과 e2는 셋에 존재하지 않습니다.

public interface Set<E> extends Collection<E> {
    // Collection에서 설명한 메서드 설명과 거의 비슷합니니다.
    ...
}

셋 초기화 하기

자바 9부터는 List.of()와 마찬가지로 Set.of()라는 정적 팩토리 메서드를 제공합니다. 마찬가지로 이 셋은 변경할 수 없는 컬렉션(ImmutableCollections)이므로 새로운 요소를 추가하거나 제거할 수 없습니다. 변경하려고 시도하면 UnsupportedOperationException 예외가 발생하니 주의합시다. 그리고 인수(argument)로 null을 넘기는 것은 허용되지 않습니다. 추가로 넘긴 인수 중에 중복된 인수가 있으면 IllegalArgumentException 예외가 발생합니다.

// 자바 8 이전 (변경 가능)
Set<Integer> numbers = new HashSet<>(Arrays.asList(1, 2, 3, 4));
// 자바 9 이후 (변경 불가)
Set<Integer> numbers = Set.of(1, 2, 3, 4);

구현: HashSet

HashSet은 Set 인터페이스를 구현하며, 해시 테이블(내부적으로 HashMap 객체를 사용함)을 사용하여 셋을 구현한 것입니다.

HashSet은 순서가 일정하게 유지된다는 보장이 없으므로 주의해야 합니다. 그리고 HashSet은 동기화되지 않으므로 동기화가 필요한 경우에는 외부에서 따로 동기화를 해주거나 Collections.synchronizedSet(Set<T>) 정적 메서드로 동기화된 HashSet을 얻는 방법이 있습니다(하지만 여전히 주의가 필요하며, 궁금하시다면 자바독을 참고해주세요).

public class HashSetExample {
    public static void main(String[] args) {
        Set<Integer> numbers = new HashSet<>(Arrays.asList(1, 2, 2, 3, 4, 4, 5));

        // numbers = [1, 2, 3, 4, 5]
        System.out.println("numbers = " + numbers);

        // 출력 결과를 보면 순서가 있는 것 같지만 전혀 그렇지 않다. 순서에 의존하면 안된다.
        numbers.add(10);
        System.out.println("numbers = " + numbers);

        // 크기를 출력한다.
        System.out.println("numbers.size() = " + numbers.size());

        // 값이 4인 요소를 제거한다.
        numbers.remove(4);
        System.out.println("numbers = " + numbers);
    }
}

구현: LinkedHashSet

링크드 리스트(linked list)와 해시 테이블을 사용한 Set 인터페이스의 구현입니다.

HashSet과는 다르게 우리가 요소를 삽입한 순서가 그대로 유지됩니다. HashSet과 마찬가지로 동기화가 필요한 경우에는 외부에서 따로 동기화를 해줘야 합니다.

public class LinkedHashSetExample {
    public static void main(String[] args) {
        Set<Integer> a = new LinkedHashSet<>(Arrays.asList(2, 4, 6, 8, 10));
        Set<Integer> b = new LinkedHashSet<>(Arrays.asList(4, 8, 12, 16, 20));

        Set<Integer> intersection = new LinkedHashSet<>(a);
        intersection.retainAll(b);
        // intersection = [4, 8]
        System.out.println("intersection = " + intersection);

        Set<Integer> union = new LinkedHashSet<>(a);
        union.addAll(b);
        // union = [2, 4, 6, 8, 10, 12, 16, 20]
        System.out.println("union = " + union);

        Set<Integer> difference = new LinkedHashSet<>(a);
        difference.removeAll(b);
        // difference = [2, 6, 10]
        System.out.println("difference = " + difference);
    }
}

인터페이스: SortedSet

SortedSet은 Set 인터페이스를 상속하며 이 인터페이스를 구현하는 클래스는 한 요소를 다른 요소와 서로 비교할 수 있으므로 각 요소에 순서를 부여할 수 있습니다. 자연 순서(natural ordering)를 따라 정렬되거나 보통 생성자로 넘긴 Comparator를 통해서 정렬됩니다. 이 SortedSet 내의 모든 요소는 Comparable 인터페이스를 구현하거나 우리가 넘긴 Comparator로 처리할 수 있어야 합니다.

자연 순서(natural ordering)

말 그대로 사람이 보기에 자연스러운 순서를 말합니다. 예를 들어서 숫자의 자연 순서는 오름차순이 되고, 문자열은 알파벳순이 됩니다.

public interface SortedSet<E> extends Set<E> {
    // 요소 비교에 사용하는 Comparator를 반환합니다. 따로 없는 경우에는(자연 순서를 따르는 경우에는) null을 반환합니다.
    Comparator<? super E> comparator();

    // 이 셋에서 from(포함)부터 to(제외)까지인 부분 셋의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 요소를 변경하면 원본 셋에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedSet<E> subSet(E fromElement, E toElement);

    // 이 셋에서 toElement보다 작은 부분 셋의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 요소를 변경하면 원본 셋에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedSet<E> headSet(E toElement);

    // 이 셋에서 fromElement보다 크거나 같은 부분 셋의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 요소를 변경하면 원본 셋에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedSet<E> tailSet(E fromElement);

    // 현재 이 셋에 있는 첫(최저) 요소를 반환합니다.
    E first();

    // 현재 이 셋에 있는 마지막(최고) 요소를 반환합니다.
    E last();

    ...
}

인터페이스: NavigableSet

찾으려는 값과 가장 가까운 값을 반환하는 탐색 메서드를 추가한 SortedSet의 확장 인터페이스입니다.

public interface NavigableSet<E> extends SortedSet<E> {
    // 셋에서 요소 e보다 작은 요소 중 가장 큰 요소를 반환합니다. 없으면 null을 반환합니다.
    E lower(E e);

    // 셋에서 요소 e보다 작거나 같은 요소 중 가장 큰 요소를 반환합니다. 없으면 null을 반환합니다.
    E floor(E e);

    // 셋에서 요소 e보다 크거나 같은 요소 중 가장 작은 요소를 반환합니다. 없으면 null을 반환합니다.
    E ceiling(E e);

    // 셋에서 요소 e보다 큰 요소 중 가장 작은 요소를 반환합니다. 없으면 null을 반환합니다.
    E higher(E e);

    // 처음(최소) 요소를 제거하고 그 값을 반환합니다. 셋이 비어 있으면 null을 반환합니다. 
    E pollFirst();

    // 마지막(최고) 요소를 제거하고 그 값을 반환합니다. 셋이 비어 있으면 null을 반환합니다.
    E pollLast();

    // 이 셋의 역순(reverse order) 뷰를 반환합니다. 따라서 반환된 뷰를 통해 요소를 변경하면 원본 셋에도 영향을 미치며, 그 반대도 마찬가지입니다.
    NavigableSet<E> descendingSet();

    ...
}

구현: TreeSet

TreeSet은 TreeMap을 사용한 NavigableSet 인터페이스의 구현입니다.

LinkedHashSet, HashSet과 마찬가지로 동기화가 필요한 경우에는 외부에서 따로 동기화를 해줘야 합니다.

public class TreeSetExample {
    // 참고로 TreeSet은 기본 연산(add, remove, contains)의 시간 복잡도는 O(log(n))이다.
    public static void main(String[] args) {
        NavigableSet<Integer> a = new TreeSet<>(Arrays.asList(10, 4, 7, 3, 5, 8, 2, 1, 9, 6));
        System.out.println("a = " + a);

        System.out.println("\n셋에서 5보다 작은 요소 중 가장 큰 요소를 가져오기");
        System.out.println("a.lower(5) = " + a.lower(5)); // 4

        System.out.println("\n셋에서 5보다 큰 요소 중 가장 작은 요소를 가져오기");
        System.out.println("a.higher(5) = " + a.higher(5)); // 6

        System.out.println("\n처음 요소를 제거 후 그 값을 반환하기:");
        System.out.println("a.pollFirst() = " + a.pollFirst()); // 1
        System.out.println("a = " + a);

        System.out.println("\n역순 뷰 가져오기:");
        // a.descendingSet() = [10, 9, 8, 7, 6, 5, 4, 3, 2]
        System.out.println("a.descendingSet() = " + a.descendingSet());

        System.out.println("\n5 이상 8 미만의 요소들을 가져오기:");
        // a.subSet(5, 8) = [5, 6, 7]
        System.out.println("a.subSet(5, 8) = " + a.subSet(5, 8));
    }
}

Queue

인터페이스: Queue

큐(Queue)는 보통 선입선출(FIFO, 먼저 들어온게 먼저 나가는)로 동작하는 자료구조입니다. 즉, 제거가 큐의 시작 부분에서 일어나고 삽입이 큐의 끝 부분에서 일어납니다. 매장이나 은행에 설치된 순번 대기표를 떠올려보면 이해가 좀 더 쉽습니다. 큐의 처음을 보통 head, front라고 하고 끝을 tail, rear라고 합니다.

public interface Queue<E> extends Collection<E> {
    // 큐에 요소를 추가합니다. 만약에 큐에 공간(capacity) 제한이 있고 큐가 가득 찼을 때는 IllegalStateException 예외가 발생합니다. 
    boolean add(E e);

    // 큐에 요소를 추가합니다. 공간 제한이 있는 큐에서 큐가 가득 찼을 때는 예외를 발생시키는 게 아니라 false를 반환합니다.
    boolean offer(E e);

    // 큐의 헤드(head)에 있는 값을 제거하고 그 값을 반환합니다. 이 메서드는 poll()과 동일하지만 큐가 비어 있으면 NoSuchElementException 예외를 던진다는 점에서 다릅니다.
    E remove();

    // 큐의 헤드(head)에 있는 값을 제거하고 그 값을 반환합니다. 만약 큐가 비어 있으면 null을 반환합니다.
    E poll();

    // 큐의 헤드에 있는 값을 가져오지만 제거하지는 않습니다. 만약 큐가 비어 있으면 NoSuchElementException 예외가 발생한다는 점에서 peek()과는 다릅니다.
    E element();

    // 큐의 헤드에 있는 값을 가져오지만 제거하지는 않습니다. 만약 큐가 비어 있으면 null을 반환합니다.
    E peek();
    ...
}

인터페이스: Deque(Double Ended Queue)

덱(deque, 또는 데크)은 양쪽 끝에서 요소의 삽입과 제거를 지원하는 자료구조입니다. 덱을 큐로 사용하면 선입선출(FIFO)로 동작하며, 후입선출(LIFO)인 스택으로도 사용할 수 있습니다.

public interface Deque<E> extends Queue<E> {
    // 덱의 앞쪽(first) 혹은 뒤쪽(last)에 요소를 추가합니다. 만약에 덱에 공간(capacity) 제한이 있고 덱이 가득 찼을 때는 IllegalStateException 예외가 발생합니다. 공간 제한이 있다면 보통 offerFirst()를 사용하는 게 좋습니다.
    void addFirst(E e); // push(E)와 동일
    void addLast(E e); // add(E)와 동일

    // 덱의 앞쪽 혹은 뒤쪽에 요소를 추가하는 건 addFirst(), addLast()와 똑같지만 공간 제한이 있는 덱에서 덱이 가득 찼을 때는 예외를 발생시키는 게 아니라 false를 반환합니다.
    boolean offerFirst(E e);
    boolean offerLast(E e); // offer(E)와 동일

    // 이 덱의 앞쪽 혹은 뒤쪽 요소를 제거하고 그 요소를 반환합니다. 이 메서드는 pollFirst(), pollLast()와 동일하지만 덱이 비어 있으면 NoSuchElementException 예외를 던진다는 점에서 다릅니다.
    E removeFirst(); // pop()과 동일
    E removeLast();

    // 이 덱의 앞쪽 혹은 뒤쪽 요소를 제거하고 그 요소를 반환합니다. 만약 덱이 비어 있으면 null을 반환합니다.
    E pollFirst();
    E pollLast();

    // 덱의 앞쪽 혹은 뒤쪽에 있는 요소를 가져오지만 제거하지는 않습니다. 이 메서드는 peekFirst(), peekLast()와 동일하지만 덱이 비어 있으면 NoSuchElementException 예외를 던진다는 점에서 다릅니다.
    E getFirst();
    E getLast();

    // 덱의 앞쪽 혹은 뒤쪽에 있는 요소를 가져오지만 제거하지는 않습니다. 만약 덱이 비어 있으면 null을 반환합니다.
    E peekFirst();
    E peekLast();

    // 주어진 요소를 앞에서 뒤로(first) 혹은 뒤에서 앞으로(last) 탐색을 시작하여 찾은 첫 번째 요소를 덱에서 제거합니다. 더 자세히 말하면 Objects.equals(o, e)가 참인 첫 번째(first) 혹은 마지막(last) 요소 e를 제거합니다. 성공적으로 제거한 경우에는 true, 제거되지 않은 경우(발견하지 못한 경우)에는 false를 반환합니다.
    boolean removeFirstOccurrence(Object o);
    boolean removeLastOccurrence(Object o);

    // addLast(E)와 동일합니다. 반환값은 항상 true입니다.
    boolean add(E e);

    // offerLast(E)와 동일합니다.
    boolean offer(E e);

    // addFirst(E)와 동일합니다.
    void push(E e);

    // removeFirst()와 동일합니다.
    E pop();

    ...
}

구현: PriorityQueue

우선순위 힙(priority heap)을 사용하여 만든 우선순위 큐(priority queue)의 구현입니다. 따라서 가장 처음 요소(head)가 가장 크거나 가장 작다는 사실만 알 수 있습니다.

참고로, 우선순위 큐에는 null 값이 들어갈 수 없습니다. 그리고 크기가 자동으로 증가하므로 따로 지정해주지 않아도 됩니다. 주의할 점은 동기화되지 않기 때문에 따로 동기화가 필요하다면 스레드 안전(thread-safe)한 PriorityBlockingQueue를 사용합시다.

public class PriorityQueueExample {
    // 참고로 삽입과 제거 연산(offer(), poll(), remove(), add())의 시간 복잡도는 O(log(n))이다.
    // remove(Object)와 contains(Object)는 O(n)이다.
    // peek(), element(), size()는 O(1)이다.
    public static void main(String[] args) {
        Queue<Integer> minHeap = new PriorityQueue<>(); // 최소 힙

        Random r = new Random();
        for (int i = 0; i < 10; i++)
            minHeap.add(r.nextInt(100));

        // 처음 요소에만 관심이 있고 나머지는 필요할 때 정렬한다. 처음 요소가 가장 작은 것을 볼 수 있다.
        System.out.println("minHeap = " + minHeap);

        System.out.println("\n큐가 빌 때까지 반복해서 처음 요소를 꺼내기:");
        while (!minHeap.isEmpty())
            System.out.print(minHeap.poll() + " ");
        System.out.println("\n");

        Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // 최대 힙

        for (int i = 0; i < 10; i++)
            maxHeap.add(r.nextInt(100));

        // 처음 요소가 가장 큰 것을 볼 수 있다.
        System.out.println("maxHeap = " + maxHeap);

        System.out.println("\n큐가 빌 때까지 반복해서 처음 요소를 꺼내기:");
        while (!maxHeap.isEmpty())
            System.out.print(maxHeap.poll() + " ");
        System.out.println();
    }
}

구현: ArrayDeque

ArrayDeque는 크기를 변경할 수 있는 배열을 통해 만든 Deque 인터페이스의 구현입니다.

ArrayDeque는 따로 크기 제한이 없으며 확장이 필요하면 자동으로 증가합니다. 참고로, ArrayDeque에는 null 값이 들어갈 수 없습니다. 주의할 점은 동기화되지 않기 때문에 동기화가 필요한 경우에는 외부에서 따로 동기화를 해주어야 합니다. 이 클래스를 스택으로 사용하면 Stack보다 빠를 수 있으며, 큐로 사용할 경우 LinkedList보다 빠를 수 있습니다.

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        Random r = new Random();
        for (int i = 0; i < 10; i++)
            deque.add(r.nextInt(100));
        System.out.println("deque = " + deque);

        System.out.println("\n앞뒤에 요소 삽입하기");
        deque.addFirst(0);
        deque.addLast(100);
        System.out.println("deque = " + deque);

        System.out.println("\n앞뒤에 있는 요소 제거하기:");
        System.out.println("deque.removeLast() = " + deque.removeLast());
        System.out.println("deque.removeFirst() = " + deque.removeFirst());
        System.out.println("deque = " + deque);

        System.out.println("\n앞뒤에 있는 요소 제거하지 않고 가져오기:");
        System.out.println("deque.peekLast() = " + deque.peekLast());
        System.out.println("deque.peekFirst() = " + deque.peekFirst());
        System.out.println("deque = " + deque);
    }
}

Collections

이 클래스에는 컬렉션을 다루거나 반환하는 정적 메서드만 들어가 있는 유틸리티 클래스입니다.

public class Collections {
    // 요소의 자연 순서에 따라서 주어진 리스트를 오름차순으로 정렬한다. 리스트 내의 모든 요소는 Comparable 인터페이스를 구현해야 한다.
    public static <T extends Comparable<? super T>> void sort(List<T> list) { ... }
    public static <T> void sort(List<T> list, Comparator<? super T> c) { ... }

    // 이진 탐색 알고리즘을 사용하여 리스트 내에서 요소를 검색한다. 이 메서드를 호출하기 전에 리스트를 자연 순서에 따라서 오름차순으로 정렬해야 한다.
    public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { ... }
    public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) { ... }

    // 주어진 리스트의 요소 순서를 뒤집는다. 이 메서드는 시간 복잡도가 O(n)이다.
    public static void reverse(List<?> list) { ... }

    // 리스트를 무작위로 섞는다. 이 메서드는 시간 복잡도가 O(n)이다.
    public static void shuffle(List<?> list) { ... }
    public static void shuffle(List<?> list, Random rnd) { ... }

    // 리스트에서 두 위치에 있는 요소를 서로 바꾼다.
    public static void swap(List<?> list, int i, int j) { ... }
    private static void swap(Object[] arr, int i, int j) { ... }

    // 리스트의 모든 요소를 지정한 요소로 바꾼다. 이 메서드는 시간 복잡도가 O(n)이다.
    public static <T> void fill(List<? super T> list, T obj) { ... }

    // 한 리스트에서 다른 리스트로 모든 요소를 복사한다. 이 메서드는 시간 복잡도가 O(n)이다.
    public static <T> void copy(List<? super T> dest, List<? extends T> src) { ... }

    // 요소의 자연 순서나 넘겨준 Comparator를 통해 부여된 순서에 따라서 컬렉션 내에서 최소 혹은 최대 요소를 반환한다. 컬렉션 내의 모든 요소는 Comparable 인터페이스를 구현해야 한다.
    public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) { ... }
    public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) { ... }
    public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) { ... }
    public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) { ... }

    // 리스트를 주어진 거리(distance)만큼 회전시킨다. 이 메서드를 호출한 후 인덱스 i에 있는 요소는 전에 인덱스 (i - distance) % list.size()에 있던 요소가 된다.
    public static void rotate(List<?> list, int distance) { ... }

    // 리스트 내에서 주어진 값을 모두 다른 값으로 변경한다. 좀 더 자세히 말하면, (oldval == null ? e == null : oldVal.equals(e))가 참인 요소 e가 모두 newVal로 변경된다.
    public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal) { ... }

    // 원본(source) 리스트 내에서 대상(target) 리스트가 등장하는 첫 번째 혹은 마지막 위치를 반환하고, 만약 없으면 -1을 반환한다. 더 자세히 말하면 source.subList(i, i + target.size()).equals(target)가 참인 가장 낮은 혹은 높은 인덱스를 반환한다.
    public static int indexOfSubList(List<?> source, List<?> target) { ... }
    public static int lastIndexOfSubList(List<?> source, List<?> target) { ... }

    // 자연 순서의 역순을 나타내는 Comparator를 반환한다(자연 순서는 객체의 compareTo() 메서드를 통해 부여되는 순서다).
    public static <T> Comparator<T> reverseOrder(Comparator<T> cmp) { ... }

    // 컬렉션에서 주어진 객체 o와 동일한 요소의 수를 반환한다. 좀 더 자세히 말하면, Objects.equals(o, e)가 참인 요소 e의 수를 반환한다.
    public static int frequency(Collection<?> c, Object o) { ... }

    // 두 컬렉션에 같은 요소가 하나도 없는 경우 true를 반환한다.
    public static boolean disjoint(Collection<?> c1, Collection<?> c2) { ... }

    ...
}

예제를 간단하게 살펴보면 다음과 같습니다.

public class CollectionsExample {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 7, 10, 2, 3, 5, 6, 8, 9, 4));

        System.out.println("list = " + list);

        System.out.println("\n정렬:");
        Collections.sort(list);
        System.out.println("list = " + list);

        System.out.println("\n이진 탐색:");
        int foundPos = Collections.binarySearch(list, 6);
        System.out.println("foundPos = " + foundPos);

        System.out.println("\n리스트 뒤집기:");
        Collections.reverse(list);
        System.out.println("list = " + list);

        System.out.println("\n요소 서로 바꾸기:");
        Collections.swap(list, 0, 9);
        System.out.println("list = " + list);

        System.out.println("\n역순 정렬:");
        Collections.sort(list, Collections.reverseOrder());
        System.out.println("list = " + list);

        System.out.println("\n회전:");
        Collections.rotate(list, 3);
        System.out.println("list = " + list);

        System.out.println("\n리스트 섞기:");
        Collections.shuffle(list);
        System.out.println("list = " + list);

        int min = Collections.min(list);
        int max = Collections.max(list);
        System.out.println("\n최소값:" + min + ", 최대값: " + max);
    }
}

Map

인터페이스: Map

Map은 키를 값에 매핑(mapping, 또는 대응)시키는 자료구조입니다. 맵에서 키가 중복될 수 없으며, 하나의 키는 최대 하나의 값에만 매핑시킬 수 있습니다.

public interface Map<K, V> {
    // === 질의 연산(query operations) ===
    // 이 맵의 키-값 매핑의 수를 반환합니다. 맵에 요소 수가 Integer.MAX_VALUE개를 넘어가면 Integer.MAX_VALUE를 반환합니다.
    int size();

    // 이 맵에 키-값 매핑이 없으면 true를 반환합니다.
    boolean isEmpty();

    // 어떤 값을 주어진 키로 매핑하고 있으면 true를 반환합니다. 더 자세히 말하면, 이 맵에 Objects.equals(key, k)가 참인 키 k가 어떤 값에 매핑된 상태면 true를 반환합니다.
    boolean containsKey(Object key);

    // 주어진 값에 매핑된 키가 하나 이상 있으면 true를 반환합니다. 더 자세히 말하면, 이 맵에 Objects.equals(key, k)가 참인 값 v가 어떤 키로 매핑된 상태면 true를 반환합니다.
    boolean containsValue(Object value);

    // 주어진 키로 매핑된 값을 반환하거나, 매핑된 값이 없으면 null을 반환합니다. 더 자세히 말하면, Objects.equals(key, k)가 참인 키 k로 매핑된 값을 가져오고, 없으면 null을 반환합니다.
    V get(Object key);

    // === 수정 연산(modification operations) ===
    // 키를 값에 매핑시킵니다. 만약에 그 키로 이미 매핑된 값이 있다면 기존 값을 변경합니다.
    // 반환값은 이전에 매핑된 값이거나 기존에 키 key로 매핑된 게 없었다면 null을 반환합니다.
    // 주의해야 할 점은 맵에서 null 값을 허용하는 경우에는 반환값 null의 의미가 두 개라는 것입니다. 하나는 기존에 키 key로 매핑된 게 없었다는 뜻이고, 또 하나는 이전에 매핑된 값이 null이라는 뜻입니다.
    V put(K key, V value);

    // 해당 키로 매핑된 값이 있는 경우 이를 맵에서 제거합니다. 더 자세히 말하면, Objects.equals(key, k)가 참인 키 k로 매핑된 값 v가 있다면 이러한 매핑을 제거합니다.
    // 반환값은 제거된 키-값 매핑의 값이며, 매핑이 없는 경우에는 null을 반환합니다.
    // 주의해야 할 점은 맵에서 null 값을 허용하는 경우에는 성공적으로 제거했다고 하더라도 null 값을 반환할 수 있다는 것입니다. 그 키가 null 값에 매핑되었을 수도 있기 때문입니다.
    V remove(Object key);

    // === 대량 연산(bulk operations) ===
    // 맵 m에서 현재 맵으로 모든 매핑을 복사합니다. 즉, 맵 m에 있는 키 k로 매핑된 값 v마다 현재 맵에서 put(k, v)를 한 번 호출하는 것과 같습니다.
    void putAll(Map<? extends K, ? extends V> m);

    // 맵에서 모든 매핑을 제거합니다.
    void clear();

    // === 뷰(views) ===
    // 키의 뷰를 Set으로 반환합니다. 맵에 변경이 일어나면 뷰에도 똑같이 일어나고 그 반대도 마찬가지입니다.
    Set<K> keySet();

    // 값의 뷰를 Set으로 반환합니다. 맵에 변경이 일어나면 뷰에도 똑같이 일어나고 그 반대도 마찬가지입니다.
    Collection<V> values();

    // 엔트리(entry, 또는 항목)의 뷰를 Set으로 반환합니다. 엔트리는 키-값의 쌍으로 getKey()나 getValue()로 키나 값을 얻어올 수 있습니다.
    Set<Map.Entry<K, V>> entrySet();

    // === 비교와 해싱(comparison and hashing) ===
    // 주어진 객체 o를 현재 맵과 비교하여 동등성(equality)을 확인합니다. 주어진 객체도 Map이고 두 맵의 매핑이 서로 같다면 true를 반환합니다.
    boolean equals(Object o);

    // 이 리스트의 해시 코드 값을 반환합니다.
    int hashCode();

    // == 디폴트 메서드(defaultable methods) ===
    // 주어진 키 key로 매핑된 값이 있으면 반환하고, 없으면 기본값 defaultValue를 반환합니다.
    default V getOrDefault(Object key, V defaultValue);

    // for-each의 메서드 버전입니다. 모든 엔트리가 처리되거나 예외가 발생할 때까지 각 엔트리에 주어진 action을 실행합니다.
    default void forEach(BiConsumer<? super K, ? super V> action);

    // 모든 엔트리가 처리되거나 예외가 발생할 때까지 각 엔트리마다 function을 호출하여 값을 반환된 값으로 변경합니다.
    default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function);

    // 주어진 키 key로 매핑된 값이 아직 없을 경우(아니면 null에 매핑된 경우) 키를 주어진 값 value로 매핑시킵니다. 만약에 매핑된 값이 있으면 그 값을 반환합니다.
    default V putIfAbsent(K key, V value);

    // 주어진 키 key가 주어진 값 value에 매핑된 경우에만 해당 엔트리를 제거합니다.
    default boolean remove(Object key, Object value);

    // 주어진 키 key가 주어진 값 oldValue에 매핑된 경우에만 새로운 값 newValue로 변경합니다.
    default boolean replace(K key, V oldValue, V newValue);

    // 주어진 키 key가 어떤 값에 매핑되어 있는 경우에만 값 value로 변경합니다.
    default V replace(K key, V value);

    ...
}

맵 초기화 하기

자바 9부터는 List.of(), Set.of()와 마찬가지로 Map.of(), Map.ofEntries()라는 정적 팩토리 메서드를 제공합니다. 마찬가지로 이 맵은 변경할 수 없는 컬렉션(ImmutableCollections)이므로 새로운 요소를 추가하거나 제거, 변경할 수 없습니다. 변경하려고 시도하면 UnsupportedOperationException 예외가 발생하니 주의합시다. 그리고 인수(argument)로 null을 넘기는 것은 허용되지 않습니다. 추가로 넘긴 인수 중에 중복된 키가 있으면 IllegalArgumentException 예외가 발생합니다.

// 자바 8 이전 (변경 가능)
Map<Integer, String> map = new HashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");

// 자바 9 이후 (변경 불가)
// 최대 10개의 키-값 쌍을 넣을 수 있으며 (키1, 값1, 키2, 값2, ..., 키10, 값10)과 같이 넣으면 된다.
Map<Integer, String> map = Map.of(
        1, "one", 
        2, "two", 
        3, "three"
);

// 자바 9 이후 (변경 불가)
// 이 방법은 Map.of()와 달리 개수 제한이 없다.
Map<Integer, String> map = Map.ofEntries(
        Map.entry(1, "one"),
        Map.entry(2, "two"),
        Map.entry(3, "three")
);

구현: HashMap

HashMap은 해시 테이블을 기반으로 맵을 구현한 것입니다.

키와 값에 모두 null이 들어갈 수 있으며, 맵 내의 순서가 일정하게 유지된다는 보장은 없습니다. 동기화가 되지 않았기 때문에 필요한 경우에는 외부에서 따로 동기화를 해주거나 ConcurrentHashMap 혹은 Collections.synchronizedMap(T) 정적 메서드로 동기화된 Map을 얻는 방법이 있습니다(하지만 여전히 주의가 필요하며, 궁금하시다면 자바독을 참고해주세요).

public class HashMapExample {
    public static void main(String[] args) {
        Map<String, String> users = new HashMap<>();
        users.put("asteroidlog", "abc123");
        users.put("moonaries", "efg123");
        users.put("bagelbeef", "hij123");

        System.out.println("맵에 해당 키가 있는지 확인하기:");
        if (users.containsKey("moonaries")) {
            System.out.println("맵에 키 moonaries가 있으며 값은 " + users.get("moonaries") + "입니다.");
        }

        System.out.println("\nfor-each로 순회하기:");
        for (Map.Entry<String, String> user : users.entrySet()) {
            System.out.println(user.getKey() + ": " + user.getValue());
        }

        System.out.println("\n값을 모두 대문자로 바꾸기:");
        users.forEach((k, v) -> users.put(k, v.toUpperCase()));
        for (String password : users.values()) {
            System.out.print(password + " ");
        }

        System.out.println("\n\n기존 값 아니면 기본 값 가져오기:");
        System.out.println(users.getOrDefault("moonaries", "default"));
        System.out.println(users.getOrDefault("citylights", "default"));

        System.out.println("\n아직 없을 경우 맵에 넣기:");
        users.putIfAbsent("moonaries", "abc123");
        System.out.println("users.get(\"moonaries\") = " + users.get("moonaries"));
        users.putIfAbsent("citylights", "xyz123");
        System.out.println("users.get(\"citylights\") = " + users.get("citylights"));
    }
}

구현: LinkedHashMap

링크드 리스트(linked list)와 해시 테이블을 사용한 Map 인터페이스의 구현입니다.

HashMap과는 다르게 우리가 요소를 삽입한 순서가 그대로 유지됩니다. HashMap과 마찬가지로 동기화가 필요한 경우에는 외부에서 따로 동기화를 해줘야 하며, 키와 값에 모두 null이 들어갈 수 있습니다.

public class LinkedHashMapExample {
    public static void main(String[] args) {
        Map<String, List<String>> teams = new HashMap<>();
        teams.put("The Grass Frogs", Arrays.asList("John", "Paul", "George"));
        teams.put("Flaming Titans", Arrays.asList("Brian", "Anthony", "Steve", "Peter"));
        teams.put("Mad Suns", Arrays.asList("Michael", "Mark", "Mullins", "Anderson", "Walters"));

        System.out.println("=== for-each 루프를 통한 출력 ===");
        for (Map.Entry<String, List<String>> entry : teams.entrySet()) {
            System.out.println("팀: " + entry.getKey());
            for (String name : entry.getValue()) {
                System.out.print(name + " ");
            }
            System.out.println("\n");
        }

        System.out.println("=== for-each 메서드를 통한 출력 ===");
        teams.forEach((team, players) -> {
            System.out.println("팀: " + team);
            players.forEach(player -> System.out.print(player + " "));
            System.out.println("\n");
        });

        System.out.println("현재 맵의 크기: " + teams.size());
        teams.clear();
        System.out.println("clear() 후 현재 맵의 크기: " + teams.size());
    }
}

인터페이스: SortedMap

SortedMap은 Map 인터페이스를 상속하며 이 인터페이스를 구현하는 클래스는 한 요소를 다른 요소와 서로 비교할 수 있으므로 각 요소에 순서를 부여할 수 있습니다. 자연 순서(natural ordering)를 따라 정렬되거나 보통 생성자로 넘긴 Comparator를 통해서 정렬됩니다(이 순서는 entrySet(), keySet(), values()와 같은 뷰 연산에 반영됨). 이 SortedMap 내의 모든 요소는 Comparable 인터페이스를 구현하거나 우리가 넘긴 Comparator로 처리할 수 있어야 합니다.

public interface SortedMap<K,V> extends Map<K,V> {
    // 키를 정렬할 때 사용하는 Comparator를 반환합니다. 따로 없는 경우에는(자연 순서를 따르는 경우에는) null을 반환합니다.
    Comparator<? super K> comparator();

    // 이 맵에서 키의 범위가 from(포함)부터 to(제외)까지인 부분 맵의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 변경하면 원본 맵에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedMap<K,V> subMap(K fromKey, K toKey);

    // 이 맵에서 키가 toKey보다 작은 부분 맵의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 변경하면 원본 맵에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedMap<K,V> headMap(K toKey);

    // 이 맵에서 키가 fromElement보다 크거나 같은 부분 맵의 뷰를 반환합니다. 따라서 반환된 뷰를 통해 변경하면 원본 맵에도 영향을 미치며, 그 반대도 마찬가지입니다.
    SortedMap<K,V> tailMap(K fromKey);

    // 현재 이 맵에 있는 첫 번째(최저) 키를 반환합니다.
    K firstKey();

    // 현재 이 맵에 있는 마지막(최고) 키를 반환합니다.
    K lastKey();

    ...
}

인터페이스: NavigableMap

찾으려는 키와 가장 가까운 키를 반환하는 탐색 메서드를 추가한 SortedMap의 확장 인터페이스입니다.

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    // 맵에서 주어진 키 key보다 작은 키 중 가장 큰 키를 가진 엔트리를 반환합니다. 없으면 null을 반환합니다.
    Map.Entry<K,V> lowerEntry(K key);

    // 맵에서 주어진 키 key보다 작은 키 중 가장 큰 키를 반환합니다. 없으면 null을 반환합니다.
    K lowerKey(K key);

    // 맵에서 주어진 키 key보다 작거나 같은 키 중에서 가장 큰 키를 가진 엔트리를 반환합니다. 없으면 null을 반환합니다.
    Map.Entry<K,V> floorEntry(K key);

    // 맵에서 주어진 키 key보다 작거나 같은 키 중에서 가장 큰 키를 반환합니다. 없으면 null을 반환합니다.
    K floorKey(K key);

    // 맵에서 주어진 키 key보다 크거나 같은 키 중에서 가장 작은 키를 가진 엔트리를 반환합니다. 없으면 null을 반환합니다.
    Map.Entry<K,V> ceilingEntry(K key);

    // 맵에서 주어진 키 key보다 크거나 같은 키 중에서 가장 작은 키를 반환합니다. 없으면 null을 반환합니다.
    K ceilingKey(K key);

    // 맵에서 주어진 키 key보다 큰 키 중에서 가장 작은 키를 가진 엔트리를 반환합니다. 없으면 null을 반환합니다.
    Map.Entry<K,V> higherEntry(K key);

    // 맵에서 주어진 키 key보다 큰 키 중에서 가장 작은 키를 반환합니다. 없으면 null을 반환합니다.
    K higherKey(K key);

    // 맵에서 가장 작은 키를 가진 엔트리를 반환합니다. 맵이 비어 있으면 null을 반환합니다.
    Map.Entry<K,V> firstEntry();

    // 맵에서 가장 큰 키를 가진 엔트리를 반환합니다. 맵이 비어 있으면 null을 반환합니다.
    Map.Entry<K,V> lastEntry();

    // 맵에서 가장 작은 키를 가진 엔트리를 제거하고 그 엔트리를 반환합니다. 맵이 비어 있으면 null을 반환합니다.
    Map.Entry<K,V> pollFirstEntry();

    // 맵에서 가장 큰 키를 가진 엔트리를 제거하고 그 엔트리를 반환합니다. 맵이 비어 있으면 null을 반환합니다.
    Map.Entry<K,V> pollLastEntry();

    // 이 맵의 역순(reverse order) 뷰를 반환합니다. 따라서 반환된 뷰를 통해 변경하면 원본 맵에도 영향을 미치며, 그 반대도 마찬가지입니다.
    NavigableMap<K,V> descendingMap();

    ...
}

구현: TreeMap

TreeMap은 레드 블랙 트리(red–black tree)를 기반으로 NavigableMap 인터페이스를 구현한 것입니다.

이 맵은 키의 자연 순서 혹은 생성자로 넘긴 Comparator에 따라 정렬됩니다. 동기화가 되지 않았기 때문에 필요한 경우에는 외부에서 따로 동기화를 해주거나 ConcurrentSkipListMap 혹은 Collections.synchronizedSortedMap(SortedMap<K,V>) 정적 메서드로 동기화된 SortedMap을 얻는 방법이 있습니다(하지만 여전히 주의가 필요하며, 궁금하시다면 자바독을 참고해주세요).

public class TreeSetExample {
    // 참고로 containsKey(), get(), put(), remove() 연산은 O(log(n))의 시간 복잡도를 가진다.
    public static void main(String[] args) {
        NavigableMap<Integer, String> map = new TreeMap<>();
        map.put(3, "three");
        map.put(1, "one");
        map.put(2, "two");
        map.put(4, "four");

        System.out.println("map.lowerEntry(3): " + map.lowerEntry(3));
        System.out.println("map.lowerKey(3): " + map.lowerKey(3));

        System.out.println("map.higherEntry(1): " + map.higherEntry(2));
        System.out.println("map.higherKey(1): " + map.higherKey(2));

        System.out.println("map.firstEntry(): " + map.firstEntry());
        System.out.println("map.lastEntry(): " + map.lastEntry());

        System.out.println("\n맵 전체 출력:");
        for (Map.Entry<Integer, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }

        System.out.println("\n맵 역순 전체 출력:");
        for (Map.Entry<Integer, String> entry : map.descendingMap().entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

가능하다면 항상 인터페이스 타입을 사용하자

이는 컬렉션에만 적용되는 얘기가 아닙니다. 가능한 구체적인 타입보다 일반적인 타입을 쓰는 게 좋습니다. 이렇게 하면 변경의 범위가 줄어들고, 재사용하기 용이한 메서드가 만들어집니다. 간단한 예를 들어서 ArrayList 내의 두 요소의 자리를 서로 바꾸는 메서드가 있다고 할 때 아래와 같이 메서드를 선언할 수 있습니다.

public static void swap(ArrayList<?> list, int i, int j) {
	final ArrayList l = list;
	l.set(i, l.set(j, l.get(i)));
}

하지만 이러면 LinkedList나 Vector, Stack에서는 이런 메서드를 사용할 수 없으며 필요하다면 기능이 똑같은 메서드를 다시 정의해야 합니다. 인덱스를 기반으로 값을 가져오거나 변경하는 get()과 set() 메서드는 List 인터페이스에 선언되어 있으므로 우리는 이를 아래와 같이 고쳐쓸 수 있습니다.

// Collections.swap(List<?>, int, int)
public static void swap(List<?> list, int i, int j) {
	final List l = list;
	l.set(i, l.set(j, l.get(i)));
}

이렇게 만들면 swap() 입장에서는 구체적인 타입을 몰라도 되고, 향후에 List를 구현하는 클래스가 새로 추가되어도 별다른 변경 없이 기존의 메서드를 재사용할 수 있게 됩니다. 추가로, 다른 구현으로 변경하고 싶은 경우에 실제 타입만 살짝 바꾸기만 하면 됩니다. 이는 기존 코드가 ArrayList의 존재를 모르기 때문에 가능한 일입니다.

// 변경 전
List<Integer> nums = new ArrayList<>();
...

// 변경 후
List<Integer> nums = new LinkedList<>();
...

물론 인터페이스가 잘 설계되었다는 가정 하에 해당 인터페이스에는 없고 그 클래스에만 정의된 기능, 즉 그 클래스에 특화된 기능이 있는 경우에는 클래스로 참조해야 합니다.