[Java] 컬렉션 프레임워크(Collections Framework)

JDK1.2부터 컬렉션 프레임워크가 등장하면서 다양한 종류의 컬렉션 클래스가 추가되고 모든 컬렉션 클래스를 표준화된 방식으로 다룰 수 있도록 체계화되었다.

 

컬렉션 프레임워크(Collections Framework)는 컬렉션, 다수의 데이터를 다루는 데 필요한 다양하고 풍부한 클래스들을 제공하기 때문에 프로그래머의 짐을 상당히 덜어 주고 있으며, 또한 인터페이스와 다형성을 이용한 객체지향적 설계를 통해 표준화되어 있기 때문에 사용법을 익히기에도 편리하고 재사용성이 높은 코드를 작성할 수 있다는 장점이 있다.

 

 

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

---

컬렉션 프레임워크에서는 컬렉션 데이터 그룹을 크게 3가지 타입이 존재한다고 인식하고 그 컬렉션을 다루는데 필요한 기능을 가진 3개의 인터페이스를 정의하였다. 인터페이스 List와 Set의 공통된 부분을 다시 뽑아서 새로운 인터페이스인 Collection을 추가로 정의하였다.

컬렉션 프레임워크의 핵심 인터페이스간의 상속계층도

Map인터페이스는 List와 Set과 전혀 다른 형태로 컬렉션을 다루기 때문에 Collection인터페이스로 정의하지 않는다.

 

List

• 순서가 있는 데이터의 집합
• 데이터의 중복 허용
• ArrayList, LinkedList, Stack, Vector 등

Set

• 순서를 유지하지 않는 데이터의 집합
• 데이터의 중복 허용하지 않음.
• HashSet, TreeSet 등

Map

• 키(Key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합
• 순서를 유지하지 않는 데이터의 집합
• 키(Key)는 중복을 허용하지 않고, 값(Value)은 중복을 허용한다.

Vector, Stack, Hashtable, Properties와 같은 클래스들은 컬렉션 프레임워크가 만들어지기 이전부터 존재하던 것이기 때문에 컬렉션 프레임워크의 명명법을 따르지 않는다.

 

Vector나 Hashtable과 같은 기존의 컬렉션 클래스들은 호환을 위해, 설계를 변경해서 남겨두었지만 가능하면 사용하지 않는 것이 좋다. 그 대신 새로 추가된 ArrayList와 HashMap을 사용하자.

 

Collection 인터페이스

List와 Set의 조상인 Collection인터페이스에는 다음과 같은 메서드들이 정의되어 있다.

Collection인터페이스에 정의된 메서드

Collection인터페이스는 컬렉션 클래스에 저장된 데이터를 읽고, 추가하고 삭제하는 등 컬렉션을 다루는데 가장 기본적인 메서드들을 정의하고 있다.

 

E는 특정 타입을 의미하는 것으로 지네릭스(Generics)에 의한 표기이다.

 

List인터페이스

• 순서가 있는 데이터의 집합
• 데이터의 중복 허용
• ArrayList, LinkedList, Stack, Vector 등

List의 상속계층도

List인터페이스의 메서드

 

Set인터페이스

• 순서를 유지하지 않는 데이터의 집합
• 데이터의 중복 허용하지 않음.
• HashSet, TreeSet 등

Set의 상속계층도

 

Map인터페이스

• 키(Key)와 값(value)의 쌍(pair)으로 이루어진 데이터의 집합
• 순서를 유지하지 않는 데이터의 집합
• 키(Key)는 중복을 허용하지 않고, 값(Value)은 중복을 허용한다.

Map의 상속계층도

Map인터페이스의 메서드

value()에서는 반환 타입이 Collection이고, keySet()에서는 반환 타입이 Set이다.

Map인터페이스에서 값(value)은 중복을 허용하기 때문에 Collection타입으로 반환하고, 키(key)는 중복을 허용하지 않기 때문에 Set타입으로 반환한다.

 

Map.Entry인터페이스

Map.Entry인터페이스는 Map인터페이스의 내부 인터페이스이다. 인터페이스도 내부 클래스처럼 내부 인터페이스를 정의하는 것이 가능하다.

 

Map 저장되는 key-value쌍을 다루기 위해 내부적으로 Entry인터페이스를 정의해놓았다. 이것은 보다 객체지향적으로 설계하도록 유도하기 위한 것으로 Map인터페이스를 구현하는 클래스에서는 Map.Entry인터페이스도 함께 구현해야 한다.

public interface Map<K,V> {
    ...
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        ...
    }
}

Map.entry인터페이스의 메서드

 

 

ArrayList

---

• 가장 많이 사용되는 컬렉션 클래스
• List인터페이스를 구현
• 순서가 있는 저장 순서 유지
• 데이터의 중복 허용

Java API ArrayList

 

ArrayList의 생성자와 메서드

출처. https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb

