컬렉션 프레임웍 (Collections Framework)

다수의 데이터(Collection)를 다루는 클래스의 표준 설계(Framework)

JDK 1.2부터 도입됨

 

컬렉션 프레임웍의 핵심 인터페이스

컬렉션에는 3가지 타입이 존재 (List, Set, Map)

이들 각각을 다루는데에 필요한 기능을 List, Set, Map 인터페이스로 정의함.

이 중에서 List와 Set은 공통적인 부분이 많아서 상위 인터페이스로 Collection을 만들고 거기에 공통 기능들을 넣었음.

인터페이스	특징	구현 클래스
List	- 순서가 있는 데이터의 집합 - 데이터의 중복 허용	ArrayList, LinkedList, Stack, Vector
Set	- 순서가 유지되지 않는 데이터의 집합 - 데이터의 중복 불허	HashSet, TreeSet
Map	- key와 value의 쌍으로 이루어진, 순서가 유지되지 않는 데이터의 집합 - key 중복 불허, value 중복은 허용	HashMap, TreeMap, Hashtable, Properties

 

구현 클래스의 네이밍을 보면 자신이 구현한 인터페이스의 이름을 포함하고 있음

Stack, Vector, Hashtable, Properties는 컬럭션 프레임웍이 등장하기 이전부터 있었기 때문에 네이밍 컨벤션을 따르지 않음.

가능하면 구형 컬렉션인 Vector 대신 ArrayList를, Hashtable 대신 HashMap을 사용하는 것이 좋음

 

Collection 인터페이스

List와 Set 인터페이스의 조상.

컬렉션 클래스에 저장된 데이터 읽기, 추가하기, 삭제하기 등의 기본적인 기능 정의

 

인터페이스

Map 인터페이스의 내부 인터페이스로, 저장되어있는 key-value쌍을 다루기 위한 용도.

따라서 Map을 구현하는 클래스에서는 Map.Entry도 같이 구현해야함

public interface Map {
    ...
    public static interface Entry {
        Object getKey();
        Object getValue();
        Object setValue();
        boolean equals(Object o);
        int hashCode();
        ...
    }
}

 

ArrayList

기존의 Vector를 개선한 것이기 때문에 기능적으로는 동일.

Vector는 레거시 호환 차원에서 남겨놓은 것이므로 되도록 ArrayList 사용 권장

Object 배열에 데이터를 0번 인덱스부터 순차적으로 저장함. (기본 배열 크기: 10)

저장 공간이 가득 차면, 더 큰 용량의 Object 배열을 생성해서 그쪽으로 데이터를 전부 복사하고, 마저 저장 작업을 함.

예시1) 기본 메서드 활용

class ArrayListExample {
    public static void main(String[] args) {
        ArrayList l1 = new ArrayList();
        l1.add(3);
        l1.add(1);
        l1.add(5);
        l1.add(4);
        l1.add(2); // l1: [3, 1, 5, 4, 2]

        ArrayList l2 = new ArrayList(l1.subList(1, 4)); // l2: [1, 5, 4]

        Collections.sort(l1); // l1: [1, 2, 3, 4, 5]
        Collections.sort(l2); // l2: [1, 4, 5]

        System.out.println(l1.containsAll(l2)); // true

        l2.set(2, "A"); // l2: [1, 4, "A"]

        l1.retainAll(l2); // l1: [1, 4]

        for (int i = (l2.size() - 1); i >= 0; i--) {
            if (l1.contains(l2.get(i))) l2.remove(i);
        }

        System.out.println(l2); // ["A"]
    }
}

for문에서 i를 0부터 증가시켜가며 삭제하면, 요소가 삭제될 때마다 배열 원소들이 당겨지면서 올바른 결과를 얻을 수 없게 되므로, i의 최대값부터 내려오면서 돌아야함

 

예시2) 문자열을 특정 단위만큼씩 잘라서 배열에 넣기

class ArrayListExample2 {
    public static void main(String[] args) {
        final int LIMIT = 10; // 10개씩 자를 예정
        String source = "1234567890abcdefghijABCDEFGHIJZZZ";
        int length = source.length();

        ArrayList list = new ArrayList(length / LIMIT + 10); // 배열의 길이를 넉넉하게 잡고 시작

        for (int i = 0; i < length; i += LIMIT) {
            if (i + LIMIT < length) {
                list.add(source.substring(i, i + LIMIT)); // i부터 (i + LIMIT) 인덱스까지 잘라서 list에 추가
            } else {
                list.add(source.substring(i)); // i부터 맨끝 인덱스까지 잘라서 list에 추가
            }
        }

        System.out.println(list); // [1234567890, abcdefghij, ABCDEFGHIJ, ZZZ]
}

📌 [주의] ArrayList를 생성할 때 크기를 여유있게 만드는 것이 좋음.

작업 도중 공간이 부족하면 크기를 알아서 늘려주기는 하지만, 이 과정에서 처리시간이 불필요하게 소모되기 때문

 

LinkedList

앞서 살펴보았던 ArrayList의 단점을 먼저 짚어보자.

1. 크기 변경 불가

   • 원하는 크기의 새로운 인스턴스를 생성하여 그곳에 모든 데이터를 붙여넣는 식으로만 크기 변경 가능

   • 성능 이슈를 감안해 처음부터 넉넉한 크기로 생성해버리면, 남는 공간이 생겨 메모리가 낭비될 수 있음

2. 비순차적 데이터의 추가와 삭제 작업이 비효율적임

   • 배열의 중간에 데이터를 추가하거나 삭제할 때, 해당 자리 뒤의 원소들을 모두 복사해서 한칸 밀거나 당겨 붙여넣는 작업이 이루어지므로 비효율적.

 

이러한 단점을 보완하기 위해 나온 것이 Linked List.

배열은 모든 데이터가 연속적으로 존재하지만, Linked List는 불연속적으로 존재하는 데이터를 연결한 구조.

Linked List의 각 요소(node)는 데이터와 함께 자신과 연결된 다음 node의 주소값을 가지고 있음.

class Node {
    Node next; // 다음 노드의 주소값
    Object obj; // 데이터
}

 

Linked List에서 요소를 추가하거나 삭제하는 프로세스는 매우 간단함.

1. 요소 추가

