Move Fast

▶ 스레드(Thread)

- 멀티 태스킹(Multi-Tasking) : 여러 개의 애플리케이션을 동시에 실행하면서 컴퓨터의 시스템 성능을 높이기 위한 기법이다.

 예를 들어, 파일을 인쇄하면서 동시에 문서를 편집하거나 인터넷에서 파일을 다운로드 받는 등의 경우가 있다. 이를 병렬 처리라고 한다.

 이러한 경우는 운영 체제가 CPU의 시간을 쪼개서 각 작업들에 할당하여서 작업들이 동시에 수행되는 것처럼 보이게 하기 때문이다. 멀티-코어(Multi-Core)를 가지고 있는 CPU라면 실제로도 동시에 실행될 것이다.

- 멀티 스레딩(Multi-Threading) : 하나의 애플리케이션 안에서도 여러 가지 작업을 동시에 하는 것을 의미한다. 

 앞서 말한 멀티 태스킹과 유사한 의미이다. 단지 범위를 애플리케이션 내부로 제한한 것이다. 자바는 멀티 스레딩을 프로그래머들한테 언어 수준에서 제공한다.

 예를 들어, (1) 음악을 재생하는 애플리케이션은 인터넷을 통하여 (2) mp3 파일을 다운로드 받으면서 동시에 압축을 풀어서 음악을 재생한다고 하면 각각의 작업 (1), (2) 는 스레드(Thread)라고 불린다.

- 스레드(Thread) : 실이라는 의미로, 하나의 실행 흐름(thread of execution)을 의미한다.

- 하나의 애플리케이션 안에서 동시에 실행되는 여러 스레드를 만들 수 있으며 이 스레드들은 자바 런타임 시스템에 의하여 동시에 실행된다.

▶ 프로세스와 스레드

- 프로세스와 스레드는 컴퓨터의 실행 단위이다.

• 프로세스(process)는 자신만의 데이터를 가진다.

• 스레드(thread)들은 동일한 데이터를 공유한다.

- 동시에 데이터를 공유하는 것은 자칫 위험할 수 있으나, 공유함으로서 스레드 간의 통신이 상당히 효율적이게 된다.

- 프로세스(Process)

• 실행 중인 프로그램을 의미한다.

• 독자적으로 실행이 가능한 환경을 가진다.

• 자신 만의 자원을 가진다.

• 프로세스의 메모리 공간은 다른 프로세스와 완전히 분리된다.

• 자바 가상 기계는 하나의 프로세스로 실행된다.

• 하나의 애플리케이션이 여러 개의 프로세스로 이루어질 수도 있다.

- 스레드(Thread)

• 경량 프로세스(lightweight process)라고도 불린다.

• 스레드를 생성하는 것은 프로세스를 생성하는 것보다 훨씬 자원이 적게 든다.

• 스레드들은 프로세스 안에 존재한다.

• 메모리와 파일을 포함하여 프로세스의 모든 자원을 공유한다.

• 모든 자바 애플리케이션은 적어도 하나의 스레드를 가진다. 이를 메인 스레드(main thread)라고 부른다.

• 메인 스레드에서 필요하면 추가적인 스레드를 생성할 수 있다.

- 동시 작업 프로그램은 단일 작업 프로그램보다 신경 써야할 부분이 많은데 그중 하나가 “동기화”이다. 동시에 여러 작업들이 같은 데이터를 공유하게 되면 발생하는 문제로 자바에는 이 문제를 해결할 수 있는 다양한 툴이 포함되어 있다. 이는 나중에 설명하도록 하겠다.

▶ 스레드의 생성과 실행

- 스레드를 나타내는 클래스는 Thread 이다.

• Thread 클래스의 객체를 생성하고 start()를 호출하면 스레드가 시작된다.

- 스레드의 작업은 Thread 클래스의 run() 메소드를 재정의(overriding)하여 작성한다. 따라서 스레드가 실행하는 모든 작업은 run() 메소드 안에 있어야 한다.

- 스레드가 시작되면 run() 메소드는 자바 런타임 시스템에 의하여 호출된다.

- 스레드를 생성하여 작업을 실행하는 방법은 아래와 같은 두 가지 방법이 있다.

• Thread 클래스를 상속하는 방법 : Thread 클래스를 상속받은 후에 run() 메소드를 재정의(overriding)한다.

• Runnable 인터페이스를 구현하는 방법 : run() 메소드를 가지고 있는 클래스를 작성하고 이 클래스의 객체를 Thread 클래스의 생성자를 호출할 때 매개변수로 전달한다. 
  