ArrayList나 Vector같이 배열을 이용한 자료구조는 데이터를 읽어오고 저장하는 데는 효율이 좋지만, 용량을 변경해야 할 때는 새로운 배열을 생성한 후 기존의 배열로부터 새로 생성된 배열로 데이터를 복사해야 하기 때문에 상당히 효율이 떨어진다는 단점을 가지고 있다. 그래서 처음에 인스턴스를 생성할 때, 저장할 데이터의 개수를 잘 고려하여 충분한 용량의 인스턴스를 생성하는 것이 좋다.

 

 

연결 리스트(LinkedList)

---

 배열의 단점

1. 크기를 변경할 수 없다.
   • 크기를 변경할 수 없으므로 새로운 배열을 생성해서 데이터를 복사해야 한다.
   • 실행 속도를 향상하기 위해서는 충분히 큰 크기의 배열을 생성해야 하므로 메모리가 낭비된다.
2. 비순차적인 데이터의 추가 또는 삭제에 시간이 많이 걸린다.
   • 차례대로 데이터를 추가하고 마지막에서부터 데이터를 삭제하는 것은 빠르지만,
   • 배열의 중간에 데이터를 추가하려면, 빈자리를 만들기 위해 다른 데이터들을 복사해서 이동해야 한다.

 

연결 리스트(LinkedList)는 불연속적으로 존재하는 데이터를 서로 연결(link) 한 형태로 구성되어 있다.

연결리스트(LinkedList)

연결 리스트의 각 요소(node)들은 자신과 연결된 다음 요소에 대한 참조(주소 값)와 데이터로 구성되어 있다.

class Node {
	Node next;		// 다음 요소의 주소를 저장
    Object obj;		// 데이터를 저장
}

 

LinkedList의 데이터 삭제

노드 A(삭제하려는 Node)의 전에 있는 Node가 A의 다음 Node를 참조하도록 하면 된다. 배열처럼 데이터를 이동하기 위해 복사하는 과정이 없기 때문에 처리속도가 매우 빠르다.

링크드 리스트에서의 데이터 삭제

 

LinkedList의 데이터 추가

추가하려는 요소를 다음 추가하고자 하는 위치의 이전 요소의 참조를 새로운 요소에 대한 참조로 변경해주고,

새로운 요소가 그다음 요소를 참조하도록 변경하기만 하면 되므로 처리속도가 매우 빠르다.

링크드 리스트에서의 데이터 추가

 

이중 연결 리스트(doubley linked list)

연결 리스트는 이동방향이 단방향이기 때문에 다음 요소에 대한 접근은 쉬지만 이전 요소에 대한 접근은 어렵다.

 

이중 연결 리스트(double linked list)는 단순히 링크드 리스트에 참조 변수를 하나 더 추가하여 다음 요소에 대한 참조뿐 아니라 이전 요소에 대한 참조가 가능하도록 했을 뿐, 그 외에는 링크드 리스트와 같다.

class Node {
	Node	next;		// 다음 요소의 주소
    Node	prev;		// 이전 요소의 주소
    Object	obj;		// 데이터
}

이중 연결 리스트의 장점은 각 요소에 대한 접근과 이동이 쉽다.

이중 연결리스트(double linked list)

이중 원형 연결 리스트(double circular linkedlist)

이중 원형 연결 리스트(double circular linkedlist)는 이중 연결 리스트의 첫 요소와 마지막 요소를 서로 연결시킨 것이다.

이중 원형 연결리스트(double circular linked list)

 

LinkedList의 생성자와 주요 메서드

ArrayList와 비슷한 메서드를 제외하고 주로 사용하는 메서드만 작성한다.

출처: https://catsbi.oopy.io/8f0f5192-3a06-405e-8076-dbc5ff9f2dfb

 

ArrayList vs LinkedList

순차적으로 추가/삭제하는 경우에는 ArrayList가 LinkedList보다 빠르다.

만약 ArrayList의 크기가 충분하지 않으면, 새로운 크기의 ArrayList를 생성하고 데이터를 복사하는 일이 발생하게 되므로 순차적으로 데이터를 추가해도 ArrayList보다 LinkedList가 더 빠를 수 있다.

중간 데이터를 추가/삭제하는 경우에는 LinkedList가 ArrayList보다 빠르다.

LinkedList는 각 요소 간의 연결만 변경해주면 되기 때문에 처리속도가 상당히 빠르다.

반면에 ArrayList는 각 요소들을 재배치하여 추가할 공간을 확보하거나 빈 공간을 채워야 하기 때문에 처리속도가 늦다.

 

데이터의 개수가 매우 크지 않다면 어느 것을 사용해도 큰 차이가 나지는 않는다.

그래도 ArrayList와 LinkedList의 장단점을 잘 이해하고 상황에 따라 적합한 것을 선택해서 사용하는 것이 좋다.

컬렉션	읽기(접근시간)	추가/삭제	비고
ArrayList	빠름	느림.	순차적인 추가삭제는 더 빠름. 비효율적인 메모리사용.
LinkedList	느림.	빠름.	데이터가 많을수록 접근성이 떨어짐.

작업하기 전에 데이터를 저장할 때는 ArrayList,