   추가할 위치의 이전 Node가 신규 Node를 참조하게 하고, 신규 Node가 추가할 위치 다음의 Node를 참조하게 만들면 됨.

   추가 전: prevNode --------------------> nextNode

   추가 후: prevNode ----> newNode ----> nextNode

2. 요소 삭제

   삭제하고자 하는 node의 이전 node가 삭제하고자 하는 node의 다음 node를 참조하게 만들면 됨

   삭제 전: prevNode ---> targetNode ---> nextNode

   삭제 후: prevNode --------------------> nextNode

 

Linked List는 이동 방향이 단방향이라서 다음 Node 접근은 쉽지만, 이전 Node 접근은 어려움

이를 보완한 Doubly Linked List는 Node 안에 다음 Node의 주소값 뿐만 아니라, 이전 Node의 주소값도 저장함.

LinkedList는 이름과는 다르게 실제로는 이 Doubly Linked List로 구현되어 있음

class Node {
    Node next; // 다음 노드 주소값
    Node previous; // 이전 노드 주소값
    Object obj; // 데이터
}

여기서 한 발 더 나아가 Doubly Linked List의 접근성을 더 향상시킨 것이 Doubly Circular Linked List임

이름의 circular에서 짐작할 수 있듯, 순환 구조를 띄고 있어 마지막 Node가 첫번째 Node의 주소값을 가지고 있고, 첫번째 Node도 마지막 Node의 주소값을 가지고 있음

원래의 Linked List나 Doubly Linked List에서는 순환 구조가 아니므로 해당 값들이 null임

 

(메서드 전체는 교재 p.598 참고)

LinkedList의 메서드 중 element()와 peek()은 모두 첫번째 요소를 반환함.

단, 리스트가 비어있을 때 element()는 NoSuchElementException을 던짐

따라서 리스트가 비어있으면 안되는 경우라면 element()를 써서 fail fast 하는게 나음

이처럼 메서드 중에는 같은 기능을 하는 것들이 있는데, 그 중에서 작업 실패시 예외를 던지는 메서드를 사용하는 것이 디버깅 측면에서는 안전함.

 

👨‍💻 ArrayList와 LinkedList 성능 테스트

예시)

import java.util.*;

class LinkedListExample {
    public static void main(String[] args) {
        ArrayList al = new ArrayList(2000000);
        LinkedList ll = new LinkedList();

        System.out.println("---순차적으로 추가하기---");
        System.out.println("ArrayList: " + add1(al) + "ms");
        System.out.println("LinkedList: " + add1(ll) + "ms");

        System.out.println("---중간에 추가하기---");
        System.out.println("ArrayList: " + add2(al) + "ms");
        System.out.println("LinkedList: " + add2(ll) + "ms");

        System.out.println("---순차적으로 삭제하기---");
        System.out.println("ArrayList: " + remove1(al) + "ms");
        System.out.println("LinkedList: " + remove1(ll) + "ms");

        add1(al);
        add1(ll);

        System.out.println("---중간에 삭제하기---");
        System.out.println("ArrayList: " + remove2(al) + "ms");
        System.out.println("LinkedList: " + remove2(ll) + "ms");
    }

    public static long add1(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 1000000; i++) list.add(i);
        long end = System.currentTimeMillis();
        return (end - start);
    }

    public static long add2(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) list.add(500, i);
        long end = System.currentTimeMillis();
        return (end - start);
    }

    public static long remove1(List list) {
        long start = System.currentTimeMillis();
        for(int i = (list.size() - 1); i >= 0; i--) list.remove(i);
        long end = System.currentTimeMillis();
        return (end - start);
    }

    public static long remove2(List list) {
        long start = System.currentTimeMillis();
        for(int i = 0; i < 10000; i++) list.remove(i);
        long end = System.currentTimeMillis();
        return (end - start);
    }
}

실행 결과)

---순차적으로 추가하기---
ArrayList: 23ms
LinkedList: 147ms
---중간에 추가하기---
ArrayList: 2478ms
LinkedList: 9ms
---순차적으로 삭제하기---
ArrayList: 6ms
LinkedList: 18ms
---중간에 삭제하기---
ArrayList: 1249ms
LinkedList: 100ms

테스트 결과로 다음과 같은 결론을 얻음.

1. 데이터를 순차적으로 추가/삭제하는 경우 ArrayList가 더 빠름

   단, 여기서는 저장 속도만 비교하기 위해 처음에 ArrayList에 충분한 크기를 지정해줬음.

   만약 크기 지정 없이 진행했으면 반복적으로 새 인스턴스를 생성하게 되어 속도가 LinkedList보다 느려질 수도 있음

2. 데이터를 중간에 추가/삭제하는 경우 LinkedList가 더 빠름

 

ArrayList와 LinkedList가 데이터를 읽어오는 방식에 대해서 살펴보자

ArrayList는 데이터가 저장된 메모리 주소가 연속적이기 때문에 index만 주어지면 곧바로 주소값을 도출할 수 있음. 즉, 첫번째 요소부터 순서대로 다 훑지 않아도 됨.

반면, LinkedList는 데이터가 저장 위치가 불연속적이라서 link를 따라 첫번째 요소부터 순서대로 따라가야만 n번째 요소에 접근할 수 있음.

따라서 읽기 작업에 있어서는 전체 데이터 개수가 많으면 많을수록 LinkedList가 성능이 떨어짐.

 

Stack과 Queue

Stack: Last-In-First-Out(LIFO)

Queue: First-In-First-Out(FIFO)

위의 특성을 고려했을 때, Stack은 데이터를 순차적으로 추가하고 삭제할 수 있는 ArrayList가 적합.

그러나 Queue의 경우는 첫번째 요소부터 빠져나가는 구조이므로 ArrayList로 구현할 시, 매번 요소들의 자리 이동이 발생하여 비효율적. 따라서 LinkedList가 적합.

 

👨‍💻 Stack과 Queue의 메서드를 활용한 요소 삽입 및 제거

예시)

Stack s = new Stack();
Queue q = new LinkedList(); // Queue 인터페이스의 구현 클래스

s.push(1);
s.push(2);
s.push(3);

q.offer(1);
q.offer(2);
q.offer(3);