- Thread 클래스를 상속하는 방법

- Runnable 인터페이스를 구현하는 방법

 자바에서는 단일 상속만 가능하기 때문에 다른 클래스를 이미 상속받은 클래스는 스레드로 만들 수 없다. 이 경우에 Runnable 인터페이스를 구현하는 방법을 사용한다. Runnable 인터페이스 안에는 메소드 run() 만이 정의되어 있다. 이 방법이 좀 더 일반적인 스레드 실행 방법이다.

- 멀티 스레드 예제

class MyRunnable implements Runnable {
    String myName;

    public MyRunnable(String name) {
        myName = name;
    }

    public void run() {
        for(int i = 10; i >= 0; i--) {
            System.out.println(myName + i + " ");
        }
    }
}

public class ThreadTest {
    public static void main(String[] args) {
        Thread t1 = new Thread(new MyRunnable("A"));
        Thread t2 = new Thread(new MyRunnable("B"));
        t1.start();
        t2.start();
    }
}

 [출력 결과]

 여기서 총 스레드의 개수는 2개가 아닌 3개임에 주의해야 한다. 그 이유는 메인스레드와 t1 스레드, t2 스레드가 실행되고 있기 때문이다. 세 개의 스레드 모두 서로 다른 실행 흐름을 가진다.

- 예제 : 스레드를 정해진 시간 동안만 일시 중지하기

import javax.swing.*;
import java.awt.*;

public class CountDownTest extends JFrame {
    
    public static void main(String[] args) {
        new CountDownTest();
    }

    private JLabel label;

    CountDownTest() {
        setTitle("카운트 다운 예제");
        setSize(300, 200);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        label = new JLabel("Start", SwingConstants.CENTER); //글자를 레이블의 중간에 위치시킨다.
        label.setFont(new Font("Serif", Font.PLAIN, 100));
        add(label);

        Thread myThread = new MyThread
        myThread.start();

        setVisible(true);
    }

    class MyThread extends Thread { //스레드를 내부 클래스로 만들면 필드에 접근이 쉽다.
        public void run() {
            for(int i = 10; i >= 0; i--) {
                try {
                    Thread.sleep(1000); //sleep 의 매개변수는 밀리초 단위로 받기 때문에 1초동안 일시중지
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                label.setText(i + ""); // 1초가 지나면 레이블의 텍스트를 변경한다.
            }
        }
    }
}

▶ 스레드 활용

- Thread 클래스에는 스레드의 생성 및 제어에 관련된 여러 가지 메소드들이 정의되어 있다.

- 스레드 스케줄링

• CPU 스케줄링에 의하여 하나의 CPU를 여러 스레드가 나누어 쓸 수 있게 스케줄링하는 방법으로, 어떤 원칙과 순서로 스레드를 수행시킬 것인가를 결정한다.

• 자바 런타임 시스템은 우선순위(priority) 스케줄링을 이용한다. 이는 우선순위가 높은 스레드가 먼저 실행되는 알고리즘이다. 참고로 모든 스레드는 우선순위를 가지고 있다.

• 스레드는 생성되면 Thread 클래스에 정의된 MIN_PRIORITY와 MAX_PRIORITY 사이의 숫자인 우선순위를 배정 받는다.

• 스케줄러는 현재 수행 가능한 스레드 중에서 가장 우선순위가 높은 스레드를 먼저 수행시킨다.

• 스레드는 생성될 때 자신을 생성한 스레드로부터 우선순위를 상속받는다.

• 실행도중에는 setPriority()와 getPriority() 메소드를 이용하여 스레드의 우선순위를 변경하거나 얻는 것이 가능하다.

- 아래 4개의 메소드는 스케줄링과 관련된 가장 일반적으로 많이 쓰이는 메소드이다.

• sleep()

• join()

• yield()

• interrupt()

- sleep(long millis)

• 밀리초 단위로 스레드를 쉬게 할 수 있다.

• 스레드가 수면 상태로 있는 동안 interrupt 되면 InterruptedException 이 발생한다. 따라서 예외를 처리하여야 한다.

• 이 메소드는 CPU의 시간을 다른 스레드에게 넘겨주는 효율적인 방법이다.

• 다른 스레드의 보조를 맞추는 용도로도 사용될 수 있다.

• sleep()은 매개변수로 지정된 시간을 받을 때 밀리초 단위와 나노초 단위로 지정받을 수 있다.

• 해당 메소드는 분명히 지켜지는 것은 아니기 때문에 언제라도 중단될 수 있음을 감안해야 한다.

- interrupt()

• 하나의 스레드가 실행하고 있는 작업을 중지하도록 하는 메소드이다.

• 일반적으로 인터럽트 메소드가 실행되면 해당 스레드는 종료된다.

• 하나의 스레드가 다른 스레드의 interrupt()를 호출하면 대상 스레드가 중지된다.

• 그러나 인터럽트에 대한 스레드의 반응은 프로그래머가 설정할 수 있다.

