자바의 제네릭 (Generic)

오늘은 자바의 제네릭과 관련해서 글을 써내려가려 한다. 자바의 제네릭은 어렵다. 필자가 생각하기엔 자바에서 가장 어려운 문법? 부분에 속한다고 할 수 있다. 누군가가 자바에서 가장 어려운게 무엇이냐고 물어보면 1초도 망설이지 않고 제네릭이라고 대답했을 것이다. 그만큼 나에겐 어렵다.
자바의 제네릭을 아주 자유자재로 사용할 수 있는 개발자는 많지 않을 것이라고 생각한다. (내가 못해서 그렇게 생각할지도..)

자바의 Generic은 처음 나왔을 때 부터 있었던 것은 아니다. 1996년에 자바가 처음 발표되고 8년이 지난 2004년에 java5가 발표되면서 Generic이 추가되었다. java5가 발표되면서 아주아주 많은 변화가 있었다. java8의 람다만큼 큰 변화가 많이 있었다. (어쩌면 람다보다 더..) 그 중에서 가장 대표적인 것들은 Generic, 오토박싱/언박싱, foreach, enum type, 가변인자(varargs), 어노테이션(Annotation) 등 무수히 많은 변화를 들고 나왔다. 그 때 당시에는 자바개발자들이 고생을 많이 했겠다. 구현한 사람이나 사용하는 사람이나..

제네릭 작성해보기

일단 간단하게 제네릭 타입인 List<E>를 작성해보자. 뭐 자주 사용하는 인터페이스니 예제를 남길 필요도 없을 듯 한데..

List<Integer> numbers = new ArrayList<>();
numbers.add(1);
numbers.add(2);
numbers.add(3);

우리가 흔히 작성하는 코드이다. List의 <E>를 타입 파라미터라고 부른다. 이것이 있기에 우리는 컴파일 타임에 해당 타입이 일치하는지 확인 할 수 있다. 좀 더 안전하게 사용할 수 있게 되었다. 예전 자바5 이전에는 Generic이 존재 하지 않았기 때문에 아무 객체나 넣을 수 있었다.

List numbers = new ArrayList();
numbers.add(1);
numbers.add("2");
numbers.add(3);

위와 같이 말이다. 하지만 현재도 위와 같이 작성해도 문제 없이 컴파일이 되고 실행된다. 그 이유는 아래가서 설명하겠다.
그럼 한번 타입파라미터가 있는 클래스를 간단하게 만들어보자.

MyList

자바의 ArrayList를 참고해서 나만의 리스트를 만들어보자.

public class MyList<E> {
  private static final int DEFAULT_CAPACITY = 10;
  private Object element[];
  private int index;

  public MyList() {
    element = new Object[DEFAULT_CAPACITY];
  }

  public void add(E e) {
    this.element[index++] = e;
  }

  public E get(int index){
    return (E) element[index];
  }
}

아주 심플하게 나만의 리스트를 만들었다. 보기에도 심플하고 만들기도 심플하다. 물론 예외처리라든지 리스트의 길이 동적으로 변한다는지는 나중 문제지 여기서 핵심은 그게 아니라서 제외시켰다. 물론 알겠지만..
아무튼 우리는 자바의 Generic을 이용해서 클래스를 만들어 봤다. MyList라는 클래스는 타입 파라미터가 존재한다. 이는 MyList라는 클래스에 사용될 클래스를 제한한다는 뜻이다. add(E) 라는 메서드의 E는 클래스의 타입과 동일해야만 한다. 마찬가지로 get 메서드의 리턴타입도 E 로 정의해 두었으니 클래스의 타입과 동일해야 된다.
만약 String으로 정의했는데 int, long, double, pojo나 기타 다른 타입이 들어간다면 컴파일 타임에 에러를 발생시킨다.
한번 사용해보자.

MyList<String> myList = new MyList<>();
myList.add("wonwoo");
myList.add("seungwoo");
myList.add(1); //컴파일 에러
System.out.println(myList.get(0));
System.out.println(myList.get(1));