System.out.println("---Stack---");
while (!s.isEmpty()) {
    System.out.println(s.pop());
}

System.out.println("---Queue---");
while (!q.isEmpty()) {
    System.out.println(q.poll());
}

실행 결과)

---Stack---
3
2
1
---Queue---
1
2
3

Stack은 별도 클래스가 존재하지만, Queue는 인터페이스로만 존재하므로 Queue를 구현한 클래스인 LinkedList를 사용

 

Stack 직접 구현하기

Stack은 컬렉션 프레임웍 이전부터 존재했기 때문에 Vector로부터 상속을 받음.

실제 Stack을 단순화하여 구현해보면 다음과 같음.

Vector에 구현된 메서드인 addElement(), removeElement(), elementAt(), size(), lastIndexOf() 사용

class MyStack extends Vector {
        public Object push(Object item) {
                addElement(item);
                return item;
        }

        public Object pop() {
                Object obj = peek();
                removeElementAt(size() - 1);
                return obj;
        }

        public Object peek() {
                if (size() == 0) throw new EmptyStackException();
                return elementAt(size() - 1);
        }

        public boolean empty() {
                return size() == 0;
        }

        public int search(Object o) {
                int i = lastIndexOf(o);
                if (i >= 0) return (size() - i);
                return -1;
        }
}

📌 [주의] Stack은 (가장 나중에 들어온) 맨 뒤의 요소부터 index 1로 간주하기 때문에 search() 메서드에서 반환하는 index는 앞에서부터 센 i가 아닌 size() - i 가 됨.

 

PriorityQueue

Queue 인터페이스의 구현체 중 하나.

저장 순서와 상관 없이 우선 순위(priority)가 높은 것부터 꺼냄

• null 저장 불가 (NullPointerException)

• 저장 공간으로 배열 활용

• 요소를 heap 형태로 저장

  heap은 최대값, 최소값을 빠르게 찾을 수 있는 구조이므로, 저장된 값의 크기에 따라 우선순위를 매기는 PriorityQueue에게 적합한 저장 방식

class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.offer(4);
        pq.offer(1);
        pq.offer(5);
        pq.offer(3);
        pq.offer(2);
        System.out.println(pq);

        Object obj = null;
        while ((obj = pq.poll()) != null) { // pq의 요소를 맨앞에서부터 하나씩 빼서 obj에 할당하고 출력
            System.out.println(obj);
        }
    }
}

실행 결과)

[1, 2, 5, 4, 3]
1
2
3
4
5

4, 1, 5, 3, 2 순서로 저장했는데 [1, 2, 5, 4, 3]으로 출력된 이유는 PriorityQueue의 자료구조가 heap이기 때문.

heap은 이진 트리 방식이므로 1 밑으로 2, 5가 오고, 다시 2 밑으로 4, 3이 왔다고 보면 됨

그리고 개별 원소를 하나씩 poll()로 빼낼 때는 숫자가 작을수록 우선순위가 높기 때문에 값이 낮은 순서대로 나왔음

만약 숫자가 아니고 객체를 요소로 갖고 있었다면, 객체 간의 크기를 비교할 방식을 제시해주어야함.

예시에서는 숫자를 넣어서 컴파일러가 Integer로 auto-boxing 해주었고, 자체적으로 비교 방식이 정의되어 있기 때문에 별도로 비교 방식을 제시해줄 필요가 없었던 것.

 

Deque(Double-Ended Queue)

Queue의 자손 인터페이스 (구현체: ArrayDeque, LinkedList)

Queue가 한쪽 방향으로만 추가 및 삭제가 가능한 반면, Deque는 양방향으로 추가 및 삭제가 가능.

사실상 Stack과 Queue의 기능을 모두 할 수 있는 존재

Java 공식 문서에서는 Stack을 레거시로 취급하고, Stack보다는 Deque를 활용할 것을 권장함.

 

👨‍💻 Deque를 Stack처럼 사용하기

class DequeExample {
    public static void main(String[] args) {
        Deque d = new ArrayDeque();
        d.offerLast(1);
        d.offerLast(2);
        d.offerLast(3);

        System.out.println(d);

        System.out.println(d.pollLast());
        System.out.println(d.pollLast());
        System.out.println(d.pollLast());

        System.out.println(d);
    }
}

실행 결과)

[1, 2, 3]
3
2
1
[]

 

👨‍💻 Deque를 Queue처럼 활용하기

class DequeExample {
        public static void main(String[] args) {
                Deque d = new ArrayDeque();
                d.offerLast(1);
                d.offerLast(2);
                d.offerLast(3);

                System.out.println(d);

                System.out.println(d.pollFirst());
                System.out.println(d.pollFirst());
                System.out.println(d.pollFirst());

                System.out.println(d);
        }
}

실행 결과)

[1, 2, 3]
1
2
3
[]

만약 offerFirst()에 pollLast()로 하면 반대 방향의 Queue가 됨

 

Iterator, ListIterator, Enumeration

셋 모두 컬렉션에 저장된 요소에 접근하는데 사용되는 인터페이스.

Enumeration은 Iterator의 구버전으로, 레거시 차원에서 남겨진 것이므로 Iterator 사용이 권장됨.

ListIterator는 Iterator를 향상시킨 버전

 

Iterator

객체 지향적 프로그래밍에서 배열이나 그와 유사한 자료 구조의 내부 요소를 순회(traverse)할 수 있게 해주는 객체.

컬렉션 프레임웍에서는 순회하는 방식을 표준화해서 Iterator 인터페이스로 정의함

 

Collection 인터페이스의 iterator() 메서드는 Iterator를 구현한 클래스의 인스턴스를 반환함.

특정 순회 방식이 정의된 클래스의 인스턴스를 반환한다는 뜻

컬렉션 클래스는 iterator()를 호출하여 Iterator를 얻은 다음 반복문을 돌려서 컬렉션 클래스의 요소들을 읽어올 수 있음.

 

👨‍💻 컬렉션 클래스 중 하나인 ArrayList에 저장된 요소를 출력하는 예시

Collection c = new ArrayList(); // 컬렉션 클래스의 인스턴스 생성
Iterator it = c.iterator(); // iterator() 호출로 Iterator 얻음

while (it.hasNext()) {
    System.out.println(it.next());
}

 