작업할 때는 LinkedList로 데이터를 옮겨서 작업하면 좋은 효율을 얻을 수 있을 것이다.

ArrayList al = new ArrayList(100000);
for(int i = 0; i<100000;i++) al.add(i+"");

LinkedList ll = new LinkedList(al);
for(int i = 0; i<1000;i++) ll.add(500, "X");

컬렉션 프레임워크에 속한 클래스들은 이처럼 서로 변환이 가능한 생성자를 제공하므로 간단히 다른 컬렉션 클래스로 데이터를 옮길 수 있다.

 

 

Stack과 Queue

---

• 스택(Stack) : 마지막에 저장한 데이터를 가장 먼저 꺼내는 LIFO(Last In First Out) 구조
  • class Stack<E>

Stack의 메서드

• 큐(Queue) : 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out) 구조
  • interface Queue<E>

Queue의 메서드

순차적으로 데이터를 추가하고 삭제하는 스택에는 ArrayList와 같은 배열 기반의 컬렉션 클래스가 적합하다.

 

큐는 데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로, ArrayList와 같은 배열 기반의 컬렉션 클래스를 사용한다면 데이터를 꺼낼 때마다 빈 공간을 채우기 위해 데이터의 복사가 발생하므로 비효율적이다.

그래서 큐는 ArrayList보다 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 더 적합하다.

 

자바에서는 스택을 Stack클래스로 구현하여 제공하고 있지만 큐는 Queue인터페이스로만 정의해 놓았을 뿐 별도의 클래스를 제공하고 있지 않다. 대신 Queue인터페이스를 구현한 클래스들이 있어서 이들 중의 하나를 선택해서 사용한다.

Stack st = new Stack();
Queue q = new LinkedList();		// Queue인터페이스의 구현체인 LinkedList를 사용

 

PrioirtyQueue

Queue인터페이스의 구현체 중의 하나로, 저장한 순서에 관계없이 우선순위(priority)가 높은 것부터 꺼내게 된다는 특징이 있다. 그리고 null은 저장할 수 없다. null을 저장하면 NullPointerException이 발생한다.

 

PriorityQueue는 저장공간으로 배열을 사용하며, 각 요소를 힙(heap)이라는 자료구조의 형태로 저장한다.

힙(heap)은 이진트리의 한 종류로 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있다는 특징이 있다.

import java.util.PriorityQueue;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        //Queue<Integer> pq = new PriorityQueue<Integer>();
        Queue pq = new PriorityQueue();

        pq.offer(3);    // pq.offer(new Integer(3)); 오토박싱
        pq.offer(1);
        pq.offer(5);
        pq.offer(2);
        pq.offer(4);
        System.out.println(pq); // pq의 내부 배열을 출력

        Object obj = null;
        Integer i = null;
        while ((obj = pq.poll()) !=null) {
            System.out.println(obj);
        }
        /*
        while ((i = (Integer) pq.poll()) !=null){
            System.out.println(i);
        }*/
    }
}

 

Deque(Double-Ended Queue)

Deque(덱)은 양 끝에서 추가/삭제가 가능하다.

Deque의 조상은 Queue이며, 구현체로 ArrayDeque와 LinkedList 등이 있다.

Deque

덱은 스택과 큐를 하나로 합쳐놓은 것과 같으며 스택으로 사용할 수도 있고, 큐로 사용할 수도 있다.

Deque	Queue	Stack
offerLast()	offer()	push()
pollLast()	-	pop()
pollFirst()	poll()	-
peekFirst()	peek()
peekLast()	-	peek()

 

 

Iterator, ListIterator, Enumeration

---

Iterator, ListIterator, Enumeration은 컬렉션에 저장된 요소를 접근하는 데 사용되는 인터페이스이다.

Enumeration은 Iterator의 구버전이라고 생각하면 된다. Enumeration대신 Iterator를 사용하자.

ListIterator는 Iterator의 기능을 향상 시킨 것이다. 

 

Iterator

컬렉션에 저장된 각 요소에 접근하는 기능을 가진 Iterator인터페이스를 정의하고, Collection인터페이스에는 Iterator를 반환하는 iterator()를 정의하고 있다.

public interface Iterator {
	boolean		hasNext();
    Object		next();
    void		remove();
}

public interface Collection {
	...
    public Iterator iterator();
    ...
}

iterator()는 Collection에 정의된 메서드이므로 Collection인터페이스의 자손인 List와 Set에도 포함되어 있다.

그래서 List나 Set인터페이스를 구현하는 컬렉션은 iterator()가 각 컬렉션의 특징에 맞게 작성되어 있다.

Iterator인터페이스의 메서드

보통 hasNext()는 next() 메서드를 호출하기 전에 다음 요소가 있는지 확인하기 위해 사용한다.

 

Collection c = new ArrayList();			//다른 컬렉션으로변경시 이 부분만 고치면 된다.
Iterator it = c.iterator();

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

ArrayList대신 Collection인터페이스를 구현한 다른 컬렉션 클래스에 대해서도 이와 동일한 코드를 사용할 수 있다.

 