 단, 스레드가 실행 중에 한번도 sleep()을 호출하지 않는다면 InterruptedException을 받지 못한다. 그러면 아래와 같이 인터럽트를 검사해주는 것이 좋다.

- join()

• 하나의 스레드를 다른 스레드가 종료될 때까지 기다리게 한다.

• 중복 정의된 join()을 사용하면 기다리는 시간을 지정할 수 있다.

 예를 들어 A라는 스레드가 선언된 객체에서 B라는 스레드의 종료를 기다리게 할려면 A 클래스 안에 B.join(); 이라고 작성해야 한다.

- yield()

• CPU를 다른 스레드에게 양보하는 메소드이다. 

• 동일한 우선순위를 가지고 있는 다른 스레드를 실행시키고자 할 때 사용된다.

- 예제

public class ThreadControl {
    //내부 클래스
    private static class MessageLoop implements Runnable {
        public void run() {
            String[] messages = { "Pride will have a fall.",
            "Poser is dangerous unless you have humility.",
            "Office changes manners.",
            "Empty vessels make the mose sound." };

            try {
                for(int i = 0; i < messages.length; i++) {
                    print(messages[i]);
                    Thread.sleep(2000);
                }
            }catch(InterruptedException e) {
                print("아직 끝나지 않았습니다!");
            }
        }
    }

    static void print(String message) {
        String threadName = Thread.currentThread().getName();
        System.out.format("%s : %s%n", threadName, message);
    }

    public static void main(String[] args) throws InterruptedException {
        int tries = 0;

        print("추가적인 스레드를 시작합니다.");
        Thread thread = new Thread(new MessageLoop());
        thread.start();

        print("추가적인 스레드가 끝나기를 기다립니다.");

        while(thread.isAlive()) {
            print("아직 기다립니다.");
            thread.join(1000); // thread가 종료하기를 1초동안 기다린다.
            tries++;

            if(tries > 2) {
                print("참을 수 없습니다");
                thread.interrupt();
                thread.join();
            }
        }
        print("메인 스레드 종료!");
    }
}

[출력 결과]

▶ 동기화

- 스레드 간섭(thread interference) : 다수의 스레드가 공유된 데이터에 접근할 때 발생한다.

 예를 들어, 하나의 스레드가 공유 데이터 값을 변경하고 있는 중간에 다른 스레드가 끼어들면 원치 않은 결과가 나타나게 된다.

- 메모리 일치 오류(memory consistency error) : 공유된 메모리의 불일치가 나타나는 현상이다.

- 동기화(Synchronization) : 위의 2가지의 문제를 해결하는 도구로, 공유된 자원 중에서 동시에 사용하면 안 되는 자원을 막는다. 즉, 공유된 자원을 충돌 없이 사용할 수 있도록 해주는 도구이다. 예를 들어 하나의 스레드의 작업이 끝나면 다음 스레드가 사용할 수 있도록 한다. 

- 임계 영역(Critical Section) : 일상을 예로 들면, 공중 화장실, 공동 세미나실, 공동 실험실, 공동 강의실과 같은 곳은 모두 하나의 사용자가 사용중이면 다른 사용자는 사용이 끝날 때까지 기다려야 한다. 이처럼 동시에 접근할 수 없는 공유 자원에 접근하게 해주는 코드의 일부라고 보면 된다.

▶ 스레드 간섭(Thread Interference)

- 서로 다른 스레드에서 실행되는 두 개의 연산이 동일한 데이터에 적용되면서 서로 겹치는 것을 의미한다.

- 결과적으로 데이터들이 섞이거나 데이터 값이 이상하게 변경된다.

- 예제

class Counter {
    private int value = 0;
     
    public void increment() { 
        value++; 
    }
    
    public void decrement() { 
        value--; 
    }
    
    public void printCounter() { 
        System.out.println(value); 
    }
} 