컬렉션 클래스들 중 Map 인터페이스를 구현한 것들은 데이터가 key-value 쌍으로 되어있기 때문에 바로 iterator()를 호출할 수 없음.

keySet(), entrySet() 메서드로 key의 집합과 value의 집합을 구한 다음 거기에 iterator()를 사용할 수 있음

Map map = new HashMap();
Iterator it = map.entrySet().iterator();

List 인터페이스를 구현한 클래스들은 저장순서가 유지되기 때문에 Iterator를 돌려서 읽어온 값의 순서가 저장순서와 동일.

Set 인터페이스를 구현한 클래스들은 동일하지 않음.

 

Iterator 인터페이스의 메서드

이렇게 표준화된 방식이 존재하기 때문에 컬렉션을 순회하는 코드 작성에 있어서 일관성, 재사용성이 높아짐.

1. boolean hasNext()

   읽어올 요소가 남아있는지 확인

2. Object next()

   다음 요소를 읽어옴

   안전하게 하려면, hasNext()가 true인지 먼저 확인하고 진행

3. void remove()

   next()로 읽어온 요소를 삭제

   optional method 이므로 구현하지 않고 구현부에 예외를 던지는 것으로 처리 가능

   public void remove() {
      throw new UnsupportedOperationException();
   }

   구현되지 않은 기능이라는 표시를 해줌으로써 메서드를 호출하는 사람이 바로 알 수 있게 함

 

ListIterator

Iterator는 순회 시 단방향 이동만 가능하지만, ListIterator는 양방향 이동이 가능함.

단, 이름에서 짐작 가능하듯 List 인터페이스를 구현한 클래스에서만 사용 가능.

발전된 순서로 보면 Enumeration(레거시) → Iterator → ListIterator

 

listIterator()를 호출해서 사용

class ListIteratorExample {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        ListIterator it = list.listIterator();

        while (it.hasNext()) {
            System.out.print(it.next()); // 12345
        }
        System.out.println();

        while (it.hasPrevious()) {
            System.out.print(it.previous()); // 54321
        }
        System.out.println();
    }
}

정방향과 역방향 순회가 모두 가능한 모습

next()나 previous() 사용 전에 hasNext()와 hasPrevious()를 확인하는 것이 중요

 

Arrays

Arrays 클래스에는 배열을 다루는 유용한 메서드가 정의되어 있음.

매개변수로 올 배열의 타입만 다르게 해서 같은 기능의 메서드가 다수 오버로딩 되어있음.

 

배열의 복사 - copyOf(), copyOfRange()

copyOf()는 배열 전체, copyOfRange()는 특정 인덱스 구간의 배열을 복사해서 만든 새로운 배열을 반환해줌.

int[] arr = {0, 1, 2, 3, 4};

int[] arr2 = Arrays.copyOf(arr, 3); // [0, 1, 2]
// arr배열의 원소를 앞에서부터 3개 복사

int[] arr3 = Arrays.copyOf(arr, 8); // [0, 1, 2, 3, 4, 0, 0, 0]
// 남는 자리는 0으로 채워짐

int[] arr4 = Arrays.copyOfRange(arr, 1, 3); // [1, 2]
// 인덱스 1이상 3 미만의 arr배열 원소를 복사

int[] arr5 = Arrays.copyOfRange(arr, 2, 7); // [2, 3, 4, 0, 0, 0]
// 남는 자리는 0으로 채워짐

 

배열 채우기 - fill(), setAll()

fill(): 배열의 모든 요소를 지정된 값으로 채움

setAll(): 함수형 인터페이스 구현 객체 또는 람다식을 매개변수로 받아 지정된 방식대로 배열을 채움

int[] arr = new int[5];

Arrays.fill(arr, 7); // [7, 7, 7, 7, 7]
// 모든 요소를 7로 채움

Arrays.setAll(arr, (e) -> (int)(Math.random() * 5) + 1); // [3, 1, 2, 4 ,5]
// 람다식으로 얻은 1 ~ 5 사이의 무작위 정수로 배열을 채움

 

배열의 정렬과 검색 - sort(), binarySearch()

sort(): 배열을 정렬할 때 사용

binarySearch(): 배열에 지정된 값이 저장된 인덱스를 찾아 반환

• 반드시 배열이 정렬된 상태여야 함

• 일치하는 값이 여러개인 경우 그 중에 하나가 무작위로 반환됨

int[] arr = { 6, 3, 5, 4, 2, 1, 7 };
int wrongIndex = Arrays.binarySearch(arr, 2);
System.out.println(wrongIndex); // -1

Arrays.sort(arr); // [1, 2, 3, 4, 5, 6, 7]
int correctIndex = Arrays.binarySearch(arr, 2);
System.out.println(correctIndex); // 1

sort()하지 않고 binarySearch()를 돌리면 잘못된 결과가 나온다는 것을 알 수 있음

 

배열의 비교와 출력 - equals(), toString()

toString(): 배열의 모든 요소를 문자열로 출력 (1차원 배열만)

다차원 배열은 deepToString()을 통해 구할 수 있음 (배열 안에 중첩된 배열들을 재귀적으로 접근)

int[] arr = {1, 2, 3, 4, 5};
int[][] arr2D = {{6, 7}, {8, 9}};

System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5]
System.out.println(Arrays.deepToString(arr2D)); // [[6, 7], [8, 9]]

equals(): 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false 반환 (1차원 배열만)

다차원 배열은 deepEquals()를 통해 구할 수 있음

다차원 배열은 배열의 주소값을 원소로 가지기 때문에 equals()로 단순히 원소의 값을 비교하면 주소값들이 각자 달라 항상 false가 나올 수 밖에 없음.

int[][] arr2D = {{6, 7}, {8, 9}};
int[][] arr2D2 = {{6, 7}, {8, 9}};

System.out.println(Arrays.equals(arr2D, arr2D2)); // false
System.out.println(Arrays.deepEquals(arr2D, arr2D2)); // true

 

배열을 List로 변환 - asList()

asList(): 배열을 List에 담아 반환.

매개변수 타입이 가변인수 Object... obj이므로 단순히 저장할 요소만 나열해도 List에 담아서 반환해줌.