Iterator를 이용해서 컬렉션의 요소를 읽어오는 방법을 표준화했기 때문에 이처럼 코드의 재사용성을 높이는 것이 가능한 것이다. 이처럼 공통 인터페이스를 정의해서 표준을 정의하고 구현하여 표준을 따르도록 함으로써 코드의 일관성을 유지하여 재사용성을 극대화하는 것이 객체지향 프로그래밍의 중요한 목적 중의 하나이다.

 

참조 변수의 타입을 ArrayList타입이 아니라 Collection타입으로 한 이유는?

Collection에는 없고 ArrayList에만 있는 메서드를 사용하는 게 아니라면, Collection타입의 참조 변수로 선언하는 것이 좋다. 만일 Collection인터페이스를 구현한 다른 클래스, 예를 들어 LinkedList로 바꿔야 한다면 선언문 하나만 변경하면 나머지 코드는 검토하지 않아도 된다. 참조 변수 타입이 Collection이므로 Collection에 정의되지 않은 메서드는 사용되지 않았을 것이 확실하기 때문이다. 그러나 참조 변수 타입을 ArrayList로 했다면, 선언문 이후의 문장들을 검토해야 한다. Collection에 정의되지 않은 메서드를 호출했을 수 있기 때문이다.

 

Map은 어떻게?

Map인터페이스는 키와 값을 쌍으로 저장하고 있기 때문에 iterator()를 직접 호출할 수 없고, 그 대신 keySet()이나 entrySet()과 같은 메서드를 통해서 키와 값을 각각 따로 Set의 형태로 얻어 온 후에 다시 iterator()를 호출해야 한다.

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

 

ListIterator

Iterator는 단방향으로만 이동할 수 있는 데 반해 ListIterator는 양방향으로서의 이동이 가능하다.

다만, ArrayList나 LinkedList와 같이 List인터페이스를 구현한 컬렉션에서만 사용할 수 있다.

ListIterator의 메서드

import java.util.ArrayList;
import java.util.ListIterator;

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

        ListIterator it = list.listIterator();

        while (it.hasNext()) {
            System.out.println(it.next());      // 순방향
        }
        System.out.println();

        while (it.hasPrevious()) {
            System.out.println(it.previous());  // 역방향
        }
        System.out.println();

    }
}

--------실행 결과---------
1
2
3
4
4

4
4
3
2
1

이동하기 전에 반드시 hasNext()나 hasPreveious()를 호출해서 이동할 수 있는지 확인해야 한다.

 

 

Arrays

---

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

 

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

• copy() : 배열 전체를 복사해서 새로운 배열을 만들어 반환
• copyOfRange() : 배열의 일부를 복사해서 새로운 배열을 만들어 반환

int[] arr = {0,1,2,3,4};
int[] arr2 = Arrays.copyOf(arr, arr.length);    // arr2 = [0,1,2,3,4,]
int[] arr3 = Arrays.copyOf(arr, 3);             // arr3 = [0,1,2]
int[] arr4 = Arrays.copyOf(arr, 7);             // arr4 = [0,1,2,3,4,0,0] 
int[] arr5 = Arrays.copyOfRange(arr, 2, 4);     // arr5 = [2,3]
int[] arr6 = Arrays.copyOfRange(arr, 0, 7);     // arr6 = [0,1,2,3,4,0,0]

 

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

• fill() : 배열의 모든 요소를 지정된 값으로 채운다.
• setAll() : 배열을 채우는 데 사용할 함수형 인터페이스를 매개변수로 받는다.
  이 메서드를 호출할 때는 함수형 인터페이스를 구현한 객체를 매개변수로 지정 또는 람다식을 지정해야 한다.

int[] arr = new int[5];
Arrays.fill(arr, 9);    // arr = [9,9,9,9,9];
System.out.println(Arrays.toString(arr));
Arrays.setAll(arr, (index)->(int)(Math.random()*5) + 1 + index);
System.out.println(Arrays.toString(arr));

 

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

• sort() : 배열을 정렬
• binarySearch() : 배열에 저장된 요소의 위치 검색
  • 반드시 배열이 정렬되어 있어야 올바른 결과를 얻는다.
  • 검색한 값과 일치하는 요소가 여러 개 있다면, 어떤 것의 위치가 반환될지 알 수 없다.

int[] arr = {3, 2, 0, 1, 4};
int idx = Arrays.binarySearch(arr, 2);

System.out.println(idx);
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
int idx2 = Arrays.binarySearch(arr, 2);
System.out.println(idx2);

---------실행 결과----------
-5
[0, 1, 2, 3, 4]
2

 

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

toString()은 배열의 모든 요소를 편하게 출력할 수 있다. toString()은 일차원 배열에만 사용할 수 있으므로, 다차원 배열에는 deepToString()을 사용해야 한다. deepToString()은 배열의 모든 요소를 재귀적으로 접근해서 문자열을 구성하므로 2차원뿐만 아니라 3차원 이상의 배열에도 동작한다.