우리는 안전하게 해당 타입에 맞는 List를 만들수 있어서 보다 버그나 에러를 줄일 수 있게 되었다.

근데 코드를 자세히보면 뭔가 꺼림칙하다. element을 Object로 선언하고 (Object 선언은 봐줄수 있을 언정) get() 메서드를 보면 E 타입으로 캐스팅까지 한다. 뭔가 마음에 들지 않는다.

Type erasure

꺼림칙하니 코드를 바꾸어 보자.

public class MyList<E> {
  private static final int DEFAULT_CAPACITY = 10;
  private E element[];
  private int index;

  public MyList() {
    element = new E[DEFAULT_CAPACITY];
  }

  public void add(E e) {
    this.element[index++] = e;
  }

  public E get(int index){
    return element[index];
  }
}

Object 타입을 제거하고 E 타입으로 변경하였다. 그러고 나니 get() 메서드에 캐스팅하는 부분이 사라졌다. 깔끔하다. 하지만 안타깝게도 이코드는 동작하지 않는다. 아니 컴파일 조차 되지 않는다. (필자가 그렇게 한 이유가 다..) 컴파일 에러가 발생하는 부분은 다음과 같다.

element = new E[DEFAULT_CAPACITY];

어떤 에러인지 IDEA에서 살펴보면 Type Parameter 'E' cannot be instantiated directly 이와 같은 에러가 발생한다. 타입파라미터 E는 직접적으로 인스턴스화 할 수 없다. 엥 이건 또 무슨 말인가? 왜 타입파라미터는 인스턴화 할 수 없을까?
그 이유는 눈치빠른 사람들은 알겠지만 소 제목에 있다시피 type erasure 때문이다. 그렇다면 type erasure란 뭘까?

자바에서는 제네릭 클래스를 인스턴화화 할 때 해당 타입 타입을 지워버린다. 그 타입은 컴파일시까지만 존재하고 컴파일된 바이트코드에서는 어떠한 타입파라미터의 정보를 찾아볼 수 없다. 필자 말이 진짜인지 한번 살펴보자.

List<Integer> numbers = new ArrayList<>();

//기타 생략

아까 사용했던 List를 바이트 코드 레벨에서 한번 살펴보자.

L0
LINENUMBER 11 L0
NEW java/util/ArrayList
DUP
INVOKESPECIAL java/util/ArrayList.<init> ()V
ASTORE 1

//기타 생략

보시다시피 ArrayList를 생성할 때 어떠한 타입정보도 들고 있지 않다. new ArrayList()로 생성한 것과 동일하게 바이트 코드가 생성된다.
그럼 자바가 이렇게 한 이유는 무엇일까? 이유는 단 한개 밖에 없는 듯하다. (물론 다른 이유도 있을 수 있겠지만 필자 추측에는) 당시 특히나 자바는 하위 호환성을 매우 중요시했다. 그래서 위와 같은 결정을 내린듯 하다. 그래서 제네릭을 사용한 java5에서 컴파일된 코드를 java4에서도 실행 시킬수 있고 제네릭을 사용하지 않았던 레거시 코드들도 java5이상에서 무사히 잘 실행 될 수 있었던 이유이다.
그래서 우리는 아래와 같은 코드들를 만들 수 없다.

if(numbers instanceof List<Integer>) {

}

List<Integer>.class

타입파라미터와 Object

그럼 타입파라미터가 있는 클래스를 컴파일 해보면 어떨까? 어떠한 타입으로 변환을 시켜야 되는데 그 어떠한 타입은 무엇일까?
그건 바로 Object 타입으로 변경시킨다.

class Node<T> {
  private T data;
  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }
}

위와 같이 Node라는 클래스에 타입파라미터가 존재 한다고 가정하자. 그럼 자바 컴파일러는 아래와 같이 변경한다.

class Node {
  private Object data;
  public Object getData() {
    return data;
  }

  public void setData(Object data) {
    this.data = data;
  }
}

그렇다면 만약 타입파라미터에 범위를 제한한다면 어떨까? 아래와 같이 Comparable을 상속받은 클래스만 가능하다고 해보자.

