이것이 자바다 정리 #15 컬렉션 프레임워크

이것이 자바다 정리 #15 컬렉션 프레임워크

이것이 자바다 책을 참고하였습니다.

컬렉션(Collection) 프레임워크란?

다수의 객체를 저장하고 효율적으로 추가, 삭제, 검색할 수 있도록 구현된 인터페이스와 클래스들을 말한다.

주요 인터페이스로 List, Set, Map이 있다.

배열도 다수의 객체를 저장할 수 있다. 하지만, 저장할 수 있는 크기가 고정적이며, 중간 인덱스의 자료를 삭제했을 때 빈 곳이 생기기도 한다. 이로 인해 고정적 크기의 연속된 객체를 저장하는 것은 좋지만, 유동적인 크기를 갖는 객체 저장에는 적합하지 않을 수 있다.

컬렉션이란? 사전적 의미로 요소를 수집해서 저장하는 것을 말한다.

List

특징

• 순서를 유지하고 저장한다.
• 중복 저장이 가능하다.

구현 클래스

• ArrayList
• Vector (Thread safe)
• LinkedList

Set

특징

• 순서를 유지하지 않고 저장한다.
• 중복 저장이 불가능하다.

구현 클래스

• HashSet
• TreeSet (Binary Tree)

Map

특징

• 키와 값의 쌍으로 저장됨
• 키는 중복 저장 안됨

구현 클래스

• HashMap
• HashTable (Thread safe)
• TreeMap (Binary Tree)
• Properties (Child of HashTable)

List 컬렉션

• 객체를 인덱스로 관리한다.
  • 인덱스는 자동 부여된다.
  • 인덱스로 객체를 검색, 삭제하는 기능을 제공한다.
• 객체 자체를 저장하는 것이 아니라 각 인덱스에 객체의 주소를 저장한다.
• ArrayList, Vector, LinkedList등이 있다.

추상 메소드

객체 추가

• boolean add(E e): 주어진 객체를 맨 끝에 추가한다.
• void add(int index E element): 주어진 인덱스에 객체를 추가한다.
• E set(int index, E element): 주어진 인덱스에 있는 저장된 객체를 주어진 객체로 바꾼다.

객체 검색

• boolean contains(Object o): 주어진 객체가 저장되어 있는지 여부를 확인한다.
• E get(int index): 주어진 인덱스에 저장된 객체를 리턴한다.
• boolean isEmpty(): 컬렉션이 비어있는지 조사한다.
• int size(): 저장되어 있는 전체 객체의 수를 반환한다.

객체 삭제

• void clear(): 저장된 모든 객체를 삭제한다.
• E remove(int index): 주어진 인덱스에 저장되어 있는 객체를 삭제한다.
• boolean remove(Object o): 주어진 객체를 삭제한다.

ArrayList 구현체

• new ArrayList<T>()처럼 생성자로 생성이 가능하다.
  • 초기 용량은 10이다.
  • 자바 5 이후부터 제네릭 타입을 사용했다.
• 용량이 늘어나는 유연한 배열로 생각하면 된다.
  • 인덱스 0부터 차례로 객체가 저장된다.

리스트 중간에 데이터를 추가, 삭제하는 경우, 해당 인덱스를 기준으로 데이터가 밀려나거나 당겨지는 현상이 일어난다. 중간 데이터가 삭제되거나 추가되는 일이 많은 경우, LinkedList를 사용하면 성능상의 이득을 볼 수 있다.
그러나 인덱스 검색이 일어날 시, 혹은 맨 마지막에만 데이터가 추가되는 경우에는 ArrayList가 유리하다.

Array.asList(T... a)

Array.asList(T... a) 메소드는 배열을 리스트로 만들 때 용이하다. 해당 메소드의 인자 값에 배열을 주면 해당 데이터를 가지는 ArrayList가 반환된다.

public class AsListTest {
    public static void main(String[] args) {
        List<Integer> integerList = Arrays.asList(new Integer[]{1, 2, 3, 4}); // 혹은 Arrays.asList(1, 2, 3, 4);

        for (Integer integer : integerList) {
            System.out.println("integer = " + integer);
        }
    }
}

내부 구현을 보면, new ArrayList<>(a)의 결과를 반환하는 것을 볼 수 있다.

Vector 구현체

• 기본적으로 ArrayList와 동일한 내부 구조를 갖는다.
• 유일한 차이점은 스레드 환경에서 안전하게 객체를 추가, 삭제할 수 있다는 것이다.
  • 이러한 특성을 Thread Safe 하다고 한다.
  • 동기화된(synchronized) 메소드로 구성되어 있기 때문에 가능하다.