int[] arr = {0, 1, 2, 3, 4};
int[][] arr2D = {{11, 12}, {21, 22}};

System.out.println(Arrays.toString(arr));
System.out.println(Arrays.deepToString(arr2D));

---------실행 결과----------
[0, 1, 2, 3, 4]
[[11, 12], [21, 22]]

 

equals()는 두 배열에 저장된 모든 요소를 비교해서 같으면 true, 다르면 false를 반환한다.

equals()도 일차원 배열에만 사용 가능하므로, 다차원 배열의 비교에는 deepEquals()를 사용해야 한다.

String[][] str2D = new String[][]{{"aaa", "bbb"}, {"AAA", "BBB"}};
String[][] str2D2 = new String[][]{{"aaa", "bbb"}, {"AAA", "BBB"}};

System.out.println(Arrays.equals(str2D, str2D2));
System.out.println(Arrays.deepEquals(str2D, str2D2));

--------실행 결과--------
false
true

다차원 배열은 배열의 배열의 형태로 구성하기 때문에 equals()로 비교하면, 문자열을 비교하는 것이 아니라 배열에 저장된 배열의 주소를 비교하게 된다. 서로 다른 배열은 항상 주소가 다르므로 false를 결과로 얻는다.

 

배열을 List로 변환 - asList(Object... a)

asList()는 배열을 List에 담아서 반환한다.

List list = Arrays.asList(new Integer[]{1, 2, 3, 4, 5});
List list2 = Arrays.asList(1, 2, 3, 4, 5);
list.add(6);        // unsuportedOperationException 예외 발생

주의할 점은 asList()가 반환한 List의 크기를 변경할 수 없다는 것이다.

즉, 추가 또는 삭제가 불가능하다. 저장된 내용은 변경 가능하다.

만약 크기를 변경할 수 있는 List가 필요하다면 다음과 같이 하면 된다.

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

 

 

Comparator와 Comparable

---

Comparator와 Comparable은 모두 인터페이스로 컬렉션을 정렬하는데 필요한 메서드를 정의하고 있으며,

Comparable을 구현하고 있는 클래스들은 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들, 주로 Integer와 같은 wrapper클래스와 String, Date, File과 같은 것들이며 기본적으로 오름차순으로 정렬되도록 구현되어 있다.

그래서 Comparable을 구현한 클래스는 정렬이 가능하다는 것을 의미한다.

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

    boolean eqauls(Object obj);
}

public interface Comparable {
    public int compareTo(Object o);
}

compareTo()와 compare() 메서드는 객체를 비교해서 음수, 0, 양수 중의 하나를 반환하도록 구현되어 있다.

 

Comaparable을 구현한 클래스들을 내림차순으로 정렬하던가 다른 기준에 의해서 정렬하고 싶을 때 Comparator를 구현해서 정렬 기준을 제공할 수 있다.

import java.util.Arrays;
import java.util.Comparator;

class Descending implements Comparator {
    public int compare(Object o1, Object o2) {
        if (o1 instanceof Comparable && o2 instanceof Comparable) {
            Comparable c1 = (Comparable)o1;
            Comparable c2 = (Comparable)o2;
            return c1.compareTo(c2) * -1 ;  // -1을 곱해서 기본 정렬방식의 역으로 변경한다.
                                            // 또는 c2.compareTo(c1)와 같이 순서를 바꿔도 된다.
        }
        return -1;
    }
}
public class Test {
    public static void main(String[] args) {
        String[] strArr = {"cat", "Dog", "lion", "tiger"};

        Arrays.sort(strArr);    //String의 Comparable구현에 의한 정렬
        System.out.println("strArr=" + Arrays.toString(strArr));

        Arrays.sort(strArr, String.CASE_INSENSITIVE_ORDER); // 대소문자 구분없이 오름차순 정렬
        System.out.println("strArr=" + Arrays.toString(strArr));

        Arrays.sort(strArr, new Descending());
        System.out.println("strArr=" + Arrays.toString(strArr));
    }
}

--------실행 결과---------
strArr=[Dog, cat, lion, tiger]
strArr=[cat, Dog, lion, tiger]
strArr=[tiger, lion, cat, Dog]

 

 

HashSet

---

HashSet은 저장 순서를 유지하지 않으며 중복된 요소를 저장하지 않는다.

HashSet 대신 LinkedHashSet을 사용하면 저장 순서를 유지할 수 있다.

HashSet에 중복된 요소를 추가하고자 한다면 메서드들은 false를 반환함으로써 중복된 요소이기 때문에 추가에 실패했다는 것을 알린다.

HashSet의 생성자

load factor는 컬렉션 클래스에 저장공간이 가득 차기 전에 미리 용량을 확보하기 위한 것으로 이 값을 0.8로 지정하면, 저장공간의 80%가 채워졌을 때 용량이 두 배로 늘어난다. 기본값은 0.75, 즉 75%이다.