class Node<T extends Comparable<T>> {

  private T data;

  public T getData() {
    return data;
  }

  public void setData(T data) {
    this.data = data;
  }
}

만약 위와 같이 작성된 코드라면 아래와 같이 변경 된다.

class Node {

  private Comparable data;

  public Comparable getData() {
    return data;
  }

  public void setData(Comparable data) {
    this.data = data;
  }
}

참 자바 컴파일러는 열심히도 일한다..

이렇게 오늘은 자바의 제네릭에 대해서 살펴봤다. 위와서 봤던 클래스에도 타입파라미터를 사용할 수 있지만 메서드에도 사용할 수 있다. 또한 바로 위에서 봤던 제네릭에 범위를 제한 할 수도 있다. 이건 예전에 글쓴게 있는데.. 어디 있더라..
제네릭 제한 여기에 보면 허접하지만 간단하게 제네릭 제한에 관련된 글이 있으니 참고 하면 되겠다.

위의 예제만 보고 쉽다고 생각하면 큰 오산일지 모른다. 인터넷에 많은 예제도 살펴보고 제네릭을 많이 사용한 라이브러리를 참고히면 더욱 많은 도움이 될 수 있을 듯 하다.

미리보는 java9

오늘은 미리보는 java9의 새로운 기능들을 살펴보자. 물론 지금은 릴리즈전이라 바뀔 내용이 있을 수 있으니 너무 깊게는 살펴보지 말자.

조만간 java9가 릴리즈 될 예정이다. 원래 일정은 올해 초에 릴리즈 될거라고 했었는데 일정이 밀렸다. 왜 밀린지는 모르겠지만.. 아무튼 담달 27일인 7월27일에 다시 릴리즈 예정일이다. 역시 또 밀릴지는 의문이다.
(수정) 또 다시 딜레이 되었다고 한다. 릴리즈 일정은 아래와 같다.

2017/07/06      Final Release Candidate
2017/09/21      General Availability

그전에 안타까운 소식이 하나 있다. java7부터 언급이 많이 되었던 직소(Jigsaw) 프로젝트가 JCP에 통과하지 못하는 일이 발생하였다. 대부분의 회사들이 반대표를 던졌다. oracle, intel , Azul Systems등이 찬성표를 던졌으나, 이클립스 재단, IBM, 트위터, 레드햇(개빈 킹이겠지?) 등 이 반대표를 던저 23개 회사중 13개의 회사가 반대를 하였다.
그래서 한달이내로 다시 리뷰를 받아야 되는데 해결할 일이 많다고 한다. 그 한달이 거의 다 된거 같은데.. 조만간 소식이 들릴듯 하다. 그래서 여기서는 직소(Jigsaw)는 언급하지 않겠다. 양도 꽤 있어서 만약 java9에 들어간다면 그때 다시..

Collections 의 팩토리 메서드

List에는 Arrays 클래스에 존재 했던거지만 List 인터페이스에 새로운 팩토리메서드가 추가로 생겼다.

List.of(1,2,3,4,5);

위와 같이 간단하게 팩토리 메서드를 호출해서 생성할 수 있다. 메서드 형태들는 다음과 같다.

static <E> List<E> of(E e1) 
static <E> List<E> of(E e1, E e2)
static <E> List<E> of(E e1, E e2, E e3)
...
static <E> List<E> of(E... elements)

List에만 생겼다면 그닥 의미가 별로 없었을 것이다. 하지만 Set, Map에도 추가 되었다.

Set.of(1,2,3,4,5);
Map.of("key1", "value1", "key2","value2");

Set의 경우에는 중복을 허용하지 않는다. 그래서 만약 같은 값을 넣을 경우에는 에러를 발생시킨다.

Set.of(1,2,3,4,1);

... java.lang.IllegalArgumentException: duplicate element: 1
...

또 한 Map도 키는 중복을 허용하지 않는다. 그래서 Set과 마찬가지로 같은 키값을 넣을 경우 에러를 발생시킨다.

Map.of("key1", "value1", "key1","value2");