 위의 코드를 기반으로 하나의 특수한 상황을 예로 들면, 스레드 A가 increment()를 호출하고 동시에 스레드 B가 decrement()를 호출했다고 가정하자.

value의 초기값이 0이라면 다음과 같은 순서대로 연산이 겹칠 수 있다.

(1) 스레드 A : 변수 value의 현재값을 가져온다.

(2) 스레드 B : 변수 value의 현재값을 가져온다.

(3) 스레드 A : 가져온 값을 1 증가한다. 증가된 값은 1이 된다.

(4) 스레드 B : 가져온 값을 1 감소한다. 감소된 값은 –1이 된다.

(5) 스레드 A : value에 값을 저장한다. value 는 1이 된다.

(6) 스레드 B : value에 값을 저장한다. value 는 –1이 된다.

위의 경우 스레드 A가 저장한 값은 사라진다.

[전체 코드]

class Counter {
    private int value = 0;
     
    public void increment() { 
        value++; 
    }
    
    public void decrement() { 
        value--; 
    }
    
    public void printCounter() { 
        System.out.println(value); 
    }
}

class MyThread extends Thread {
    Counter sharedCounter;
     
    public MyThread(Counter c) {
        this.sharedCounter = c;
    }
     
    public void run() {
        int i = 0;
        while(i < 20000) {
            sharedCounter.increment();
            sharedCounter.decrement();
            //증가했다가 감소시키는 과정이 순차적이므로 카운터 값은 변화가 없다.
             
            if(i % 40 == 0) sharedCounter.printCounter(); //가끔 카운터 값 출력
             
            try {
                sleep((int) (Math.random()*2)); //난수 시간만큼 스레드를 중지한다.
            }catch (InterruptedException e) { }
             
            i++;
        }
    }
}
 
 
public class CounterTest {
    public static void main(String[] args) {
        Counter c = new Counter();
         
        new MyThread(c).start();
        new MyThread(c).start();
        new MyThread(c).start();
        new MyThread(c).start();
    }
}

결과 : (실행결과는 컴퓨터와 상황에 따라 상당히 달라진다.)

...

-7

-8

-7

-7

-8

-7

-7

...

 스레드 간섭이 없다면 모두 0이 출력되어야 하나, 음수 값을 가짐으로서 스레드 간섭이 발생했음을 알 수 있다.

▶ 메모리 불일치 오류

- 서로 다른 스레드가 동일한 데이터의 값을 서로 다르게 볼 때, 발생한다.

 예를 들어 아래와 같은 정수 변수가 스레드 A와 스레드 B 사이에서 공유된다하자.

스레드 A가 value++; 하여 value 값이 증가하였다.

잠시 후에 스레드 B가 value의 값을 출력하였다.

 위의 상황이 하나의 스레드 안에서 실행되었다면 아무런 문제가 발생하지 않고 “1”이 출력된다. 그러나 두 개의 문장이 서로 다른 스레드에서 실행되었다면 출력되는 결과는 “0”이 될 수 있다. 여기서 문제는 스레드 A가 변경한 값이 스레드 B에게 보일 것이라는 보장이 없기 때문이다.

▶ 동기화된 메소드

- 앞서 업급했던 동기화를 통해 스레드 간섭과 메모리 불일치 오류를 해결할 수 있다고 하였다.

- 동기화의 방법에는 두 가지가 있다.

• 동기화된 메소드(synchronized methods)

• 동기화된 문장(synchronized statements)

- 동기화된 메소드를 만들려면 synchronized 키워드를 메소드 선언에 포함하면 된다. 이 키워드의 의미는 동시에 접근할 수 없는 공유 자원에 접근할 수 있게 해주는 영역인 임계 영역 안에서 스레드를 실행하는 것이 보장된다는 것이다. 쉽게 말해 synchronized 키워드가 붙은 메소드는 공유 메소드가 되어 하나의 쓰레드만이 사용할 수 있게 된다.

 아래는 위에서 문제가 발생했던 Counter 클래스를 바람직하게 정의한 것이다.

 이처럼 synchronized 키워드를 붙이게 되면, 

 먼저 동기화된 메소드는 동시 호출되더라도 마이크로 단계들이 겹치지 않는다. 하나의 스레드가 동기화된 메소드를 실행하고 있으면, 그 스레드가 종료할 때까지 다른 모든 스레드는 중지된다. 따라서 스레드 간섭 문제를 해결한다.