LinkedList 구현체

• ArrayList와 다르게 내부 배열에 객체를 저장해서 인덱스로 관리하는 것이 아니라, 인접 참조를 링크해서 체인처럼 관리한다.
• 중간 인덱스의 데이터를 제거하거나 추가할 때, 앞 뒤 링크만 변경되고 나머지 링크는 변경되지 않는다.
  • 이러한 이유 때문에 중간 인덱스에서 잦은 추가, 삭제가 일어날 때는 LinkedList 구현체가 유리하다.

성능 테스트 결과

public class LinkedListPerformanceTest {
    public static void main(String[] args) {
        List<String> arrayList = new ArrayList<>();
        List<String> linkedList = new LinkedList<>();

        long startTime;
        long endTime;
        long result;

        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            arrayList.add(0, "테스트 문자열");
        }
        endTime = System.nanoTime();
        result = endTime - startTime;
        System.out.println("result = " + result); // 소요시간: 355540900 나노초

        startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(0, "테스트 문자열");
        }
        endTime = System.nanoTime();
        result = endTime - startTime;
        System.out.println("result = " + result); // 소요시간: 5242300 나노초
    }
}

10만번 루프 기준으로 약 67배의 성능 차이가 나는 것을 확인했다.

Set 컬렉션

• 중복 데이터가 저장되지 않는다.
• 순서를 보장하지 않는다.
• HashSet, LinkedSet, TreeSet 등이 있다.
• 인덱스를 관리하지 않기 때문에, 인덱스를 매개값으로 갖는 메소드가 없다.

추상 메소드

객체 추가

• boolean add(E e): 주어진 객체를 저장한다. 성공 true 실패 false

객체 검색

• boolean contains(Object o): 주어진 객체가 저장되어있는지 확인한다.
• boolean isEmpty(): 컬렉션이 비어있는지 조사한다.
• Iterator<E> iterator(): 저장된 객체를 한번씩 가져오는 반복자(Iterator 객체)를 반환한다.
• int size(): 저장되어 있는 전체 객체 수를 리턴한다.

Set 컬렉션에는 인덱스로 객체를 검색하여 가져오는 메소드가 없다. 대신 Iterator객체를 반환하는 메소드가 있고, Iterator 객체에서는 hasNext(), next(), remove()를 제공한다.

단순 반복을 하고 싶다면 Iterator를 쓰지 않고 향상된 for문을 이용한 조회도 가능하다.
for(E element : set) { ... }

객체 삭제

• void clear(): 저장된 모든 객체를 삭제한다.
• boolean remove(Object o): 주어진 객체를 삭제한다.

HashSet

HashSet은 동일 객체를 판단할 때, hashCode() 메소드를 통해 해시 코드를 얻어낸 뒤에 이미 저장된 객체들의 해시코드와 비교하고, 동일한 해시코드가 있다면, equals() 메소드로 두 객체를 비교해서 true가 나오면 마침내 동일한 객체로 판단한다.

예제 코드

• Person 객체

public class Person {
    private String name;
    public int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public boolean equals(Object o) {
        System.out.println("equals method called");

        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        System.out.println("hashCode method called");

        return Objects.hash(name, age);
    }
}

• main 함수

public class HashSetTest {
    public static void main(String[] args) {
        Person person1 = new Person("제이크", 30);
        Person person2 = new Person("제이크", 30);

        System.out.println("person1 = " + System.identityHashCode(person1));
        System.out.println("person2 = " + System.identityHashCode(person2));
        System.out.println(person1 == person2);

        Set<Person> personSet = new HashSet<>();

        personSet.add(person1);
        personSet.add(person2);

        int size = personSet.size();
        System.out.println("size = " + size);
    }
}

• 결과

비록 두 개의 객체가 다른 identityHashCode를 갖고 있지만, .hashCode() 메소드의 결과가 같고 .equals() 메소드의 결과가 true라서 둘은 HashSet 내부에서 같은 값이라고 인식된다.

Map 컬렉션

• Map 컬렉션은 키(key)와 값(value)로 구성된 Entry 객체를 저장하는 구조를 가지고 있다.
• 키, 값은 모두 객체이다.
• 키는 중복이 안되며, 값은 중복이 된다.
• HashMap, HashTable, LinkedHashMap, Properties, TreeMap 등이 있다.

