제네릭

제네릭 타입

public class StringBox {
    private String value;

    public void set(String object) {
        this.value = object;
    }

    public String get() {
        return value;
    }
}

• 위 클래스는 String 데이터를 넣고 빼는 역할을 한다.
• 데이터가 확장되는 경우, Object클래스 기반으로 다형성을 구현하거나 모든 타입별 박스 클래스를 생성할 수 있다.
  • 타입별 박스 구현: 코드 중복 과다 발생
  • 다형성: 입력 데이터에 잘못된 타입의 데이터를 넣을 가능성 존재 / 리턴 타입이 Object가 되므로 타입 다운캐스팅이 필요
• 해결되지 않는 위 두 문제를 제네릭을 활용하여 해결 가능하다.

public class GenericBox<T> {
    private T value;

    public void set(T value) {
        this.value = value;
    }

    public T get() {
        return value;
    }
}

// 생성시점
public static void main(String[] args) {
    GenericBox<Integer> integerBox = new GenericBox<Integer>();
    // ..
}

• 제네릭 클래스 생성 시점에 타입 매개변수에 타입 인자를 전달해주면 된다.
• 제네릭 타입 관례는 다음과 같다.
  • E - Element
  • K - Key
  • V - Value
  • N - Number
  • T - Type
  • S, U, V - 2nd, 4rd, 4th types

class Data<K, V>()

• 타입 매개변수에는 제한이 필요할때도 있다.

public class AnimalHospitalV2<T> {
    private T animal;

    public void set(T animal) {
        this.animal = animal;
    }

    public void checkup() {
        // 컴파일 에러 발생
        // System.out.println("동물 이름: " + animal.getName());
    }
}

• 제네릭을 사용하면 어떤 타입이 전달될지 모르기 때문에 컴파일러가 animal 인스턴스에 대한 내부 정보를 알수없다.
• 타입에 대한 제한이 없기 때문에 의도와 다른 Object, Integer등의 타입들을 마음대로 전달할 수 있다.
• 이러한 문제들을 해결하기 위해 타입 제한을 사용한다.
  • 타입 제한은 extends 키워드를 사용한다.

public class AnimalHospitalV2<T extends Animal> {
    // ...
}

• T 타입 인자로 Animal과 그 자식들만 받을 수 있도록 제한을 둔다.
• 이러한 타입 제한을 통해 컴파일러가 T가 받을 수 있는 값 범위를 예측할 수 있다.

제네릭 메서드

• 메서드에도 제네릭을 사용한다.
• 메서드 시그니처에서 리턴타입 전에 제네릭을 정의한다.
• 메서드 호출 시점에 타입 인자를 전달한다.

public <T> T genericMethod(T t) {
    return t;
}
//
//
instance.<Integer>genericMethod(3);

• 클래스의 제네릭 타입은 제네릭 static 메서드에서 사용 불가능하다.
• 클래스 제네릭 타입은 인스턴스 생성 시점에 결정되지만, static 메서드는 클래스 단위로 동작하기 때문이다.

public class Box<T> {

    void instanceMethod(T t) { }

    static <Z> void staticMethod(Z t) {}
}

• 자바는 타입 추론을 지원한다.
• 제네릭 메서드가 제네릭 클래스보다 타입 매개변수 우선순위가 높다.
  • 제네릭 클래스의 타입은 타입 제한을 걸고 제네릭 메서드에서는 제한을 걸지 않으면 제네릭 메서드 기반으로 타입이 고정된다.

타입 공변성

• 타입에 있어서 공변성이란, T가 S의 하위 타입이면 List<T>[]도 List<S>[]의 하위 타입인 성질을 의미한다.
• 제네릭은 타입 공변성이 없다. List<Number>[]와 List<Integer>[]는 별개이다.

타입 와일드 카드

