[Java/Study] 김영한의 실전 자바 중급 2편 - 스터디 13회차

 

인프런 강의 <김영한의 실전 자바 - 중급 2편>을 보고 정리한 내용입니다.

매주 모여 각자 정리한 내용을 기반으로 발표하고 질문 공유하는 스터디입니다.

---

 

📘List

"의존한다" 라는 것은 무엇일까? 다음과 같이 MyList를 구현하는 MyArrayList와 MyArrayList를 만들었다.

public interface MyList<E> {
    int size();
    void add(E e);
    void add(int index, E e);
    E get(int index);
    E set(int index, E element);
    E remove(int index);
    int indexOf(E o);
}

public class MyArrayList<E> implements MyList<E> {
 //...
}

public class MyLinkedList<E> implements MyList<E> {
 //...
}

 

만약 MyArrayList 를 활용해서 많은 데이터를 처리하는 BatchProcessor 클래스를 개발한다고 할 때, 데이터를 앞에서 추가하는 일이 많은 상황이 올 수 있다. 그러면 그때마다 MyLinkedList 를 사용하도록 코드를 변경해야 한다. 이런 상황을 BatchProcessor가 구체적인 클래스에 의존한다고 표현한다.

public class BatchProcessor {

    private final MyArrayList<Integer> list = new MyArrayList<>();

    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }

    public void logic(int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i); // 앞에 추가
        }
        long endTime = System.currentTimeMillis();
        System.out.println("크기: " + size + 
        ", 계산 시간: " + (endTime - startTime) + "ms");
    }

}

 

구체적인 클래스에 의존하는 대신 추상적인 MyList 인터페이스에 의존할 수 있다. 이렇게 하면 BatchProcessor를 생성하는 시점에 리스트 전략을 선택해 전달하면 되고, 클라이언트 코드인 BatchProcessor의 변경 없이도 MyArrayList에서 MyLinkedList로 변경하는 것이 가능하다. 바로 이것을 의존 관계 주입(Dependency Injection, DI)이라고 한다.

public class BatchProcessor {

    private final MyList<Integer> list = new MyList<>();

    public BatchProcessor(MyList<Integer> list) {
        this.list = list;
    }

    public void logic(int size) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            list.add(0, i); // 앞에 추가
        }
        long endTime = System.currentTimeMillis();
        System.out.println("크기: " + size + 
        ", 계산 시간: " + (endTime - startTime) + "ms");
    }

}

 

다음과 같이 외부에서 MyArrayList를 쓸지, MyLinkedList를 쓸지 결정할 수 있다는 것이다. 이 예시 코드에서는 BatchProcessor의 생성자를 통해 의존관계를 주입했기 때문에 생성자 의존관계 주입(생성자 주입)이라고 한다.

public class BatchProcessorMain {
    public static void main(String[] args) {
//        MyArrayList<Integer> list = new MyArrayList<>();
        MyLinkedList<Integer> list = new MyLinkedList<>();

        BatchProcessor processor = new BatchProcessor(list);
        processor.logic(50_000);
    }
}

 

의존관계는 두 가지로 나뉜다.

 

1) 컴파일 타임 의존관계

• 컴파일 타임(compile time): 코드 컴파일 시점
• 자바 컴파일러가 보는 의존관계로, 실행하지 않은 소스 코드에 정적으로 나타난다.
• BatchProcessor 클래스를 보면 MyList 인터페이스에만 의존하고 있는 것을 알 수 있다.
• 화살표 방향은 의존관계라고 보면 된다.

컴파일 타임 의존관계

2) 런타임 의존관계

• 런타임(runtime): 프로그램 실행 시점
• 실제 프로그램이 작동할 때 보이는 의존관계로, 프로그램이 실행될 때 인스턴스 간에 의존관계이다.
• 런타임 의존관계는 프로그램 실행 중에 계속 변할 수 있다.

런타임 의존관계

 

BatchProcessor를 생성할 때 생성자를 통해 MyArrayList의 참조인 x001을 던져준다. list 필드가 x001을 세팅하면 BatchProcessor가 MyArrayList를 사용할 수 있게 된다. 따라서 MyArrayList에 대해 런타임 의존관계를 가지게 된다. 따라서 이후에 logic() 을 호출하면 MyArrayList 인스턴스를 사용하게 된다.

 

클라이언트 클래스는 컴파일 타임에 추상적인 것에 의존하고, 런타임에 의존 관계 주입을 통해 구현체를 주입받아 사용함으로써 다양한 이점을 얻을 수 있다.