HashSet의 메서드

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void main(String[] args) {
        String[] strArr = {"1", "1", "2", "2", "3", "3", "4", "4", "4"};
        Set<String> set = new HashSet<>();
        for(int i=0; i<strArr.length; i++) {
            set.add(strArr[i]);
        }
        System.out.println(set);
    }
}

-------실행 결과---------
[1, 2, 3, 4]

public class Test {
    public static void main(String[] args) {
        Object[] strArr = {"1",new Integer(1), "2", "2", "3", "3", "4", "4", "4"};
        Set set = new HashSet<>();
        for(int i=0; i<strArr.length; i++) {
            set.add(strArr[i]);
        }
        System.out.println(set);
    }
}

--------실행 결과---------
[1, 1, 2, 3, 4]

1이 두 번 출력되었는데, 하나는 String이고 다른 하나는 Integer로 서로 다른 객체이므로 중복으로 간주하지 않는다.

Set을 구현한 컬렉션 클래스는 순서를 유지하지 않기 때문에 저장한 순서가 다를 수 있다.

만일 중복을 제거하는 동시에 저장한 순서를 유지하고자 한다면 HashSet 대신 LinkedHashSet을 사용해야 한다.

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

        for (int i = 0; set.size() < 6; i++) {
            int num = (int) (Math.random() * 45 + 1);
            System.out.print(num + " ");
            set.add(new Integer(num));
        }
        System.out.println();

        List list = new LinkedList(set);
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
    }
}

--------실행 결과----------
42 17 8 25 35 24 
[17, 35, 8, 24, 25, 42]
[8, 17, 24, 25, 35, 42]

sort메서드는 인자로 List인터페이스 타입이 필요하기 때문에 LinkedList클래스의 생성자 LinkedList(Collection c)를 이용해서 HashSet에 저장된 객체들을 LinkedList에 담아서 처리했다.

 

 

TreeSet

---

TreeSet은 이진 검색 트리(binary search tree)라는 자료구조의 형태로 데이터를 저장하는 컬렉션 클래스이다.

이진 검색 트리는 정렬, 검색, 범위 검색(range search)에 높은 성능을 보이는 자료구조이며

TreeSet은 이진 검색 트리의 성능을 향상한 '레드-블랙 트리(Red-Black tree)'로 구현되어 있다.

• 중복된 데이터의 저장 허용하지 않음.
• 정렬된 위치에 저장하므로 저장 순서를 유지하지 않음.

이진 트리(binary tree)

이진 검색 트리(binary search tree)는 부모 노드의 왼쪽에는 부모 노드의 값보다 작은 값의 자식 노드를 오른쪽에는 큰 값의 자식 노드를 저장하는 이진트리이다.

 

이진 검색 트리에 7, 4, 9, 1, 5의 순서로 값을 저장한다고 가정하면 다음과 같은 순서로 진행된다.

이진 검색 트리에 값을 저장하는 과정

TreeSet은 정렬된 상태를 유지하기 때문에 단일 값 검색과 범위 검색(range search)이 매우 빠르다.

 

이진 검색 트리(binary search tree)

• 모든 노드는 최대 두 개의 자식 노드를 가질 수 있다.
• 왼쪽 자식 노드의 값은 부모 노드의 값보다 작고 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 한다.
• 노드의 추가 삭제에 시간이 걸린다. (순차적으로 저장하지 않으므로)
• 검색(범위 검색)과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다.

TreeSet의 생성자

TreeSet의 메서드

TreeSet의 메서드

import java.util.*;

public class Test {
    public static void main(String[] args) {
        TreeSet set = new TreeSet();
        int[] score = {80, 95, 50, 35, 45, 65, 10, 100};

        for (int i = 0; i < score.length; i++) {
            set.add(new Integer(score[i]));
        }
        System.out.println("50보다 작은 값" + set.headSet(new Integer(50)));
        System.out.println("50보다 큰 값" + set.tailSet(new Integer(50)));
    }
}

--------실행 결과---------
50보다 작은 값[10, 35, 45]
50보다 큰 값[50, 65, 80, 95, 100]

headSet 메서드와 tailSet 메서드를 이용하면, TreeSet에 저장된 객체 중 지정된 기준 값보다 큰 값의 객체들과 작은 값의 객체들을 얻을 수 있다.

위 코드에 사용한 데이터로 구성한 이진 검색 트리

 

 

HashMap

HashMap은 Map의 특징인 키(key)와 값(value)을 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다.

그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보인다.

Map의 상속계층도

HashMap의 소스코드 일부

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    transient Node<K,V>[] table;
    ...
    static class Node<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        ...
    }
}

HashMap은 Node <K, V>라는 내부 클래스를 정의하고 다시 Node<K, V> 타입의 배열을 선언하고 있다. 

키(key)와 값(value)은 별개의 값이 아니라 서로 관련된 값이기 때문에 각각의 배열로 선언하기보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성(integrity)적인 측면에서 더 바람직하기 때문이다.

HashMap의 생성자

HashMap의 메서드

import java.util.*;

public class Test {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("myId", "1234");
        map.put("asdf", "1111");
        map.put("myId", "1234");