추상 메소드

객체 추가

• V put(K key, V value): 주어진 키로 값을 저장한다. 새로운 키일 경우 null을 리턴하고, 이전에 있던 키에 새로운 값을 덮어 씌우는 경우 이전에 있던 값을 리턴한다.

객체 검색

• boolean containsKey(Object key): 주어진 키가 있는지 여부를 파악한다.
• boolean containsValue(Object value): 주어진 값이 있는지 여부를 파악한다.
• Set<Map.Entry<K, V>> entrySet(): 키와 값의 쌍으로 구성된 모든 Map.Entry 객체를 Set에 담아서 반환한다.
• V get(Object key): 주어진 키가 있는 값을 리턴한다.
• boolean isEmpty(): 컬렉션이 비어있는지 여부를 확인한다.
• Set<K> keySet(): 모든 키를 Set 객체에 담아서 리턴한다.
• int size(): 저장된 키의 총 수를 리턴한다.
• Collection<V> values(): 저장된 모든 값을 Collection에 담아서 리턴한다.

객체 삭제

• void clear(): 모든 Map.Entry 객체를 삭제한다.
• V remove(Object key): 주어진 키와 일치하는 Map.Entry를 삭제하고 값을 반환한다.

반복 방법

• ketSet() 메소드로 모든 키의 Set을 얻고 .get() 메소드로 모든 키를 조회해보면 된다.
• .entrySet() 메소드로 모든 Map.Entry의 Set을 얻고 .iterator() 메소드를 통해서 반복자(Iterator)를 얻은 후 돌려보면 된다.

HashMap

• 키 타입의 객체가 있다면, hashCode()와 equals() 메소드를 둘 다 확인 후에 같은 객체라고 판단한다.
• 키와 값은 primitive type이 올 수 없다.
  • 아마 .hashCode(), .equals()등의 메소드가 없기 때문?

HashTable

• HashMap과 동일한 내부구조를 갖고 있다.
• 동기화된 (synchronized) 메소드를 갖고 있어서, 멀티 스레드 환경에서 안전하게 객체를 추가, 삭제 가능하다. (thread safe)

Properties

• HashTable의 하위 클래스이다.
• 키와 값을 String이라는 타입으로만 제한한 클래스이다.
• 보통 애플리케이션의 옵션 정보, 데이터베이스 연결 정보, 다국어 정보 등이 저장된 프로퍼티 파일(.properties)을 읽을 때 주로 사용한다.
  • 프로퍼티 파일(.properties)은 키와 값이 =기호로 연결된 텍스트 파일로 ISO-8859-1 문자셋으로 저장된다. 이 문자셋으로 저장할 수 없는 한글은 유니코드로 변환되어 저장된다.
• 프로퍼티 파일을 읽기 위해서는 Properties 객체를 생성 후에 .load() 메소드를 이용하면 된다. .load() 메소드는 프로퍼티 파일로부터 데이터를 읽기 위해 FileReader 객체를 매개값으로 받는다.

예제 코드

public class PropertiesTest {
    public static void main(String[] args) throws IOException {
        String encodedPath = PropertiesTest.class.getResource("../../config/my_properties.properties").getPath();
        System.out.println("encodedPath = " + encodedPath);

        String decodedPath = URLDecoder.decode(encodedPath, "utf-8");
        System.out.println("decodedPath = " + decodedPath);

        Properties properties = new Properties();
        properties.load(new FileReader(decodedPath));

        for (Map.Entry<Object, Object> propertyEntry : properties.entrySet()) {
            String key = (String) propertyEntry.getKey();
            String value = (String) propertyEntry.getValue();

            System.out.println("key = " + key + ", value = " + value);
        }
    }
}

• my_properties.properties 파일은 최상위 디렉토리의 config 디렉토리에 위치해 있다고 가정했다. 현재 클래스의 위치로부터 두 경로 상위로 가야하기 때문에 ../을 두번 적어서 경로를 맞춰주었다.
  • getPath()해서 나온 값은 한글 디코드가 안 되어있기 때문에, URLDecoder 클래스 내부에 있는 정적 메소드를 이용하여 디코드해주었다.
• 이후 Properties 객체를 생성하고, .load() 메소드를 통해 my_properties.properties 파일을 불러왔다.
• 기본적으로 Properties도 HashTable의 하위 클래스이기 때문에, Map 인터페이스에서 쓰던 추상 메소드들을 그대로 이용할 수 있다.
  • 사실 키에 대한 값을 얻을 때는 .getProperties()가 가장 흔히 쓰이는 메소드이다.