 동기화된 메소드가 종료되면 자동적으로 이후의 동기화된 메소드 호출은 변경된 상태를 볼 수 있다. 따라서 메모리 불일치 오류 문제를 해결한다.

- 결과적으로, 어떤 객체를 두 개 이상의 스레드가 사용한다면, 공유된 객체의 변수에 대한 모든 읽기와 쓰기 연산은 동기화된 메소드를 통하여 이루어져야 한다. 이 기법은 효과적이지만 데드락(deadlock)과 아사 문제(starvation)는 해결할 수 없다.

▶ 스레드 간의 조정

- 두 개의 스레드 사이에서 데이터를 공유할 때, 데이터를 생산하고 있는 스레드를 생산자 스레드라 하고, 데이터를 사용하여 어떤 작업을 하는 스레드를 소비자 스레드라고 하자. 두 개의 스레드는 공유된 객체를 사용하여 통신을 하게 된다. 이런 경우 스레드 간의 조정이 필요하다.

- 위의 경우를 계속할 때, 소비자 스레드는 생산자 스레드가 데이터를 생산하여 가져다주기 전까지 데이터를 가져가면 안된다. 또한 생산자 스레드는 소비자 스레드가 이전 데이터를 가져가지 않았는데 새로운 데이터를 생산하면 안된다.

- 이와 같은 상황을 코드로 작성할 때, 최악의 경우는 스레드로 하여금 조건과 반복 루프에서 무한정 검사하게 하는 것이다. 이것을 폴링(polling)이라고 한다. 폴링(polling)은 CPU의 시간을 심각하게 낭비한다.

- 스레드 간의 조정에 있어 효율적인 방법은 조건이 만족할 때까지 현재의 스레드를 일시 중지시키는 것이다. 조건이 만족한다는 것은 어떤 이벤트의 발생이 될 수도 있고, 단지 하나의 조건일 수도 있다. Thread 클래스에서는 이처럼 다른 스레드가 어떤 이벤트가 발생했다고 알려줄 때까지 스레드를 중지시키는 wait() 메소드를 제공한다.  

• - wait() : 다른 스레드가 어떤 이벤트가 발생했다고 알려줄 때까지 스레드를 중지시킨다.

• 주의할 점은 wait()에서 리턴한 후에 반드시 다시 조건을 검사하여야 한다는 점이다. 발생된 이벤트가 우리가 원하는 이벤트가 아닐 수도 있기 때문이다.

• wait() 메소드는 InterruptedException을 발생시킬 수 있으로 try-catch 블록을 통해 예외 처리를 해주어야 한다.

- 스레드 간의 조정에 있어 synchronized 키워드를 사용하는 이유는 락(loack)과 관련이 있다. 

 예를 들어 스레드 A가 wait()의 호출 대상이라고 한다면 스레드 B가 A.wait()를 호출하면 스레드 B는 A에 대하여 락(lock)을 소유한다고 표현한다. 그렇지 않으면 오류가 발생한다.

• 동기화된 메소드 안에서 wait()를 호출하면 간단하게 락을 획득할 수 있다.

• wait() 메소드가 호출되면 대상 스레드는 가지고 있던 락을 해제하고 실행을 일시 중지한다.

• 차후에 다른 스레드가 동일한 락을 획득하여서 notifyAll()을 호출하면, 이벤트가 발생하기를 기다리면서 일시 중지된 모든 스레드들이 깨어나게 된다.

- wait() 메소드는 어떤 일이 일어나기를 기다릴 때 사용하는 메소드이다.

- notifyAll() 메소드는 어떤 일이 일어났을 때 이를 알려주는 메소드이다.

- 맨 처음 언급했던 생산자 스레드와 소비자 스레드를 예시로 계속 들면, wait() 메소드를 통해 생산자가 소비자에게 알려주면, 소비자 스레드가 작업이 끝나면 notifyAll()을 통해 생산자 스레드를 실행시킨다.

- 예제 : 생산자 스레드와 소비자 스레드를 구현해보자

class Buffer { //데이터를 공유하기 위한 버퍼 클래스
    private int data;
    private boolean empty = true;

    public synchronized int get() {
        while(empty) {
            try {
                wait(); //버퍼가 비어있는 동안 소비자 스레드는 기다린다.
            } catch (InterruptedException e) { }
        }

        empty = true;
        notifyAll(); //버퍼로부터 데이터를 가져갔으니 생산자 스레드를 깨운다.
        return data;
    }

    public synchronized void put(int data) {
        while(!empty) {
            try {
                wait(); //아직 버퍼가 비어있지 않으니 생산자 스레드는 기다린다.
            } catch (InterruptedException e) { }
        }

        empty = true;
        this.data = data; //버퍼가 비었으니 추가할 데이터를 저장한다.
        notifyAll();
    }
}


//생산자 클래스
class Producer implements Runnable {
    private Buffer buffer;

    public Producer(Buffer buffer) {
        this.buffer = buffer;
    }