List list = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});
List list2 = Arrays.asList(1, 2, 3, 4, 5);

System.out.println(list); // [1, 2, 3, 4, 5]
System.out.println(list2); // [1, 2, 3, 4, 5]

이렇게 생성된 List의 원소 값을 변경할 수는 있지만, 원소를 새로 추가하거나 삭제하는 것은 불가능.

list.add(6); // UnsupportedOperationException

asList()가 반환하는 것은 크기 변경이 불가한 List이기 때문

크기 변경이 가능하게 하려면, List 구현체 인스턴스의 생성자에 인자로 넘겨 같은 내용의 또 다른 List를 만들어 사용하면 됨.

List list = new ArrayList(Arrays.asList(1, 2, 3, 4, 5));

 

parallel~(), spliterator(), stream()

이름이 parallel로 시작하는 메서드: 빠른 결과 도출을 위해 여러 쓰레드에 작업을 나누어 처리하도록 함.

spliterator(): 하나의 작업을 여러 작업으로 나누는 Spliterator 반환.

stream(): 컬렉션을 스트림으로 변환.

 

Comparator와 Comparable

컬렉션을 정렬하는데 필요한 메서드를 정의한 인터페이스.

Arrays.sort()처럼 정렬하는 기능들은 기본적으로 Comparable을 구현하면서 만든 정렬 기준을 따르고 있음

Comparable로 구현된 기준을 따르지 않는다면 Comparator를 구현하여 만든 별도의 정렬 기준을 적용할 수 있음

 

Comparable: 기본 정렬 기준을 구현하는데에 사용

일반적으로 compareTo()는 객체 a와 b를 비교하여 a가 작으면 음수를, a가 크면 양수를, 같으면 0을 반환하도록 구현함

public interface Comparable {
    public int compareTo(Object o);
    // 이전에 봤던 String이나 Date 클래스의 compareTo()는 이 메서드를 구현한 것이었음
}

Comparable의 구현 클래스:

같은 타입의 인스턴스끼리 서로 비교 가능한 클래스

오름차순 정렬을 하도록 구현되어 있음

• wrapper 클래스 (ex. Integer)

• String, Date, File 등

 

Comparator: 기본 정렬 기준 외에 다른 정렬 기준을 구현하는데에 사용

public interface Comparator {
    int compare(Object o1, Object o2);
}

 

👨‍💻 Comparator 구현해보기 (내림차순)

class ComparatorExample {
    public static void main(String[] args) {
        Integer[] arr = {3, 1, 4, 2, 5};
        Arrays.sort(arr, new Descending()); // 새 Comparator 구현체의 인스턴스 제공
        System.out.println(Arrays.toString(arr)); // [5, 4, 3, 2, 1]
    }
}

class Descending implements Comparator {
    public int compare(Object o1, Object o2) {
        if (o1 instanceof Comparable && o2 instanceof Comparable) {
            // 비교 대상 객체들이 Comparable의 구현체여야만 compareTo를 사용할 수 있음
            Comparable c1 = (Comparable) o1;
            Comparable c2 = (Comparable) o2;

            return c1.compareTo(c2) * -1;
            // 기존 오름차순 정렬 방식의 부호를 바꿔줌으로써 역순인 내림차순으로 만듦
        }
        return -1;
    }
}

int[]가 아닌 Integer[]를 생성한 이유는 객체 배열이어야 compare()로 객체인 원소들을 비교할 수 있기 때문.

Descending 클래스의 return문에서

return c2.compareTo(c1);

처럼 반대로 메서드를 걸어주는 방식도 같은 결과를 반환함

 

HashSet

Set 인터페이스의 대표적인 구현체.

중복 요소를 허용하지 않기 때문에 중복 요소를 제거하는 로직에서 유용하게 쓰임.

저장 순서를 유지하지 않으므로, 저장 순서 유지가 필요하다면 LinkedHashSet을 사용

 

class HashSetExample {
    public static void main(String[] args) {
        Object[] arr = {"1", 1, "2", "2", "3", "3", "3"};
        Set set = new HashSet();

        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }

        System.out.println(set); // [1, 1, 2, 3]
    }
}

HashSet 안에 중복된 객체들은 저장하지 않았지만, 1의 경우는 하나는 String, 다른 하나는 Integer 인스턴스이므로 중복으로 간주하지 않아 둘 다 저장됨.

 

class HashSetExample2 {
    public static void main(String[] args) {
        Set set1 = new HashSet();

        set1.add(3);
        set1.add(2);
        set1.add(1);

        System.out.println(set1); // [1, 2, 3]

        Set set2 = new LinkedHashSet();

        set2.add(3);
        set2.add(2);
        set2.add(1);

        System.out.println(set2); // [3, 2, 1]
    }
}

HashSet은 3, 2, 1 순으로 요소를 삽입해도 1, 2, 3 으로 저장됨.

삽입된 순서와 관계없이 내부적인 저장 방식에 의해 요소들의 저장 순서를 정하기 때문에 Integer의 경우 오름차순으로 저장됨.

대신, LinkedHashSet을 이용하면 삽입한 순서대로 저장 순서를 보장할 수 있음.

 

class HashSetExample3 {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        set.add(new Person("Andy", 20));
        set.add(new Person("Andy", 20));
        set.add("test");
        set.add("test");
        // 같은 내용을 지닌 `Person`인스턴스 2개와 `String`인스턴스 2개를 요소로 추가함

        System.out.println(set);
    }
}

class Person {
    String name;
    int age;

    Person (String name, int age) {
        this.name = name;
        this.age = age;
    }

    public boolean equals(Object obj) {
        if (obj instanceof Person) {
                Person tmp = (Person) obj;
                return name.equals(tmp.name) && age == tmp.age;
        }
        return false;
    }

    public int hashCode() {
        return (name + age).hashCode();
    }

    public String toString() {
        return name + "(" + age + ")";
    }
}

객체 요소들을 추가할 때, HashSet은 해당 객체가 지닌 equals()와 hashCode()를 호출해서 일치 여부를 판단한 후, 중복을 제거하여 추가함.

String은 값이 같으면 equals()가 true를 반환하고, hashCode()도 동일한 hash code를 반환하기 때문에, 두 번 추가했더라도 하나만 들어가게 됨.