참고로 위에 모든 컬렉션은 immutable하다. 변경할 수 없다. 만약 List.of()로 생성하고 add() 메서드를 호출하면 UnsupportedOperationException 이 발생한다.

좀 더 쉽게 Set과 Map을 사용할 수 있어서 괜찮은거 같다.

Stream API

Stream에 몇가지 API가 추가 되었다. takeWhile(), dropWhile(), ofNullable()가 추가 되었다.

takeWhile

takeWhile() 의 메서드 형태는 다음과 같다.

default Stream<T> takeWhile(Predicate<? super T> predicate)

이 아이는 특정한 엘리먼트까지 왔다면 멈추고 그 엘리먼트까지 반환한다. Predicate을 파라미터로 받으니 boolean 값을 리턴하면 된다.

List<Integer> numbers = List.of(1, 3, 7, 8, 15, 4)
        .stream()
        .takeWhile(i -> i < 10)
        .collect(toList());

filter와 유사하다. 하지만 filter와 다른점은 해당 조건까지 왔다면 멈추고 반환한다는 것이다. filter와 비교해보자.

List<Integer> numbers = List.of(1, 3, 7, 8, 15, 4)
        .stream()
        .filter(i -> i < 10)
        .collect(toList());

filter를 사용했을 경우에는 1, 3, 7, 8, 4를 반환하는 반면에 takeWhile를 사용할 경우에는 1, 3, 7, 8까지 데이터를 반환한다.

dropWhile

dropWhile 의 메서드 형태는 다음 과 같다.

default Stream<T> dropWhile(Predicate<? super T> predicate)

dropWhile() 메서드는 takeWhile() 메서드와 반대 개념이다. takeWhile()메서드가 1, 3, 7, 8를 반환하였다면 dropWhile() 메서드는 나머지인 15, 4를 반환한다.

List<Integer> numbers = List.of(1, 3, 7, 8, 15, 4)
        .stream()
        .dropWhile(i -> i < 10)
        .collect(toList());
//[15, 4]

ofNullable

ofNullable의 메서드 형태는 다음 과 같다.

public static<T> Stream<T> ofNullable(T t) 

ofNullable() 메서드는 Optional.ofNullable() 과 동일하다. null safe한 메서드 이다.

Stream.ofNullable(null)

위와 같이 작성해도 에러는 발생하지 않는다.

Optional API

Optional에도 몇가지 API가 추가 되었다. stream(), or(), ifPresentOrElse() 메서드가 추가되었다.

stream

메서드 명 그대로 Optional을 Stream 타입으로 변경하는 메서드 이다. 메서드 형태는 다음과 같다.

public Stream<T> stream()

Optional 타입을 만들어서 stream 형태로 만드는 예이다.

Optional<String> foo = Optional.ofNullable("foo");
Stream<String> stream = foo.stream();

or

or 메서드는 기존의 orXXX 와 비슷한 메서드이다. or 메서드 경우에는 Optional을 다시 리턴한다. 메서드 형태는 다음과 같다.

public Optional<T> or(Supplier<? extends Optional<? extends T>> supplier)

Supplier에 Optional 타입을 받고 Optional을 리턴한다.

Optional<String> foo = Optional.ofNullable("foo");
Optional<String> bar = foo.or(() -> Optional.of("bar"));
// Optional[foo]
Optional<String> foo = Optional.ofNullable(null);
Optional<String> bar = foo.or(() -> Optional.of("bar"));
// Optional[bar]

ifPresentOrElse

기존의 ifPresent(Consumer<? super T> action) 메서드 형태에서 조금 확장된 형태이다. ifPresent() 메서드 경우에는 값이 있을 경우에만 동작하지만 ifPresentOrElse() 메서드 경우에는 값이 없을 경우에도 동작하는 부분이 추가 되었다.
메서드 형태는 다음과 같다.

public void ifPresentOrElse(Consumer<? super T> action, Runnable emptyAction)

Runnable을 파라마터로 받는 부분이 추가 되었다.