    public void run() {
        for(int i = 0; i < 10; i++) {
            buffer.put(i);
            System.out.println("생산자 : "+ i + "번 데이터 생성");

            try {
                Thread.sleep((int) Math.random()*100);
            } catch (InterruptedException e) { }
        }
    }
}

//소비자 클래스
class Consumer implements Runnable {
    private Buffer buffer;

    public Consumer(Buffer drop) {
        this.buffer = drop;
    }

    public void run() {
        for(int i = 0; i < 10; i++) {
            int data = buffer.get();
            System.out.println("소비자 : "+ i +"번 데이터 소비");

            try {
                Thread.sleep((int) Math.random() * 100);
            } catch (InterruptedException e) { }
        }
    }
}

public class Test {
    public static void main(String[] args) {
        Buffer buffer = new Buffer();
        (new Thread(new Producer(buffer))).start();
        (new Thread(new Consumer(buffer))).start();
    }
}

▶ Collections 클래스

- Collections 클래스는 여러 유용한 알고리즘을 구현한 메소드들을 제공한다.

- 이 메소드들은 제네릭 기술을 사용하여 작성되었으며 정적 메소드의 형태로 되어있다.

- 자주 사용되는 알고리즘으로는 정렬(Sorting), 섞기(Shuffling), 탐색(Searching) 등이 있다. 

• 언급한 세 메소드의 첫 번째 매개변수는 알고리즘이 적용되는 컬렉션이다.

▶ 정렬(Sorting)

- 데이터를 어떤 기준에 의하여 순서대로 나열하는 알고리즘이다.

- 퀵 정렬, 합병 정렬, 히프 정렬 등의 다양한 방법이 존재한다.

- Collections 클래스의 정렬은 속도가 비교적 빠르고 안전성이 보장되는 합병 정렬을 이용한다.

- 안전성이란 동일한 값을 가지는 원소를 다시 정렬하지 않는 것을 의미한다.

- 안전성은 같은 리스트를 반복하여 다른 기준에 따라 정렬할 때 중요하다.

 예를 들어 상품 주문 리스트를 날짜를 기준으로 먼저 정렬하고 이후 주문처를 기준으로 정렬한다면 사용자는 같은 주문처가 보낸 주문은 날짜별로 정렬될 것이라고 가정한다. 이처럼 한번 정렬된 것이 유지되는 경우를 안정성 있는 정렬이라고 말한다.

- Collection 클래스의 sort() 메소드는 정적메소드로, List 인터페이스를 구현하는 컬렉션에 대하여 정렬을 수행한다.

 위의 경우는 원소가 String 타입이므로 알파벳 순서대로 정렬될 것이다. 원소가 Date 타입이라면 시간적인 순서로 정렬될 것이다. 그 이유는 String 클래스와 Date 클래스 모두 Comparable 인터페이스를 구현하기 때문이다.

- 정렬은 Comparable 인터페이스를 이용하여 이루어진다. List 인터페이스는 Comparable 인터페이스를 상속하므로

• comparaTo() 메소드는 매개변수 객체를 현재의 객체와 비교하여 작으면 음수, 같으면 0, 크면 양수를 반환한다.

- 예제 1

import java.util.*;

public class SortTest1 {
    public static void main(String[] args) {
        String[] example = { "Nice", "to", "meet", "you" };
        List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
        Collections.sort(list); //리스트 정렬

        System.out.println(list);
    }
}

[예제 1 출력 결과]

meet과 to의 위치가 바뀐 것을 볼 수 있다. 알파벳순이기 때문에 이러한 결과가 나온 것이다.

- 예제 2

import java.util.*;

class Student implements Comparable<Student> {
    int number;
    String name;

    Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

    public String toString() {
        return name;
    }

    @Override
    public int compareTo(Student s) {
        return number - s.number; //학번순서로 정렬한다.
    }
}

public class SortTest2 {
    public static void main(String[] args) {
        Student[] students = {
            new Student(02, "선옥자"),
            new Student(03, "한영희"),
            new Student(01, "김철수")
        };

        List<Student> list = Arrays.asList(students);
        Collections.sort(list);
        System.out.println(list);
    }
}

[예제 2 출력 결과]

- 예제 3 : 역순으로 정렬하기 - Collections.sort(list, Collections.reverseOrder());

import java.util.*;

public class SortTest {
    public static void main(String[] args) {
        String[] example = { "Nice", "to", "meet", "you" };
        List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
        Collections.sort(list, Collections.reverseOrder()); //리스트 역순정렬

        System.out.println(list);
    }
}

 [예제 3 출력 결과]