Person에서도 String처럼 equals()와 hashCode()를 적절히 오버라이딩해서 멤버변수의 값이 같으면, 동일한 객체로 취급하게끔 만듦. 따라서 같은 내용의 Person을 두 번 추가했어도 실제로는 하나의 객체만 요소로 들어갔음.

만약 오버라이딩을 하지 않았다면, 두 객체는 멤버 변수의 일치 여부와 관계 없이 서로 다른 객체로 인식되어 HashSet에 중복 저장되었을 것임.

 

🛠 [TIP] hashCode()를 오버라이딩 할 때는 아래와 같이 Objects 클래스의 hash 메서드를 사용하는 것이 바람직함.

public int hashCode() {
   return Objects.hash(name, age);
}

(Person 클래스에서 오버라이딩한 방식은 편의상 String의 hashCode() 방식에 따라 작성한 것임)

🛠 [TIP] hashCode()를 오버라이딩할 때 지켜야 할 조건

1. 동일 런타임 안에서 어떤 객체에 대해 hashCode()를 반복적으로 호출했을 때, 동일한 hash code를 반환해야함.

   equals() 메서드에서 참고하는 멤버 변수의 값이 바뀌지 않았다는 전제 하에 두 객체가 동일한 값을 가지기만 하면 됨.

2. equals() 메서드로 비교하여 true를 얻은 두 객체는 hashCode() 메서드가 동일한 hash code를 반환해야함.

3. equals() 메서드로 비교하여 false를 얻은 두 객체가 hashCode() 메서드로 반드시 다른 hash code를 반환받아야하는 것은 아님.

   서로 다른 객체끼리 hash code 값이 겹쳐도 상관은 없으나, HashMap이나 Hashtable처럼 hash code를 사용하는 컬렉션의 성능(검색 속도)을 높이려면 값이 겹치지 않도록 설계해야 함.

 

TreeSet

이진 검색 트리(Binary Search Tree)의 일종인 Red-Black Tree라는 자료구조를 가진 컬렉션 클래스.

💡 이진 검색 트리

• 여러개의 node가 연결된 구조로서, 하나의 노드에 최대 2개의 노드를 연결

• 하나의 root node로부터 밑으로 가지를 뻗어나감

  (상대적으로 위에 있는 node가 부모, 밑에 있는 node가 자식)

• 왼쪽 자식 node는 부모보다 작은 값, 오른쪽 자식 node는 부모보다 큰 값을 저장

• 왼쪽 마지막 node가 트리의 최소값, 오른쪽 마지막 node가 트리의 최대값이 됨

• 왼쪽 마지막 node부터 시작하여 오른쪽 마지막 node까지

  "왼쪽 node → 부모 node → 오른쪽 node" 순으로 읽으면 오름차순으로 읽을 수 있음.

  이렇게 정형화된 저장 형태를 유지하기 때문에 데이터의 추가/삭제 속도가 느리지만, 검색과 정렬 속도는 빠름.

 

TreeSet에 새 객체를 저장할 때, 이진 검색 트리의 저장 원칙에 의해 기존 node와 대소비교를 해야 하는데

1. 해당 객체가 Comparable을 구현을 하거나,

2. TreeSet에게 별도의 Comparator를 제공해서 비교 방식을 알려줘야만 함.

 

class TreeSetExample {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();

        set.add(5);
        set.add(1);
        set.add(3);
        set.add(4);
        set.add(2);

        System.out.println(set); // [1, 2, 3, 4, 5]
    }
}

Collections.sort()를 호출해 따로 정렬하지 않았는데도 이진 검색 트리에 의해 자동적으로 오름차순 정렬되어 저장됨.

 

class TreeSetExample {
    public static void main(String[] args) {
        String[] strArr = {"apple", "Watermelon", "grape", "banana", "Tangerine", "orange", "tomato"};

        TreeSet set = new TreeSet(Arrays.asList(strArr));

        System.out.println(set); // [Tangerine, Watermelon, apple, banana, grape, orange, tomato]
        System.out.println(set.subSet("b", "t")); // [banana, grape, orange]
        System.out.println(set.subSet("b", "t" + "zzz")); // [banana, grape, orange, tomato]
    }
}

문자열의 경우 대문자가 소문자보다 우선하고, 알파벳 순으로 자동 정렬됨.

TreeSet 내에 저장할 데이터의 대소문자를 통일하거나, 부득이 섞어야할 경우엔 별도의 Comparator를 제시해주는 것이 좋음

subSet()으로 특정 구간의 문자열을 모두 얻고자 할 때, 제시된 끝범위는 포함이 안됨.

이 때 끝범위에 "zzz"와 같은 문자열을 더해주면 끝범위가 포함된 문자열도 모두 얻을 수 있음

예시로 보면, 알파벳 순서상 "t"로 시작하면서 "tzzz" 보다 뒤에 올 단어는 없기 때문.

 

class TreeSetExample {
    public static void main(String[] args) {
        Integer[] numArr = {7, 5, 3, 4, 9, 1, 8, 2, 6, 0};
        TreeSet set = new TreeSet(Arrays.asList(numArr));

        System.out.println(set.headSet(6)); // [0, 1, 2, 3, 4, 5]
        System.out.println(set.tailSet(6)); // [6, 7, 8, 9]
    }
}

사실상 headSet()은 기준 node의 왼쪽 아래의 모든 node를 담고 있고,

tailSet()은 headSet()이 포함한 node를 제외한 모든 node를 담고 있음.

 

HashMap과 Hashtable

key-value 쌍으로 데이터(entry)를 저장함.

HashMap 안에 Entry라는 내부 클래스를 정의하여 key와 value를 멤버변수로 담고, 전체 데이터는 Entry[]로 표현함.

hashing을 사용하기 때문에 대량 데이터 검색에 좋은 성능을 가짐.

Hashtable은 HashMap의 구버전으로 레거시 취급. HashMap 사용이 권장됨

 

key는 Object 타입이긴 하나, 보통은 String을 많이 사용함.

key는 고유해야하며, 하나의 key는 반드시 하나의 value로 이어져야함.

만약 같은 key에 대해 여러번 value를 저장하면, 덮어씌워져서 마지막으로 저장한 value만 유효함.