• 자바에서는 와일드 카드로 제네릭 타입을 지정할 수 있다.
• ? 키워드를 통해 정의한다. 모든 타입을 다 받을 수 있다는 뜻이다.
• ? == <? extends Object>로 해석할 수 있다.
• ?만 입력한 와일드 카드는 비제한 와일드카드라고 한다.
• 제네릭 타입 및 제네릭 메서드 정의가 꼭 필요하지 않으면 와일드 카드 사용을 권장한다.

static <T> void printGeneric(Box<T> box) {
    // ..
}

//..

static void printWildcard(Box<?> box) {
    // ..
}

• 와일드카드도 extends를 통해 타입 제한을 둘 수 있다.
  • Box<? extends Animal>이는 상한 와일드 카드이다.
  • Box<? super Animal>은 하한 와일드 카드이다. Animal 타입의 상위 타입들만 전달 가능하다.

타입 이레이저 (Type Erasure)

• 자바는 제네릭을 컴파일 단계에서만 사용하고 이후에는 제네릭 정보를 삭제한다.
• 타입 매개변수에 제한을 둔 경우 제한을 둔 타입으로 코드를 변경한다.

ArrayList

• 선언 코드는 아래와 같다.
• 고정된 데이터 크기를 관리할때, 인덱싱 위주로 동작할때 효율적이다.

import java.util.Arrays;

public static void main(String[] args) {
    int[] arr = new int[5];
}

• 배열과 리스트는 구분하여 이야기한다.
  • 배열: 순서가 있고 중복을 허용하지만 크기가 정적으로 고정된다.
  • 리스트: 순서가 있고 중복을 허용하지만 크기가 동적으로 변한다.
• ArrayList는 리스트 자료구조를 사용하되 내부 데이터는 배열에 보관하는 자료구조이다.
• 데이터 크기가 가변적이기 때문에 중간 삽입 및 삭제 등의 연산 시 O(N) 복잡도가 발생한다.
• 앞이나 중간에 데이터를 추가할때 성능이 좋지 않다.

LinkedList

• 배열은 사용하지 않는 공간이 낭비된다.
• 중간 삽입 및 삭제 성능이 좋지 않다.
• 연결 리스트를 사용하면 참조만 변경하면 되므로 중간 삽입 및 삭제 연산이 O(1)로 수행된다.

연산	ArrayList	LinkedList	비고
인덱스 조회	O(1)	O(n)	ArrayList는 배열 기반으로 직접 접근 가능
검색	O(n)	O(n)	둘 다 순차 탐색
앞에 추가/삭제	O(n)	O(1)	ArrayList는 요소 전체 shift 필요
뒤에 추가/삭제	O(1)	O(n)	ArrayList는 amortized O(1), 용량 초과 시 O(n)
평균 추가/삭제	O(n)	O(n)	LinkedList는 탐색 O(n) + 삽입 O(1)

• 자바 연결리스트는 양방향 이동이 가능한 이중 연결리스트이다.
• 끝노드의 tail노드가 head가 되므로, O(1)시간에 접근 가능하다.
• 자바 언어상으로는 내부 구현의 차이이지, LinkedList 객체에서 tail, head 속성을 제공하지는 않는다.

List

• BatchProcessor라는 클래스를 구현한다고 가정하자.
• 데이터 add, remove등의 메서드를 구현할때, ArrayList기반으로 삽입 추가 메서드가 구현되어 있다.
• 이때 내부 성능이 크게 저하되어 삽입 추가 메서드를 LinkedList기반으로 구현하려고 한다.
• 만약 BatchProcessor클래스가 ArrayList클래스에 직접 의존하고 있었다면 내부 모든 코드와 구현을 LinkedList기반으로 전환해야 한다.
• 이러한 번거로움을 줄이기 위해 ArrayList와 LinkedList의 공통 함수를 추출하여 인터페이스로 빼두고, 다형성 기반으로 BachProcessor 내부 데이터 보관소 타입을 자유롭게 변경할 수 있다.
  • 리스트 기반 동작을 자바에서는 List 인터페이스로 추출해두었다.