 역순정렬로 인해 예제 1의 출력 결과와 반대되는 결과를 볼 수 있다.

▶ 섞기(Shuffling)

- 리스트에 존재하는 정렬을 파괴하여서 원소들의 순서를 랜덤하게 만든다.

- 정렬과는 반대 동작을 한다.

- 주로 게임을 구현할 때 유용하게 쓰인다. 예를 들어 카드 게임에서 카드를 섞을 때 사용할 수 있다.

- 예제

import java.util.*;

public class Shuffle {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();

        for(int i = 0; i <= 10; i++) {
            list.add(i);
        }

        Collections.shuffle(list);
        System.out.println(list);
    }
}

 [출력 결과 1]

[출력 결과 2]

메소드를 실행할 때마다 서로 다른 출력 결과를 보인다.

▶ 탐색(Searching)

- 리스트 안에서 원하는 원소를 찾는 알고리즘이다.

- 선형 탐색 : 처음부터 모든 원소를 방문하는 탐색 방법으로, 리스트가 정렬되어 있지 않은 경우 사용한다.

- 이진 탐색 : 리스트가 정렬되어 있는 경우 중간에 있는 원소(m)와 먼저 비교하여, 크면 그다음부(m+1)터 끝까지 비교하고, 작으면 처음부터 그 전(m-1)까지의 원소들과 비교하는 방식을 반복하여 하나의 리스트를 계속해서 두 개의 리스트로 분할한다. 이 방법은 리스트에 하나의 원소가 남을 때까지 반복된다. 이진 탐색은 문제의 크기를 반으로 줄일 수 있기 때문에 선형 탐색보다 효율적이다.

- Collections 클래스는 정렬된 리스트에서 지정된 원소를 이진 탐색한다. 

- 이진 탐색 메소드인 binarySearch()는 만약 반환값이 양수이면 찾고자 하는 원소의 인덱스값이고, 음수이면 탐색이 실패한 것이다. 즉, 원소를 찾지 못했음을 의미한다.

 단, binarySearch() 메소드는 실패하더라도 도움이 되는 정보를 반환한다. 즉, 반환값에는 현재의 데이터가 삽입될 수 있는 위치 정보가 있다. 반환값이 pos라고 한다면, (-pos-1)이 해당 데이터를 삽입할 수 있는 위치이다.

- binarySearch() 메소드는 위에도 언급했듯이 “정렬된 리스트”에 한해서 탐색을 진행한다는 점에 주의하여야 한다.

▶ Map 인터페이스

- 많은 데이터 중에서 원하는 데이터를 빠르게 찾을 수 있는 자료 구조이다.

- 일반적으로 사전에 비유를 하는데, 사전은 단어가 있으면 단어에 대한 설명이 있다. Map에서는 그 단어(데이터)를 “키(Key)“라고 부르고 단어(데이터)에 대한 설명을 ”값(Value)“이라고 부른다.

- 중복된 키를 가질 수 없다. 각 키는 오직 하나의 값에만 매핑될 수 있다.

- 키가 제시되면 Map은 값을 반환한다.

 예를 들어 학생에 대한 정보를 Map에 저장할 때 키를 학번으로 두고, 값을 학생의 이름으로 할 때, 학번이 제시되면 Map은 학생의 이름을 반환한다.

- Map 인터페이스를 구현한 클래스로는 HashMap, TreeMap, LinkedHashMap 등이 있다.

• HashMap : 해싱 테이블에 데이터를 저장한다. 단, 저장한 순서와는 다르게 Key 값의 순서는 임의적이다.

• TreeMap : 탐색 트리에 데이터를 저장한다.

• LinkedHashMap : HashMap의 단점인 임의적인 순서를 보완하여 저장한 순서에 맞게 Key 값을 저장한다.

- 키들을 정렬된 순서로 방문할 필요가 없다면 HashMap이 TreeMap보다 빠르다.

- 예제

import java.util.*;

class Student {
    int number;
    String name;

    public Student (int number, String name) {
        this.number = number;
        this.name = name;
    }

    public String toString() {
        return name;
    }
}

public class MapTest {
    public static void main(String[] args) {
        Map<String, Student> stMap = new HashMap<String, Student>();
        stMap.put("01", new Student(01, "김철수"));
        stMap.put("02", new Student(02, "김영희"));
        stMap.put("03", new Student(03, "김자몽"));

        //모든 항목을 출력
        System.out.println("모든 항목을 출력 : " + stMap);

        //하나의 항목을 삭제
        stMap.remove("01"); //김철수 학생의 정보가 삭제된다.

        //하나의 항목을 대치
        stMap.put("03", new Student(03, "김옥자"));

        //값을 참조
        System.out.println("03번 학생의 이름 : " + stMap.get("03"));

        //모든 항목 방문
        for(Map.Entry<String, Student> s : stMap.entrySet()) {
            String key = s.getKey();
            Student value = s.getValue();
            System.out.println("key : " + key + ", value : " + value);
        }
    }
}