HashMap hm = new HashMap();
hm.put("hello", 777);
hm.put("hello", "bye");
hm.put("hello", 123);

System.out.println(hm.get("hello")); // 123
System.out.println(hm); // {hello=123}

 

HashMap에서 쓰이는 key와 value는 모두 Object 타입이므로 value에 또 다른 HashMap을 넣어 grouping을 할 수 있음.

class HashMapExample {
    static HashMap developers = new HashMap();

    public static void main(String[] args) {
        addDeveloper("andy123", "Andy", "Back-End");
        addDeveloper("michelle123", "Michelle", "Front-End");
        addDeveloper("james123", "James", "Dev-Ops");
        addDeveloper("clara123", "Clara", "Back-End");
        addDeveloper("dan123", "Dan", "Back-End");
        addDeveloper("jimmy123", "Jimmy", "Front-End");

        printAll();
    }

    static void addDeveloper(String githubAccount, String name, String position) {
        addPosition(position);
        HashMap positionGroup = (HashMap) developers.get(position); // position 이름의 그룹 접근
        positionGroup.put(githubAccount, name); // 해당 position 그룹에 사람 추가
    }

    static void addPosition(String position) {
        if (!developers.containsKey(position)) {
            developers.put(position, new HashMap()); // position 이름으로 새로운 developer 그룹 생성
        }
    }

    static void printAll() {
        Set positionSet = developers.entrySet(); // 모든 position 그룹을 Set에 담음
        Iterator positionIt = positionSet.iterator();

        while (positionIt.hasNext()) {
            Map.Entry positionEntry = (Map.Entry) positionIt.next(); // Iterator로 각 position을 순회

            Set developerSet = ((HashMap) positionEntry.getValue()).entrySet(); // 각 position 내의 모든 developer들을 Set에 담음
            Iterator developerIt = developerSet.iterator();

            System.out.println(positionEntry.getKey() + " (" + developerSet.size() + ")");

            while (developerIt.hasNext()) {
                Map.Entry developerEntry = (Map.Entry) developerIt.next(); // Iterator로 position 내의 각 developer 순회

                System.out.println(developerEntry.getValue() + " (" + developerEntry.getKey() + ")");
            }
            System.out.println();
        }
    }
}

positionGroup에는 동명이인으로 중복 key가 발생할 수 있는 name 대신, 항상 고유한 값인 githubAccount를 key로 지정함.

실행 결과)

Back-End (3)
Clara (clara123)
Andy (andy123)
Dan (dan123)

Front-End (2)
Michelle (michelle123)
Jimmy (jimmy123)

Dev-Ops (1)
James (james123)

 

해싱과 해시함수

해싱(hashing)이란 해시 함수(hash function)를 사용해 key-value 쌍의 데이터를 HashSet, HashMap, Hashtable 등에 저장하고 검색하는 기법.

hashing에는 배열과 linked list가 조합된 자료 구조 사용.

 

key 값이 주어지면 해시 함수의 알고리즘을 거쳐 배열의 index가 반환됨.

key → (해시 함수) → index

 

배열의 각 원소는 linked list와 연결되어있는 매개체의 역할만 하고, 실제 데이터는 linked list 안에 저장됨

index → (배열에서 index에 해당하는 요소 검색) → 배열 요소 → linked list

 

linked list는 크기가 크면 클수록 검색에 불리해지기 때문에

이상적인 검색 속도를 가지려면 배열의 요소에 연결된 linked list도 하나의 요소, 즉 단일 데이터만 갖고 있어야함.

 

이는 특정 key에 대해 해시 함수가 반환하는 index 값이 중복되지 않아야 가능한 시나리오이므로,

서로 다른 key에 대해 index 값이 같아버리면 배열 요소에 연결된 linked list에 여러 개의 데이터가 들어가게 되기 때문.

결국 해시 함수의 알고리즘이 얼마나 정교한지(최대한 중복되지 않는 index를 반환)가 관건.

실제로 HashMap처럼 hashing을 하는 컬렉션 클래스는 Object 클래스의 hashCode()를 해시 함수로 사용하므로 준수한 성능을 보임.

hashCode()는 객체의 주소값을 이용해서 hash code를 반환하기 때문에 반환값의 고유성이 보장됨.

 

TreeMap

key-value 쌍의 데이터를 이진 검색 트리 형태로 저장. (정확히는 Red-Black Tree)

검색과 정렬에 적합

단순 검색은 HashMap이 성능이 더 높지만, 범위 검색이나 정렬은 TreeMap의 성능이 더 높음.

 

class TreeMapExample {
    public static void main(String[] args) {
        String[] keys = {"B", "C", "C", "A", "B", "B", "C", "A", "C", "B", "C", "B", "B", "B", "A", "B", "B", "B"};
        TreeMap tm = new TreeMap();

        for (int i = 0; i < keys.length; i++) {
            if (tm.containsKey(keys[i])) {
                Integer count = (Integer) tm.get(keys[i]);
                tm.put(keys[i], count + 1);
            } else {
                tm.put(keys[i], 1);
            }
        }

        Iterator it = tm.entrySet().iterator();

        System.out.println("----- 기본 정렬 -----");
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            int frequency = (Integer) entry.getValue();
            System.out.println(entry.getKey() + ": " + generateBar('#', frequency) + " (" + frequency + ")");
        }
    }

    public static String generateBar (char symbol, int frequency) {
            char[] bar = new char[frequency];

            for (int i = 0; i < bar.length; i++) {
                bar[i] = symbol;
            }

            return new String(bar);
    }
}

실행 결과)

----- 기본 정렬 -----
A: ### (3)
B: ########## (10)
C: ##### (5)

별도의 정렬을 한 것도 아닌데 key가 오름차순으로 정렬되어 저장되었음.

key가 String이므로, TreeSet 클래스가 String의 기본 정렬 기준에 의해 자동 정렬을 시킨 것.

만약 다른 정렬 기준으로 저장하길 원한다면, Comparator를 구현한 내부 클래스를 만들고 그 인스턴스를 가지고서 Collections.sort() 메서드를 사용하면 됨.