Optional<String> foo = Optional.ofNullable("foo");
foo.ifPresentOrElse(f -> System.out.println(f), () -> System.out.println("bar"));
// foo

Optional<String> foo = Optional.ofNullable(null);
foo.ifPresentOrElse(f -> System.out.println(f), () -> System.out.println("bar"));
// bar 

Process

ProcessHandle 인터페이스가 추가 되었다. Process관련된 정보들을 쉽게 가져올 수 있다.

ProcessHandle processHandle = ProcessHandle.current();
ProcessHandle.Info processInfo = processHandle.info();
long pid = processHandle.pid();
System.out.println(pid);
System.out.println(processInfo.command().get());
System.out.println(processInfo.startInstant().isPresent());
System.out.println(processInfo.totalCpuDuration().isPresent());

간단한 인터페이스이기 때문에 한번씩 해보면 될 듯 싶다.

interface

우리가 아는 java의 interface를 말하는 거 맞다. java8 부터 인터페이스에 구현을 할 수 있게 된건 누구나 아는 사실이다.

interface SomeInterface {
    default void doSomething() {
              System.out.println("blabla");
    }
}

위와 같이 interface에 default라는 키워드를 사용해서 구현을 할 수 있다. java9 부터는 메서드에 private 접근제한을 둘수 있다.

interface SomeInterface {

    private void doSomething(){
              System.out.println("blabla");
    }
}

나쁘지 않다. 하지만 protecteddefault 접근제한은 사용할 수 없다.

Reactive

요즘 대두가 많이 되고 있는 Reactive API가 java9에 추가 되었다. 그 구현체 중 Netflix의 rxJava와 Spring의 Reactor 라는 프로젝트가 그 대표적인 예 이다. 자세한 내용은 rxJava와 Reactor라는 프로젝트를 참고하면 되겠다. 필자의 경우에는 Spring을 자주 사용하니 Spring 관련해서 Reactor를 공부할 듯 싶다. Spring5 에서 정식으로 Reactive를 지원하니 Spring5가 나올 때까지 슬슬 공부하면 될 것 같다. Spring boot는 2.0 부터 지원하니 현재 M1 버전으로 공부해도 될 듯 싶다.
그리고 java9가 나오면 java9 쪽으로 인터페이스를 바꾸지 않을까 생각된다. 그냥 필자 생각이지만..
Reactive 또한 이야기 할 것도 많고 쉬운 내용도 아니니 나중에 좀 더 공부를 한뒤에 글을 작성해보도록 하자.

좀 더 많은 내용이 있겠지만 필자가 알아본 정도는 여기까지이다. java9가 릴리즈 되면 차근차근 좀 더 알아볼 수 있도록 하자. 회사에서 사용하려면 좀 더 안정화 되면 사용해야겠지만 개인적으로는 릴리즈 되면 바로 올려서 사용할 예정이다.
직소가 JCP 리뷰에 통과해서 java9에서 만났으면 좋겠다. java7부터 고생이 많다..

위의 예제들을 간단하게 만들었는데 github에서 살펴보자.

Java의 HashMap

오늘은 java의 hashMap에 대해서 알아보자. java에서 자주 사용되는 HashMap은 아주 오래전부터 있던 API이다. 자바8까지 오면서 많은 변화가 있었겠지만 필자는 java8 기준으로 살펴보도록 한다.
참고로 이 글은 http://d2.naver.com/helloworld/831311 참고하면서 정리하는 의미로 남기는 것이다.

수학적인 의미 map

map (mapping)은 원래 수학 함수에서 대응 관계를 지칭하는 용어이다. HashMap은 키 집합인 정의역과 값 집합인 공역의 대응에 해시 함수를 이용한다. 위의 링크의 (그림 1)

HashMap과 Hashcode