• Map.Entry 객체를 가져와 키와 값을 출력했다.

검색기능을 강화시킨 컬렉션

• TreeSet
• TreeMap

위 두 컬렉션은 이진트리(binary tree)를 이용해서 계층적 구조를 가지도록 객체를 저장한다.

이진 트리 구조란?

부모 자식 관계를 갖고 위에서 아래로 뻗어나가는 트리 구조인데, 특수한 특성을 띈 트리 구조이다. 트리 구조란 것은 그냥 상위 노드에 하위 노드가 붙어있는 형태이고, 상위에서 하위 데이터 접근이 가능하다. 보통 시작점인 루트 노드에 여러 자식노드가 붙으면서 시작된다.

위와 같이 루트노드로부터 시작되어 하위에 연결된 다른 노드들이 있는 구조이다. 위와 같은 트리 노드 구조에서 이진 트리는 아래와 같은 조건을 만족하는 트리 구조를 말한다.

이진트리의 조건

• 한 부모 노드의 자식 노드는 최대 2개까지만 붙는다.
• 부모 노드의 값보다 작은 자식은 왼쪽에 붙는다.
• 부모 노드의 값보다 큰 자식은 오른쪽에 붙는다.

이진 트리의 조건을 만족하면 다음과 같은 특성을 갖게 된다.

이진트리의 조건을 충족하면, 큰 값을 찾거나 작은 값을 찾기 매우 쉽다.

핵심은 데이터의 삽입, 삭제 등의 과정을 거쳤을 때도 규칙을 깨지 않고, 위와 같은 규칙을 지킴으로써 내가 원하는 데이터를 빠르게 검색하려는 데에 있다.

이진트리의 약점

• 단, 밸런스가 맞지 않을 수 있다.

위와 같은 노드가 있을 때, 위는 완벽히 밸런스가 맞진 않지만, 꽤나 밸런스가 맞는 이진트리이다. 하지만, 가장 큰 값을 찾으려 오른쪽 노드로 계속 향했을 때 나오는 값은 11이 아닌 9이다.

위와 같은 경우에도 검색을 빠르게 하려는 이진 트리의 목적에 위배되는 구조이다.

이진트리 약점 극복

이를 위해 TreeMap과 TreeSet은 이진트리에서 더 업그레이드된 레드-블랙 트리를 사용한다.

참고 링크: 레드블랙트리 정리

TreeSet

• 이진트리를 기반으로 한 Set 컬렉션이다.
• 객체 저장 시 자동으로 부모 값보다 낮은 값은 왼쪽 자식 노드에 높은 값은 오른쪽 자식 노드에 정렬된다.

TreeSet은 Set 인터페이스가 제공하는 메소드와 별개로 자신만의 메소드를 가지고 있으므로, TreeSet 타입으로 선언해야 할 때가 있다.

• first(): 제일 낮은 객체를 리턴
• last(): 제일 높은 객체를 리턴
• pollFirst() or pollLast(): 제일 높거나 낮은 객체를 꺼내오고 컬렉션에서 제거
• floor(E e) or ceiling(E e): 동등한 객체가 없다면 높은 혹은 동등한 객체가 없다면 낮은 객체를 가져옴 동등한 게 있으면 동등한 걸 가져옴

NevigableSet

• TreeSet의 데이터를 반환받을 때, TreeSet.descendingSet() 등의 메소드를 이용하면 NevigableSet을 반환받을 수 있다.
  • 정렬등에 유연하게 구성할 수 있는 Set이다.
    • NevigableSet에서 .descendingSet()을 한번 더 호출하면 오름차순으로 구성된다.

TreeMap

• 이진트리를 기반으로 한 Map 컬렉션이다.
• 키(key)와 값(value) 중에 키(key)를 기준으로 정렬한다.
• TreeSet처럼 .descendingKeySet() 이나 .descendingMap()을 통해 NavigableKeySet이나 NavigableMap을 얻을 수 있다.

Comparable과 Comparator

• TreeSet과 TreeMap은 정렬을 위해 java.lang.Comparable을 구현한 객체를 요구한다.
• 사용자 정의 클래스도 Comparable을 구현하면 자동 정렬이 된다.

Comparable을 상속하면, int compareTo(T o) 메소드를 구현해주면 된다.

• 주어진 객체보다 크면 1(양수)을 리턴
• 주어진 객체와 같으면 0을 리턴
• 주어진 객체보다 작으면 -1(음수)을 리턴