        Scanner s = new Scanner(System.in);
        while (true) {
            System.out.println("Please enter id and password.");
            System.out.print("id: ");
            String id = s.nextLine().trim();
            System.out.print("password: ");
            String password = s.nextLine().trim();
            System.out.println();
            if (!map.containsKey(id)) {
                System.out.println("id does not exist.");
                continue;
            } else {
                if (!(map.get(id)).equals(password)) {
                    System.out.println("password does not math.");
                } else {
                    System.out.println("welcome.");
                    break;
                }
            }
        }
    }
}

데이터 쌍을 추가할 때 중복된 key가 있으면 데이터 쌍의 value가 key의 기존의 value에 덮어쓴다.

저장하려는 두 데이터 중에서 어느 쪽을 키로 할 것인지를 잘 결정해야 한다.

import java.util.*;

public class Test {
    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Kim Java", Integer.valueOf(90));
        map.put("Kim Java", Integer.valueOf(100));
        map.put("Lee Java", Integer.valueOf(100));
        map.put("Kang Java", Integer.valueOf(80));
        map.put("Ahn Java", Integer.valueOf(90));

        Set<Map.Entry<String, Integer>> set = map.entrySet();
        Iterator<Map.Entry<String, Integer>> it = set.iterator();
        while (it.hasNext()) {
            Map.Entry<String, Integer> e= (Map.Entry<String, Integer>)it.next();
            System.out.println("name: " + e.getKey() + ", score: " + e.getValue());
        }

        Set<String> keys = map.keySet();
        System.out.println("participants: " + keys);

        Collection<Integer> values = map.values();
        Iterator<Integer> it2 = values.iterator();

        int total = 0;
        while (it2.hasNext()) {
            Integer i = (Integer)it2.next();
            total += i.intValue();
        }

        System.out.println("total: " + total);
        System.out.println("average: " + (float) total / set.size());
        System.out.println("max: " + Collections.max(values));
        System.out.println("min: " + Collections.min(values));
    }
}

---------실행 결과-----------
name: Ahn Java, score: 90
name: Kang Java, score: 80
name: Lee Java, score: 100
name: Kim Java, score: 100
participants: [Ahn Java, Kang Java, Lee Java, Kim Java]
total: 370
average: 92.5
max: 100
min: 80

import java.util.*;

public class Test {
    static HashMap<String, HashMap<String, String>> phoneBook = new HashMap<>();

    public static void main(String[] args) {
        addPhoneNo("friend", "Lee Java", "010-111-1111");
        addPhoneNo("friend", "Kim Java", "010-222-2222");
        addPhoneNo("friend", "Kim Java", "010-333-3333");
        addPhoneNo("work", "Kim Daeri", "010-444-4444");
        addPhoneNo("work", "Kim Daeri", "010-555-5555");
        addPhoneNo("work", "Park Daeri", "010-666-6666");
        addPhoneNo("work", "Lee Guajang", "010-777-7777");
        addPhoneNo("laundary", "010-888-8888");
        printList();
    }

    static void addPhoneNo(String groupName, String name, String tel) {
        addGroup(groupName);
        HashMap<String, String> group = phoneBook.get(groupName);
        group.put(tel, name);  // 이름은 중복될 수 있으니 전화번호를 key로 저장한다.
    }

    static void addGroup(String groupName) {
        if(!phoneBook.containsKey(groupName))
            phoneBook.put(groupName, new HashMap<String, String>());
    }

    static void addPhoneNo(String name, String tel) {
        addPhoneNo("others", name, tel);
    }

    static void printList() {
        Set<Map.Entry<String, HashMap<String, String>>> set = phoneBook.entrySet();
        Iterator<Map.Entry<String, HashMap<String, String>>> it = set.iterator();

        while (it.hasNext()) {
            //Map.Entry<String, HashMap<String, String>> e = (Map.Entry<String, HashMap<String, String>>)it.next();
            Map.Entry<String, HashMap<String, String>> e = it.next();
            Set<Map.Entry<String, String>> subset = e.getValue().entrySet();
            Iterator<Map.Entry<String, String>> subIt = subset.iterator();

            System.out.println(" * " + e.getKey() + "[" + subset.size() + "]");
            while (subIt.hasNext()) {
                //Map.Entry<String, String> subE = (Map.Entry<String, String>)subIt.next();
                Map.Entry<String, String> subE = subIt.next();
                String telNo = subE.getKey();
                String name = subE.getValue();
                System.out.println(name + " " + telNo);
            }
            System.out.println();
        }
    }
}

---------실행 결과-----------
 * work[4]
Lee Guajang 010-777-7777
Kim Daeri 010-444-4444
Kim Daeri 010-555-5555
Park Daeri 010-666-6666

 * friend[3]
Lee Java 010-111-1111
Kim Java 010-222-2222
Kim Java 010-333-3333

 * others[1]
laundary 010-888-8888

 

 

해싱과 해시함수

해싱이란 해시함수(hash function)를 이용해서 데이터를 해시 테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 많은 데이터에서 원하는 데이터를 빠르게 찾을 수 있다.

 