HashMap은 빠르다. 내부적으로 배열은 사용해 빠른 속도를 지니고 있다. 배열을 사용해 인덱스를 접근하므로 시간복잡도는 O(1)로 아주 빠르다. 하지만 내부적으로 배열의 인덱스는 무엇으로 결정할까? 그냥 대충 인덱스를 만들어서 증가 시킬까? 만약 그렇다면 값을 어떻게 가져올까? 빠르게 가져올수나 있을까? 설사 만약 그런다면 이 글을 쓸 필요가 없을 것이다. 여기서 중요한 것은 인덱스를 만드는 과정이다. 이 과정은 보통은 해시 함수를 이용해 인덱스를 만들고 이 메서드가 고유한 데이터를 반환하는데 그 값을 hashCode라고 한다. 자바에서 다들 아시다시피 Object클래스의 hashCode() 메서드를 이용하면 된다.

만약 Integer, Long, Float, Double등 Number 객체들은 각자가 나타내려는 값을 해시 자체로 사용할 있기에 완전한 해시 함수를 만들수 있는 반면에 String 이나 기타 다른 Object(혹은 POJO)등은 완전한 해시 함수를 만들어내기 사실상은 불가능하다고 할 수 있다. java의 hashCode() 메서드는 int를 리턴한다. 논리적으로는 2^32까지만 각기 다른 해시함수를 만들수 있고 그 이상은 충돌이 일어나는데 이것을 Collision이라 부른다. (혹은 그전에 날 수도 있다.) 그래서 사실상 완벽한 해시 함수는 불가능하다고 표현한듯 하다.

해시 충돌

hash 함수를 아주 간단하게 구현해볼 수 있는데 그 원리는 나머지 연산을 이용하는 것이다. 일단 공식부터 살펴보자.

int index = X.hashCode() % M;  

메모리를 절약하고 위해 해시 함수의 표현정수보다 작은 M개의 원소가 있는 배열만을 사용한다. 예를들어 보자.

2, 4, 6, 8, 10, 12, 14, 16, 18

만약 위와 같은 해시 코드가 있다고 있다고 생각해보자. 그럼 위의 공식을 적용해서 인덱스를 만들어보자.

2 % 10 = 2
4 % 10 = 4
6 % 10 = 6 
8 % 10 = 8
10 % 10 = 2
12 % 10 = 4
14 % 10 = 6
16 % 10 = 8
18 % 10 = 2
20 % 10 = 4

위를 보시다시피 2, 4, 6, 8이 중복으로 발생한다. 위의 알고리즘으로는 1/M 확률로 같은 해시 버킷을 사용하게 된다.
이런 충돌은 피하기 위해선 아주 간단한 방법이 있는데 길이보다 큰 소수를 찾아서 값을 계산하면 된다.

2 % 11 = 2
4 % 11 = 4
6 % 11 = 6 
8 % 11 = 8
10 % 11 = 10
12 % 11 = 1
14 % 11 = 3
16 % 11 = 5
18 % 11 = 7
20 % 11 = 9

이렇게 되면 아까보다는 좀 더 충돌을 회피 할 수 있다. 하지만 이걸로도 모든걸 해결할 수는 없다. 중간에 1, 3, 7, 9 .. 등이 끼워들면 동일하게 해시 충돌이 일어난다.

해시함수를 아주 잘 구현했다고 하더라도 충돌은 일어나기 마련이다. 하지만 충돌이 일어나더라도 키-값을 잘 저장하고 조회할 수 있어야 되는데 그 대표적인 방법으로는 Open AddressingSeparate Chaining 방법이 있다. 이외에 해시 충돌 알고리즘은 더 다양하지만 거의 이 둘을 응용해서 만든거라고 할 수 있다.
java의 경우에는 Separate Chaining 사용하니 Open Addressing은 언급하지 않겠다. 궁금하면 인터넷에..맡기도록..

해시 충돌과 Separate Chaining

링크 (그림2)를 오른쪽이 Separate Chaining 알고리즘이다. 각 배열의 인자는 인덱스가 같은 해시 버킷을 연결한 링크드 리스트의 첫 부분(head)이다. Open Addressing경우에는 삭제에 적합하지 않다. java의 hashMap의 경우에는 remove() 메서드가 빈번하게 호출되므로 Separate Chaining을 선택한 것으로 보인다. 또한 HashMap에 저장된 키-값 쌍 개수가 일정 개수 이상으로 많아지면, 일반적으로 Open Addressing은 Separate Chaining보다 느리다고 한다.