위의 규칙을 따르는 compareTo()를 작성하면 오름차순 정렬이 자동으로 된다.

테스트 작성해보기

public class Score {
    int math;
    int korean;
    int english;

    public Score(int math, int korean, int english) {
        this.math = math;
        this.korean = korean;
        this.english = english;
    }
    
    public int getSum() {
        return this.math + this.korean + this.english;
    }
}

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<Score, String> treeMap = new TreeMap<>();
        treeMap.put(new Score(10, 20, 30), "김똘삼등");
        treeMap.put(new Score(10, 25, 30), "김똘이등");
        treeMap.put(new Score(10, 30, 35), "김똘일등");

        Map.Entry<Score, String> firstEntry = treeMap.firstEntry();
        System.out.println("꼴찌는? = " + firstEntry.getKey().getSum() + "점, " + firstEntry.getValue());

        Map.Entry<Score, String> lastEntry = treeMap.lastEntry();
        System.out.println("일등은? = " + lastEntry.getKey().getSum() + "점, " + lastEntry.getValue());
    }
}

위와 같이 코드를 작성하고 결과를 확인하면... 아래와 같은 결과가 나온다.

class com.company.treemap.Score cannot be cast to class java.lang.Comparable

Comparable을 구현해서 나오지 않는 에러이다.

public class Score implements Comparable<Score>{
    int math;
    int korean;
    int english;

    public Score(int math, int korean, int english) {
        this.math = math;
        this.korean = korean;
        this.english = english;
    }

    public int getSum() {
        return this.math + this.korean + this.english;
    }

    @Override
    public int compareTo(Score o) {
        if(this.getSum() > o.getSum()) {
            return 1;
        } else if(this.getSum() == o.getSum()) {
            return 0;
        }
        return -1; // the same as return Integer.compare(this.getSum(), o.getSum());
    }
}

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<Score, String> treeMap = new TreeMap<>();
        treeMap.put(new Score(10, 20, 30), "김똘삼등");
        treeMap.put(new Score(10, 25, 30), "김똘이등");
        treeMap.put(new Score(10, 30, 35), "김똘일등");

        Map.Entry<Score, String> firstEntry = treeMap.firstEntry();
        System.out.println("꼴찌는? = " + firstEntry.getKey().getSum() + "점, " + firstEntry.getValue());

        Map.Entry<Score, String> lastEntry = treeMap.lastEntry();
        System.out.println("일등은? = " + lastEntry.getKey().getSum() + "점, " + lastEntry.getValue());
    }
}

위와 같이 Comparable<Score> 인터페이스를 구현하면 정상적으로 작동한다.

위와같이 compareTo()의 반환 값의 양수 음수를 스위칭하면 결과도 반대로 바뀐다.

동기화된 컬렉션 만들기

앞에 언급됐던 컬렉션 중 Vector와 HashTable은 동기화된 메소드로 구성되어 멀티스레드환경에서 안전하지만, ArrayList, HashSet, HashMap은 synchronized 메소드로 구성되지 않아 멀티 스레드 환경에서 안전하지 않다.

컬렉션을 Thread-safe 로 만드려면, Collections.synchronizedXxx() 메소드를 이용하면 된다.

병렬처리 컬렉션 만들기 (동기화 컬렉션의 한계)

동기화된 (synchronized) 컬렉션은 스레드 환경에서 안전은 보장하지만, 스레드가 하나의 요소를 처리할 때 잠금이 발생하기 때문에 대기시간이 발생하고 그래서 빠른 속도를 보장하진 못한다.

이러한 문제를 해결하기 위해 자바에서는 멀티 스레드가 컬렉션의 요소를 병렬적으로 처리할 수 있도록 특별한 컬렉션을 제공한다. ConcurrentHashMap과 ConcurrentLinkedQueue이다.

위 컬렉션은 부분(segment) 잠금을 이용하여, 처리하는 요소가 포함된 부분만 잠금하고 나머지 부분은 다른 스레드가 변경할 수 있도록 한다.

Map<K, V> map = new ConcurrentHashMap<K, V>();

Queue<E> queue = new ConcurrentLinkedQueue<E>();

ConcurrentLinkedQueue는 락-프리 알고리즘을 구현하여, 여러개의 스레드가 동시에 접근해도 잠금을 사용하지 않고 최소한 하나의 스레드가 안전하게 요소를 저장하거나 얻도록 해준다.