• 이러한 구조를 외부에서 의존관계가 결정되어 인스턴스에 주입하는 것 같다고 하여, 의존관계 주입이라고 표현한다.

컴파일 타임 의존관계 vs 런타임 의존관계

• 컴파일 타임 의존관계: 자바 컴파일러가 보는 의존관계이다.
  • 클래스에 바로 보이는 의존관계
  • 실행하지 않은 소스 코드에 정적으로 나타나는 의존관계
• 런타임 의존관계: 실제 프로그램이 작동할 때 보이는 의존관계
  • 인스턴스 간의 의존관계
  • 실행 중 계속 변할 수 있다.

Hash

• Set은 유일한 요소들의 컬렉션이다.
  • 유일성을 보장한다.
  • 순서는 보장하지 않는다.
  • 조회가 빠르다.
• Set 내부 구현을 배열로 할 경우, contains, add, remove 구현을 할때 모든 동작에 대해 O(n) 복잡도를 갖는다. 이렇게 되면 성능이 매우 떨어진다.
  • 동적 배열이더라도 사용되지 않는 공간 최적화가 이루어지지 않으면 메모리가 낭비되기 쉽다.
• 해시 알고리즘을 사용하면 조회 성능이 O(1)으로 크게 개선된다.
  • 내부 데이터가 배열이라고 가정할때 int 데이터를 10으로 나머지 연산을 한 결과가 인덱스라고 가정해보자.
  • 이 경우 값을 보고 인덱스를 즉시 알 수 있기 때문에 조회를 즉시 할수있다.
  • 그러나 나머지 연산 시 동일한 값이 산출되면 해시의 충돌이 발생하게 된다.
• 해시 충돌 해결을 위해 2차원 배열을 활용할 수 있다.
  • 이렇게 구현했을때 최악의 경우 O(n)의 조회 성능이 발생할 수 있다.
  • 해시 충돌은 발생 가능하지만 확률은 낮은 현상으로 본다.
• 통계학적으로 입력 데이터 수가 배열 크기의 75%를 넘지 않으면 해시 충돌 확률은 낮다고 본다.
• 해시의 시간복잡도는 다음과 같다.
  • 데이터 저장
    • 평균: O(1)
    • 최악: O(N) / 해시충돌
  • 데이터 조회
    • 평균: O(1)
    • 최악: O(N) / 해시 충돌
• 조회를 위한 키값이 문자열인 경우 hashCode메서드와 같이 문자열 값을 특정 해시값으로 변경하여 조회한다.

해시 함수

• 해시 함수는 임의 길이의 데이터를 입력받아 고정 길이의 해시값을 출력하는 함수이다. (int의 경우 4byte를 의미하는 고정 길이)
• 해시 함수는 같은 데이터 입력시 항상 같은 해시 코드가 출력된다.
• 다른 데이터를 입력해도 같은 해시 코드가 출력될 수 있다. (해시 충돌)

• 클래스타입을 비롯한 수많은 타입들에 대해 해시 코드는 Object.hashCode() 함수에서 얻을 수 있다.
• 객체 참조값을 기반으로 해시 코드를 생성하는데, 인스턴스가 다르면 해시코드도 다르다.
• 해시 자료구조는 equals를 반드시 오버라이딩 해야한다.
  • 해시 충돌 시 동일 인덱스 내의 모든 데이터를 조회해보아야 하기 때문이다.
• hashCode를 오버라이딩 하지 않은 클래스 인스턴스는 기본 Object타입의 hashCode 메서드를 사용하게 된다.
  • 참조 기반으로 동작하기 때문에, 프로퍼티에 id값이 있다고 가정할때 해당값이 동일해도 다른 해싱을 할 여지가 존재한다.
• 자바에서 제공하는 해시함수는 충돌 확률이 적고, 균일하게 분포한다.