[출력 결과]

- Map에 저장된 데이터를 방문할 때는 Map.Entry 라는 인터페이스를 사용한다.

import java.util.*;

public class MapTest {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<String, Integer>();

        String[] example = { "Hi", "yes", "or", "not", "Hi", "yes", "no", "a", "and" };

        //문자열에 포함된 빈도 계산하기
        for(String str : example) {
            Integer freq = map.get(str);
            map.put(str, (freq == null) ? 1 : freq+1);
        }

        System.out.println(map.size() + "개의 단어가 있음"); //결과 : 7개의 단어가 있음
        System.out.println("containKey(\"to\") = " + map.containsKey("to"));
        System.out.println("isEmplty() = " + map.isEmpty());
        System.out.println("Map : " + map);
    }
}

[출력 결과]

▶ Queue 인터페이스

- 큐(Queue) : 데이터를 처리하기 전에 잠시 저장하고 있는 자료 구조이다.

- 전형적인 큐는 원소들을 FIFO(First-In-Fist-Out) 형식으로 저장하는 FIFO 큐인데, 후단(tail)에서 원소를 추가하고, 전단(head)에서 원소를 삭제한다. 새로운 원소들은 큐의 끝에 추가된다.

- 큐에서는 중간에 원소를 추가하는 것은 허용되지 않는다.

- 디큐는 자바 버전 1.6부터 Deque 인터페이스로 추가되었는데, 전단과 후단에서 모두 원소를 추가하거나 삭제할 수 있다.

- Deque 인터페이스는 ArrayDeque와 LinkedList 클래스들로 구현된다. 

- Queue 인터페이스는 기본적인 Collection의 연산 외에 다음과 같은 삽입, 삭제, 검색, 연산을 추가로 제공한다.

- 아래의 예제는 큐가 카운트 다운 타이머를 구현하는 예제이다.

import java.util.*;

public class QueueTest {
    public static void main(String[] args) throws InterruptedException {
        int time = 10;

        // LinkedList 안에 Queue 인터페이스가 구현되어 있다.
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = time; i > 0; i--) {
            queue.add(i);
        }

        System.out.println("start time : " + System.currentTimeMillis() / 1000);
        while(!queue.isEmpty()) {
            System.out.println(queue.remove()+ " ");
            Thread.sleep(1000); //현재의 스레드를 1초간 재운다.
        }
        System.out.println("end time : " + System.currentTimeMillis() / 1000);
    }
}

[출력 결과]

start time - end time = 10

- FIFO 큐가 전형적이지만 예외적인 큐도 존재한다. 원소들을 우선순위에 따라 저장하고 기본적인 우선순위는 원소들의 값으로 결정되는 우선순위 큐(Priority Queues)가 있다.

▶ 우선순위 큐(Priority Queue)

- 원소들이 무작위로 삽입되었더라도 정렬된 상태로 원소들을 추출한다.

- remove()를 호출할 때마다 가장 작은 원소가 추출된다.

- 우선순위 큐는 히프(heap)라고 하는 자료 구조를 내부적으로 사용하여 큐를 정렬한다.

• 히프는 이진 트리의 일종으로서 add()와 remove()를 호출하면 가장 작은 원소가 효율적으로 트리의 루트로 이동하게 된다.

• 오름차순으로 트리가 설정된다.

- 우선순위 큐의 가장 대표적인 예는 작업 스케쥴링(job scheduling)이다. 각 작업은 우선순위를 가지고 있고 가장 높은 우선순위의 작업이 큐에서 먼저 추출되어 시작된다.

- 아래는 우선순위 큐에 대한 예제이다.

import java.util.*;
 
public class PriorityQueueTest {
	public static void main(String[] args) {
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		 
		pq.add(30);
		pq.add(80);
		pq.add(20);
		 
		for(Integer o : pq) {
			System.out.println(o); // 20, 80, 30 순으로 출력됨
		}

		System.out.println("원소를 삭제합니다.");
		
		while(!pq.isEmpty()) {
			System.out.println(pq.remove()); //20, 30 80 순으로 정렬된 상태로 출력됨.
		}
	}
}

[출력 결과]