잠깐 언급했는데 Separate Chaining는 버킷을 링크드 리스트로 구현했다. 그래서 삽입, 삭제에 용이하다. 하지만 검색에는 용이하지 않다. 그래서 java8에서는 데이터 개수가 많아지면 Separate Chaining 구현을 링크드 리스트에서 트리로 변경한다. 버킷에 데이터가 많을 수록 트리로 구현하는 것이 성능상 이점이 있다.

Red-Black Tree

링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다.
HashMap에 보면 TREEIFY_THRESHOLD 상수가 존재한다. 이 기준이 링크드 리스트에서 트리로 변경하는 기준이다. 하지만 만약 데이터 개수가 6개로 된다면 다시 트리에서 링크드리스트로 변경한다. 그 이유는 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행 시간 차이 비교는 의미가 없기 때문이다. 8과 6으로 2 이상의 차이를 둔 것은, 만약 차이가 1이라면 어떤 한 키-값 쌍이 반복되어 삽입/삭제되는 경우 불필요하게 트리와 링크드 리스트를 변경하는 일이 반복되어 성능 저하가 발생할 수 있기 때문이다.

static final int TREEIFY_THRESHOLD = 8;

static final int UNTREEIFY_THRESHOLD = 6;  

트리로 변경될 때 사용하는 트리는 Red-Black Tree라고 불리는데 java의 TreeMap과 구현이 거의 동일하다. 해당 클래스는 HashMap안에 존재한다.

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
  //...
}

해시 버킷 동적 확장

해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 키-값 쌍 데이터 개수가 일정 개수 이상이 되면, 해시 버킷의 개수를 두 배로 늘린다. 해시 버킷 개수의 기본값은 16이고, 데이터의 개수가 임계점에 이를 때마다 해시 버킷 개수의 크기를 두 배씩 증가시킨다.


final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //.. if (++size > threshold) resize(); //.. } final Node<K,V>[] resize() { // ... }

최초와 특정 개수보다 hashMap에 사이즈가 커지면 resize() 통해 증가시킨다. 위는 HashMap의 일부분이다.

동일한 해시코드

만약 동일한 해시코드를 작성한다면 어떻게 될까?

@Override
public int hashCode() {
  return 42;
}

이렇게 된다면 결국 같은 버킷에 해시되어 해시 테이블은 연결 리스트 혹은 트리가 되어 버린다. 그래서 저장한 데이터가 많으면 많을 수록 속도로 현저히 떨어진다. 한번 테스트 해보도록 하자.

public static void main(String[] args) {
  long start = System.currentTimeMillis();
  Map<Hash, String> map = new HashMap<>();
  for (int i = 0; i < 10000; i++) {
    map.put(new Hash("" + i), "value" + i);
  }
  System.out.println(map.get(new Hash("9999")));
  System.out.println(System.currentTimeMillis() - start);
}

class Hash {
  private String id;

  public Hash(String id) {
    this.id = id;
  }

  @Override
  public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Hash hash = (Hash) o;
    return id != null ? id.equals(hash.id) : hash.id == null;
  }

  @Override
  public int hashCode() {
    //return id != null ? id.hashCode() : 0;
    return 42;
  }
}

해시코드를 구현한 것과 동일하게 해놓은 것과 비교를 해보자. 필자의 컴터는 느려서 저정도만 해도 심각하게 차이가 난다.

참고로 Set 구현체 중 HashSet도 동일하다. 왜냐하면 HashMap을 사용했기 때문이다.

이렇게 오늘은 HashMap와 hashcode에 대해서 살짝 살펴봤다. 필자는 중요하다고 생각되는 부분만 정리한 것이므로 만약 정보를 더 얻고 싶다면 링크한 페이지에 가서 살펴보면 되겠다. 좀 더 자세하게 설명을 해주셨으니 참고하면 되겠다. 거의 대부분은 글을 그대로 인용했지만 많은 도움이 되었다.