✔️ 전략 패턴(Strategy Pattern)
전략 패턴은 중요한 디자인 패턴 중 하나로, 위의 예시 코드처럼 알고리즘을 클라이언트 코드의 변경 없이 쉽게 교체할 수 있는 패턴이다. MyList 인터페이스가 전략을 정의하는 인터페이스가 되고, 각각의 구현체인 MyArrayList , MyLinkedList 가 전략의 구체적인 구현이 된다. 그리고 전략을 클라이언트 코드인 BatchProcessor의 변경 없이 손쉽게 교체할 수 있다.

 

ArrayList와 LinkedList의 성능을 비교해보면 어떨까? 결론부터 말하자면 대부분의 경우 ArrayList가 성능상 유리하기 때문에 실무에서는 주로 ArrayList를 사용한다. 데이터를 앞쪽에서 추가/삭제하는 일이 많다면 LinkedList를 고려하는 것이 좋다.

 

직접 구현한 MyArrayList & MyLinkedList와 자바가 제공하는 ArrayList & LinkedList의 성능 차이는 다음과 같다.

직접 구현한 List(왼) / 자바 List(오)

 

직접 구현한 List와 자바가 제공하는 List는 계산 시간 차이는 있지만 ArrayList와 LinkedList의 성능 차이는 비슷하다. 다른 점이라면 Linked 리스트의 경우 뒤에 추가(삭제) 할 때 자바의 LinkedList가 O(1)의 성능으로 더 빠르다. 왜냐하면 자바가 제공하는 LinkedList는 첫번째 위치뿐만 아니라 마지막 위치까지 가지고 있기 때문이다.

기능	ArrayList	LinkedList
앞에 추가(삭제)	O(n)	O(1)
평균 추가(삭제)	O(n)	O(n)
뒤에 추가(삭제)	O(1)	O(1)
인덱스 조회	O(1)	O(n)
검색	O(n)	O(n)

 

또한 데이터 추가 시 MyArrayList(평균 966ms)보다 자바의 ArrayList(평균 45ms)가 더 빠른 것을 알 수 있다. 그 이유는 자바의 ArrayList는 데이터를 추가할 때 메모리 고속 복사를 사용하기 때문이다. 데이터가 아주 많은 경우와 시스템에 따른 차이를 제외하면 대략 O(n/10) 정도의 성능으로 추정하고, 상수를 제거하면 O(n)이 된다. 

 

✔️ 결론

이론과 달리 실제 성능은 요소의 순차적 접근 속도, 메모리 할당 및 해제 비용, CPU 캐시 활용도 등 다양한 요소에 의해 영향을 받는다. 또한 ArrayList가 데이터를 하나씩 미는 대신 메모리 고속 복사를 이용하기도 한다. 특히 ArrayList는 메모리 상에서 연속적으로 위치하기 때문에 CPU 캐시 효율이 좋고, 메모리 접근 속도가 빠르다. 반면, LinkedList 는 각 요소가 별도의 객체로 존재하고 다음 요소의 참조를 저장하기 때문에 CPU 캐시 효율이 떨어지고, 메모리 접근 속도가 상대적으로 느려질 수 있다.

 

=>  배열 리스트가 성능상 유리하다!

📘Hash

List와 Set의 차이는 다음과 같다.

• List : 순서를 유지하며, 중복을 허용하는 자료구조. 인덱스를 통해 각 요소에 접근할 수 있다.
  • ex. 장바구니 목록, 순서가 중요한 일련의 이벤트 목록.
• Set : 순서를 유지하지 않으며, 중복을 허용하지 않는 자료구조. 요소의 유무를 빠르게 확인할 수 있도록 최적화 되어있어서 빠른 조회가 가능하다.
  • ex. 회원 ID 집합, 고유한 항목의 집합.

직접 구현한 Set은 다음과 같다. 데이터 추가, 삭제, 확인만 하면 간단하게 구현할 수 있다. 단, Set은 중복을 허용하지 않기 때문에 데이터를 추가할 때 contains() 메서드로 중복 여부를 체크해줘야 한다.

public class MyHashSetV0 {

    private int[] elementData = new int[10];
    private int size = 0;

    // O(n) - contains() 메서드 때문
    public boolean add(int value) {
        // 중복 값 체크
        if (contains(value)) {
            return false;
        }
        elementData[size] = value;
        size++;
        return true;
    }