해싱에서 사용하는 자료구조는 배열과 연결 리스트의 조합으로 되어 있다.

배열과 연결 리스트의 조합

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 요소에 연결되어 있는 연결 리스트에 저장한다.

HashMap에 저장된 데이터를 찾는 과정

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.
2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 연결 리스트를 찾는다.
3. 연결 리스트에서 검색한 키와 일치하는 데이터를 찾는다.

연결 리스트는 검색에 불리한 자료구조이기 때문에 연결 리스트의 크기가 커질수록 검색 속도가 떨어지게 된다.

이는 하나의 키에 데이터의 수가 많을수록 시간이 더 걸리는 것과 같다.

그래서 하나의 키에 하나의 데이터만 저장되어 있는 것이 더 빠른 검색 결과를 얻을 수 있다.

 

해싱을 구현하는 과정에서 가장 중요한 것은 해시함수의 알고리즘이다.

 

실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 hashCode()를 해시함수로 사용한다. 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 유일하다.

 

 

TreeMap

---

• 이진 검색 트리의 형태로 키와 값의 쌍으로 데이터를 저장.
• 검색과 정렬에 적합.

HashMap이 TreeMap보다 검색에 관한 대부분의 경우 더 뛰어나므로 HashMap을 사용하는 것이 좋다.

다만, 범위 검색이나 정렬이 필요한 경우에는 TreeMap을 사용하는 것이 좋다.

 

 

Properties

---

• (String, String)의 형태로 저장.
• 주로 환경설정과 관련된 속성을 저장하는 데 사용
• 파일로부터 읽고 쓰는 편리한 기능 제공.

 

 

Collections

---

컬렉션의 동기화

• 멀티 쓰레드(multi-thread) 프로그래밍에서 하나의 객체를 여러 쓰레드가 동시에 접근할 수 있다.
  -> 데이터의 일관성(constistency)을 유지하기 위해 공유되는 객체에 동기화(synchronization)가 필요하다.
• Vector와 Hashtable과 같은 구버전의 클래스들은 자체적으로 동기화 처리가 되어있다.
  -> 멀티 쓰레드 프로그래밍이 아닌 경우 불필요한 기능 -> 성능 저하
• ArrayList와 HashMap은 동기화를 자체적으로 하지 않고 필요한 경우에만 동기화 메서드를 이용

Collections클래스에서 제공하는 동기화 메서드

static Collection       synchronizedCollection(Collection c)
static List             synchronizedList(List list)
static Set              synchronizedSet(Set s)
static Map              synchronizedMap(Map m)
static SortedSet        synchronizedSortedSet(SortedSet s)
static SortedMap        synchronizedSortedMap(SortedMap m)

사용하는 방법

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

 

변경 불가 컬렉션 만들기

컬렉션에 저장된 데이터를 보호하기 위해 읽기 전용으로 만들어야 할 때가 있다. 주로 멀티 쓰레드 프로그래밍에서 여러 쓰레드가 하나의 컬렉션을 공유하다 보면 데이터가 손상될 수 있는데, 이를 방지하려면 아래의 메서드들 이용한다.

static Collection       unmodifiableCollection(Collection c)
static List             unmodifiableList(List list)
static Set              unmodifiableSet(Set s)
static Map              unmodifiableMap(Map m)
static NavigableSet     unmodifiableNavigableSet(NavigableSet s)
static SortedSet        unmodifiableSortedSet(SortedSet s)
static NavigableMap     unmodifiableNavigableMap(NavigableMap m)
static SortedMap        unmodifiableSortedMap(SortedMap m)

 

싱글톤 컬렉션 만들기

단 하나의 객체만을 저장하는 컬렉션을 만들고 싶은 경우

static Collection		singletonCollection(Collection c)
static List				singletonList(List list)
static Set				singletonSet(Set s)

매개변수로 저장할 요소를 저장하고 반환한다. 반환된 컬렉션은 변경할 수 없다.

 

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

컬렉션에 지정된 종류의 객체만 저장할 수 있도록 제한하고 싶을 때 아래의 메서드를 사용한다.

static Collection       checkedCollection(Collection c, Class type)
static List             checkedList(List list, Class type)
static Set              checkedSet(Set s, Class type)
static Map              checkedMap(Map m, Class KeyType, Class valueType)
static Queue            checkedQueue(Queue queue, Class type)
static NavigableSet     checkedNavigableSet(NavigableSet s, Class type)
static SortedSet        checkedSortedSet(SortedSet s, Class type)
static NavigableMap     checkedNavigableMap(NavigableMap m, Class type, Class valueType)
static SortedMap        checkedSortedMap(SortedMap m, Class keyType, Class valueType)

사용방법은 두 번째 매개변수에 저장할 객체의 클래스를 지정하면 된다.

List list = new ArrayList();
List checkdList = checkedList(list, String.class);	//String만 저장 가능
checkedList.add("abc");
checkedList.add(new Integer(3));		// ClassCastException 발생