class TreeMapExample2 {
    public static void main(String[] args) {
        // ...중복 코드 생략
        List list = new ArrayList(tm.entrySet());
        Collections.sort(list, new DescendingFrequency());

        Iterator it = list.iterator();

        System.out.println("----- frequency 내림차순 정렬 -----");
        while (it.hasNext()) {
            Map.Entry entry = (Map.Entry) it.next();
            int frequency = (Integer) entry.getValue();
            System.out.println(entry.getKey() + ": " + generateBar('#', frequency) + " (" + frequency + ")");
        }
    }

    static class DescendingFrequency implements Comparator {
        public int compare(Object o1, Object o2) {
            if (o1 instanceof Map.Entry && o2 instanceof Map.Entry) {
                int v1 = (Integer)((Map.Entry) o1).getValue();
                int v2 = (Integer)((Map.Entry) o2).getValue();

                return v2 - v1;
            }
            return -1;
        }
    }

    public static String generateBar (char symbol, int frequency) {
        // ...중복 코드 생략
    }
}

실행 결과)

----- frequency 내림차순 정렬 -----
B: ########## (10)
C: ##### (5)
A: ### (3)

 

Properties

Hashtable을 상속받아 구현한 클래스.

Hashtable은 key와 value를 각각 Object 타입으로 저장하지만, Properties는 String 타입으로만 저장함.

주로 환경 설정 속성(property)를 저장하는데에 사용.

파일로부터 데이터를 읽고 쓸 수 있는 유용한 메서드를 제공함.

 

class PropertiesExample {
    public static void main(String[] args) {
            Properties props = new Properties();

            props.setProperty("Language", "EN");
            props.setProperty("Subtitle", "KR");
            props.setProperty("Volume", "15");
            props.setProperty("Brightness", "5");

            Enumeration e = props.propertyNames();

            while (e.hasMoreElements()) {
                String element = (String) e.nextElement();
                System.out.println(element + ": " + props.getProperty(element));
            }

            props.setProperty("Volume", "30");
            props.list(System.out); // -- listing properties -- 로 시작하는 전체 목록 출력
    }
}

실행 결과)

Language: EN
Brightness: 5
Subtitle: KR
Volume: 15
-- listing properties --
Subtitle=KR
Language=EN
Volume=30
Brightness=5

Hashtable의 자손답게 저장 순서가 유지되지 않음.

Properties는 컬렉션 프레임웍이 등장하기 전에 나왔으므로, Iterator 대신 Enumeration을 사용

 

class PropertiesExample2 {
    public static void main(String[] args) {
        Properties props = new Properties();
        String inputFile = args[0];

        try {
            props.load(new FileInputStream(inputFile));
        } catch (IOException e) {
            System.out.println("파일을 찾을 수 없습니다.");
            System.exit(0);
        }

        props.list(System.out);
    }
}

data.txt

#Properties example
Subtitle=KR
Language=EN
Volume=15
Brightness=5

실행 결과)

-- listing properties --
Subtitle=KR
Language=EN
Volume=15
Brightness=5

data.txt라는 파일을 command line argument 로 넘기고 해당 파일을 읽어와 Properties에 담은 뒤 출력함.

이처럼 외부 파일로부터 데이터를 입력받는 것도 가능함.

📌 외부 파일의 양식 조건

1. line 단위로 key와 value가 =로 연결된 형태

2. 주석은 #로 시작

반대로, store()나 storeToXML() 메서드와 함께 FileOutputStream()을 사용하면 코드 상에서 작성한 Properties 데이터를 외부 파일로 저장할 수 있음

 

Collections

컬렉션과 관련된 메서드를 제공하는 클래스.

📌 Collection 인터페이스와 혼동 주의

 

동기화되는 컬렉션 만들기

멀티 쓰레드 프로그래밍을 할 때, 여러 개의 쓰레드가 하나의 객체에 동시에 접근한다면 데이터의 일관성을 지키기 위해 객체를 동기화시켜야 함.

Vector, Hashtable 같은 오래된 클래스들은 자체적으로 동기화 처리를 하는데, 문제는 멀티 쓰레드 프로그래밍을 하지 않는 경우에도 동기화를 해서 성능이 떨어지게 됨.

컬렉션 프레임웍의 클래스들은 이런 단점을 보완해서 필요한 경우에만 Collections의 동기화 메서드를 활용해 동기화를 할 수 있게함.

 

동기화 메서드는 이름이 synchronized로 시작하며, 컬렉션 타입에 맞게 사용하면 됨.

List syncList = Collections.synchronizedList(new ArrayList());

 

변경 불가 컬렉션 만들기

데이터 보호를 위해 컬렉션을 읽기 전용으로 만들 때 쓰임.

주로 멀티 쓰레드 프로그래밍 시, 다수의 쓰레드에 의해 하나의 객체가 공유될 때 데이터가 손실되는 것을 방지하기 위함.

 

이름이 unmodifiable로 시작하는 메서드를 컬렉션 타입에 맞게 사용하면 됨.

Map readOnlyMap = Collections.unmodifiableMap(new HashMap());

 

싱글톤 컬렉션 만들기

단 하나만의 객체를 저장하는 컬렉션을 만들 때 사용.

생성된 싱글톤 컬렉션은 변경할 수 없음 (immutable)

이름이 singleton으로 시작하는 메서드를 컬렉션 타입에 맞게 사용하면 됨.

List sList = Collections.singletonList("soleElement");

 

한 종류의 객체만 저장하는 컬렉션 만들기

이름이 checked로 시작하는 메서드를 컬렉션 타입에 맞게 사용하면 됨.

제네릭(generic)과 같은 기능을 하는데, checked~()는 제네릭이 나오기 전인 JDK 1.5부터 도입되었으므로 레거시 호환 차원에서 제공하는 메서드라고 보면 됨.

두번째 매개변수에는 저장할 객체의 클래스를 지정.

List list = new ArrayList();
List cList = Collections.checkedList(list, Integer.class); // Integer 객체만 저장 가능
cList.add("hello"); // ClassCastException 발생

.class: 클래스 리터럴. 런타임에 해당 클래스를 대표하는 객체로 쓰임.

주로 인스턴스 생성이 불가한 클래스인 경우에 사용함.

인스턴스 생성이 가능한 클래스인 경우, .class 객체는 인스턴스에 getClass() 메서드를 사용해 반환 받는 객체와 동일함.