    // O(n) - for문으로 하나하나 찾아야 함
    public boolean contains(int value) {
        for (int data : elementData) {
            if (data == value) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        return "MyHashSetV0{" +
                "elementData=" + Arrays.toString(Arrays.copyOf(elementData, size)) +
                ", size=" + size +
                '}';
    }
}

 

이렇게 만든 Set은 데이터 추가, 검색 모두 O(n)으로 성능이 좋지 않다. 데이터를 추가할 때마다 중복 데이터가 있는지 체크하기 위해 Set의 전체 데이터를 확인해야 한다. 이런 문제는 해시 알고리즘을 사용하면 해결할 수 있다.

해시 알고리즘

배열에서 데이터를 검색할 때는 하나하나 비교해야하기 때문에 O(n)의 시간이 걸리고, 배열의 장점인 인덱스를 사용할 수 없다. 왜냐하면 인덱스와 데이터의 값이 서로 다르기 때문이다. 인덱스로 검색을 하려면 다음 코드와 같이 데이터 값을 인덱스 번호로 사용하면 된다. 이렇게 하면 인덱스로 바로 데이터를 찾을 수 있어 O(1)의 시간이 걸린다.

Integer[] inputArray = new Integer[10];
inputArray[1] = 1;
inputArray[2] = 2;
inputArray[5] = 8;
inputArray[8] = 8;

 

위의 배열을 출력하면 이렇게 나올 것이다. 찾는 것은 바로 찾을 수 있겠지만, 수많은 null 값들이 매우 거슬린다. 만약 99라는 값이 들어간다면, 배열은 입력 값의 범위 만큼 큰 배열을 사용해야 한다. 따라서 낭비되는 공간이 많이 발생한다.

inputArray = [null, 1, 2, null, null, 5, null, null, 8, null]

 

이런 문제는 나머지 연산을 통해 해결할 수 있다. 배열의 크기에 맞추어 나머지 연산을 한 결과는 다음과 같다. 이렇게 하면 0 ~ 9 범위로 인덱스 값이 나온다. 이렇게 배열의 인덱스로 사용할 수 있도록 원래의 값을 계산한 인덱스를 해시 인덱스(hashIndex)라 한다.

• 1 % 10 = 1
• 2 % 10 = 2
• 5 % 10 = 5
• 8 % 10 = 8
• 14 % 10 = 4
• 99 % 10 = 9

다음과 같이 나머지 연산을 하는 hashIndex() 메서드와 해시 인덱스를 이용해 값을 추가하는 add() 메서드를 구현했다. 넣을 때 hashIndex() 메서드를 통해 나온 값에 데이터를 넣고, 검색을 할 때도 검색하고자 하는 값을 hashIndex() 메서드에 넣어 해시 인덱스를 구하면 된다.

private static void add(Integer[] inputArray, int value) {
    int hashIndex = hashIndex(value);
    inputArray[hashIndex] = value;
}

static int hashIndex(int value) {
    return value % CAPACITY;
}

 

하지만 여기에도 한계가 있다. 바로 해시 충돌이 날 수 있다는 것이다. 만약 9와 99를 입력한다면 둘 다 10으로 나눈 나머지가 9이기 때문에 덮어씌워져 마지막에 저장한 값만 남게 된다.

• 99 % 10 = 9
• 9 % 10 = 9

이 문제를 해결하기 위해 배열의 크기를 늘리는 방법도 있겠지만 위에서 보았듯이 메모리 낭비가 심해질 것이다. 따라서 해시 충돌이 낮을 확률로 일어날 수 있다고 인정하고 같은 해시 인덱스의 값을 같은 인덱스에 저장하면 문제를 해결할 수 있다. 배열 안에 또 다른 배열(혹은 리스트)를 만들어 같은 해시 인덱스 값을 가진 데이터를 저장한다. 다음 코드는 LinkedList를 사용해 해시 충돌이 일어날 경우를 대비한 코드이다.

private static void add(LinkedList<Integer>[] buckets, int value) {
    int hashIndex = hashIndex(value);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
    if (!bucket.contains(value)) { // 중복 체크 - O(n)
        bucket.add(value);
    }
}

private static boolean contains(LinkedList<Integer>[] buckets, int searchValue {
    int hashIndex = hashIndex(searchValue);
    LinkedList<Integer> bucket = buckets[hashIndex]; // O(1)
    return bucket.contains(searchValue); // O(n)
}

static int hashIndex(int value) {
    return value % CAPACITY;
}

 

데이터를 검색할 때는 LinkedList의 contains() 메서드를 이용해 모든 항목을 다 순회하면서 찾는 데이터가 있는지 확인한다. 따라서 O(n)의 성능이고, 해시 충돌이 발생하지 않아 데이터가 1개만 들어있는 경우에만 O(1)의 성능이다.

 

💡 정리
해시 인덱스를 사용할 때 최악의 경우는 거의 발생하지 않고, 대부분 O(1)의 빠른 성능을 제공한다.

• 데이터 저장
  • 평균: O(1)
  • 최악: O(n)
• 데이터 조회
  • 평균: O(1)
  • 최악: O(n)