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

의존 역전 원칙

아주 저번시간 인터페이스의 분리 원칙에 이어 오늘은 의존 역전 원칙에 대해서 알아보자. 원래는 단일책임원칙에 대해서 하려고 했는데 적당한 예제가 생각나지 않아서 적당한 예제가 생각날때 까지 잠시 보류..

의존 역전 원칙 (DIP)

의존 역전 원칙이란 다음과 같다

고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다. 저수준 모듈이 고수준 모듈에서 정의한 추상 타입에 의존해야 한다.

흐으음.. 이게 무슨말인가? 고수준 모듈은 무엇이며 저수준 모듈은 또 무엇인가?..
일단 고수준 모듈과 저수준 모듈에 대해서 살펴보자. 고수준 모듈은 어떤 의미가 있는 단일 기능을 제공하는 모듈이라고 생각하면되고, 저 수준 모듈은 고수준 모듈의 기능을 구현하기 위해 필요한 하위 기능을 실제로 구현한 것으로 정의 할 수 있다.

좀 더 풀어서 이야기 해보자.
예를들어 만약에 어떤 바이트 데이터를 읽어와 특정한 데이터로 결과를 반환하는 것으로 이야기를 해보자.

  1. 고수준 모듈
    • 바이트 데이터를 읽어 와서 특정한 데이터로 결과를 반환한다.
  2. 저수준 모듈
    • 파일에서 바이트 데이터를 읽어 온다.
    • Json 데이터로 결과를 반환한다.

이렇게 저수준 모듈은 좀 더 구체적인 구현을 어떻게 할지에 대한 내용을 다루는 것이다.
코드를 보며 좀 더 살펴보도록 하자.

public class Response {

  private JsonConverter jsonConverter = new JsonConverter();

  public String response()  {
    byte[] bytes = null; //파일은 생략
    return jsonConverter.convert(bytes);
  }

}

class JsonConverter {

  public String convert(byte[] bytes) {
    //json ...
    return "json";
  }
}

위는 DIP 원칙을 어기고 있는 코드이다. 아까 말했듯이 고수준 모듈은 저수준 모듈의 구현에 의존해서는 안된다. 저수준 모듈이 고수준 모듈에서 정의한 추상 타입에 의존해야 한다. 를 어기고 있다. 다시 말해 고수준모듈인 Response 는 저수준 모듈인 JsonConverter 구현에 직접적으로 의존하고 있다. 좀 더 DIP 원칙을 해결하기 위한 코드를 작성 해보록 하자.

public class Response {

  private Converter converter = new JsonConverter();

  public String response() {
    byte[] bytes = null; //파일은 생략
    return converter.convert(bytes);
  }

}

interface Converter {

  String convert(byte[] bytes);

}

class JsonConverter implements Converter {

  @Override
  public String convert(byte[] bytes) {
    //json ...
    return "json";
  }
}

Converter 라는 인터페이스를 생성후에 JsonConverterConverter를 구현하였다. 그렇게 되므로써 JsonConverterConverter를 의존하고 있게 된다.
만약 요구사항이 변경되어 xml로 데이터를 반환해야 한다면 XmlConverter클래스를 만든 후에 갈아 끼우면 된다.

public class Response {

  private Converter converter = new XmlConverter();

  public String response() {
    byte[] bytes = null; //파일은 생략
    return converter.convert(bytes);
  }

}

class XmlConverter implements Converter {

  @Override
  public String convert(byte[] bytes) {
    //xml ...
    return "xml";
  }
}

이렇게 우리는 손쉽게 원하는 형식의 데이터를 자유자재로 반환할 수 있게 되었다. 하지만 만약에 Response를 라이브러리로 배포를 한다면 말이 좀 달라진다. 각각의 스타일에 맞게 매번 배포를 해야한다. 왜냐하면 아직까지 Response 에는 구체적인 클래스인 JsonConverterXmlConverter를 의존하기 때문이다.

DI (의존성 주입)

우리는 해결할 문제가 남아있다. 아직도 구체적인 클래스인 JsonConverterXmlConverterResponse가 의존하고 있기 때문이다. 이것을 해결하기 위해 우리는 의존자 모듈에 의존성 모듈 인스턴스를 제공하면 되는데 이것이 의존성 주입이다.

생성자 주입 (Constructor Injection)

필자는 항상 사용하는 주입 방식이며 필자가 항상 사용하는 Spring도 권장하는 주입 방식이다. 의존자 인스턴스 생성됨과 동시에 생성되므로 좀 더 안전하게 사용할 수 있는 장점이 있다. 의존관계가 명확해서 누락될 시 에는 컴파일 에러가 나므로 필자도 추천하는 방식이다.

public class Response {

  private final Converter converter;

  public Response(Converter converter) {
    this.converter = converter;
  }
}

속성 주입 (Property Injection)

흔히 Spring에서는 setter 주입이라고 한다. 필수가 아닌 옵션의 형태의 의존성을 갖고 있을 때 사용하면 될 듯 싶다. 필자도 가끔 사용하는 주입 방식이다. 인스턴스가 생성후에 진행되어 만약 필요하다면 의존성을 체크도 해야 되는 부분이 있을 수 있다.

public class Response {

  private Converter converter;

  public void setConverter(Converter converter) {
    this.converter = converter;
  }
}

인터페이스 주입(Interface injection)

솔직히 써본적이 없어서 글을 남길 수 없다.. 필요하다면 자세한 내용은 인터넷에서 찾아보길 권장하며 필자 생각는 사용할 일이 없어서 찾아보지도 않았..

필드 주입 (Field Injection)

이건 솔직히 딱히 권장하지 않는 방법이고 일반적인 DI라하면 필드 주입은 없는 걸로 알고 있다. 하지만 JEE 스펙에는 버젓이 필드 주입이 있다. 그리고 Spring이나 구글주스나 여타 프로임워크에서 지원해주는 것이지 실제로 프레임워크 없이 사용하려면 리플렉션을 통해 접근 해야 되지 않나 싶다. 필자는 되도록이면 생성자 주입을 자주 사용한다.

이렇게 됨으로써 JsonConverterXmlConverter은 상세 구현에서 Converter를 의존한다는 것을 알 수있다. 이는 고수준 모듈이 저수준 모듈에 의존했던 상황이 역전되어 저수준 모듈이 고수준 모듈에 의존하게 된다는 것을 의미해 이것을 의존 역전원칙이라고 부른다.

여기서 또 중요한 것은 DIP(Dependency Inversion Principle)DI(Dependency Injection)는 다르다. 실제 DI(Dependency Injection)는 DIP(Dependency Inversion Principle) 을 구현하는 기법중 한개일 뿐이다. DIP를 구현하는 다른 기법은 서비스 로케이터(Service Locator)라고 불린다. 이것은 필자도 아직 잘 모르기에 기회가 된다면 공부후에 포스팅을 해보겠다. DIP가 상위 개념이라고 생각하면 될 듯 싶다.

오늘은 이렇게 어려운 DIP에 대해서 공부해봤다. 실제 DIP를 적용하면 나중에 다룰 개방폐쇄 원칙과 리스코프 치환 원칙을 따르게 만들어주는 기반이 된다.

내용이 쉬운거 같으면서 쉽지 않은 내용이다? 나름 쉽게 작성한다고 했는데..

java는 call by value? call by reference?

오늘도 역시 java에 대해서 이야기 해볼려고 한다. java로 먹고 살아야 하니..

call by value와 call by reference

오늘 내용은 제목에도 있다시피 java는 call by value?, call by reference? 를 알아볼 예정이다. 그 전에 아주 간단하게 call by value와 call by reference에 대해서 살짝 살펴보자. 보통 c 보다 자바를 먼저 공부한 개발자는 들어본 개발자도 있을 것이고 듣지 못한 개발자도 있을 수 있다. 왜냐하면 책에서 딱히 다루지 않기 때문이다. 필자도 자바책에서는 거의 못본.. 사실 자바만 다루는책은 두권정도밖에 없다. 그래서 못본거일 수도.. 하지만 c와 c++을 먼저 공부를 했다면 무조건 등장한다. 잠시 c언어 책을 꺼내고 살펴보도록 하자.

call by value (값에 의한 호출)

call by value는 가장 일반적인 함수 호출형태로 값을 복사하는 것이다. 예를 들어 보자.

int add(int a, int b) 
{
    return a + b;
}

c 의 함수의 기본적인 형태이다. (혹시 다음에 나올 문법이 c++이라도 그냥 c라고 이야기 하겠다.) add 메서드를 호출하면 a + b를 더한 값을 리턴한다. 호출 해보자.

int a1 = 10;
int a2 = 20;
cout << add(a1, a2) << endl;

값은 당연히 30이 출력 될 것이다. 여기서 변수 a1과 a2는 add() 함수의 a, b와는 완전 별개의 변수가 된다. 즉 값이 복사되는 것이다. 그래서 만약 add 함수의 a와 b를 변경 하더라도 a1와 a2는 영향을 받지 않는다. 뭐 당연한 말을 이렇게 하나 싶은데 좀 더 살펴보자.

call by value와 call by reference가 나오면 단골로(?) 나오는 예제를 살펴보자. 예상했겠지만 swap함수를 만들어보자.

void swap(int a, int b)
{
    int temp = a;
    a = b;
    b = temp;
}

뭐 어려운 부분은 없다. 두 변수를 바꾸는 함수이다. 한번 호출해보자.

int a1 = 10;
int a2 = 20;
swap(a1, a2);
cout << "a1: " << a1 << " a2: " << a2 << endl;

출력 해보면 a1: 10 a2: 20 이와 같이 출력 될 것이다. 아까 위에서 a1과 a는 별개의 변수인 것이 증명 되었다. 뭔 당연한 소리를 이렇게 길게 이야기 하고 있어? 라고 할 수도 있으니 빨리 다음으로 넘어가자.

call by reference (참조의 의한 호출)

call by reference 를 자세히 이야기하면 글이 너무 길어지므로 간단하게만 이야기 해보자. 포인터에 대해서도 잘알고 해야되는데 여기에서는 그게 중요한 내용이 아니므로 모르는 사람이 있다면 그냥 이런게 있다고만 알고 있자.

간단하게 한줄로 요약하자면 변수의 주소를 전달하는 것이다. 다시 swap 함수를 call by reference 로 만들어보자.

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int a1 = 10;
int a2 = 20;
swap(&a1, &a2);
cout << "a1: " << a1 << " a2: " << a2 << endl;

호출하면 아까 위의 call by value 와는 다르게 a1: 20 a2: 10 두개의 변수가 바뀌어 출력 된다. 이게 바로 call by reference 참조의 의한 호출이다. 포인터 변수 a와 b에는 각각의 a1의 주소 a2의 주소가 전달된다. call by value 처럼 값을 복사하는 것이 아니고 실제 주소를 전달하여 swap 함수 내에서 조작을 하면 실제 값도 변경 될 수 있는 것이다.

이정도면 아주 정확히는 몰라도 어느정도 두개의 차이점을 알아봤다. 그렇다면 과연 java는 call by reference 일까?

java는 call by reference가 아니다.

결론부터 말하자면 java는 항상 call by value이다. 흔히 java의 오해를 살 수 있는 부분을 살펴보자.

public class CallByValue {

  public static void main(String[] args) {
    Person p = new Person("wonwoo");
    System.out.println("p.name: " + p.name);
    callByValue(p);
    System.out.println("p.name: " + p.name);
  }

  public static void callByValue(Person p) {
    p.name = "kevin";
  }
}

class Person  {
  String name;

  public Person(String name) {
    this.name = name;
  }
}

위의 코드를 출력해보면 아래와 같이 출력 된다.

p.name: wonwoo
p.name: kevin

읭? 바뀌었는데? 그럼 자바도 call by reference가 아닐까? 오해의 소지는 여기서 발생했다. 실제 상태값을 바꾸는 것에서 오해가 시작되었다. call by reference라면 상태를 변경하는게 아니라 실제 callByValue 함수의 p에 다른 Person 객체를 넣어 바뀐다면 그게 call by reference가 되는 것이다. 다음과 같이 말이다.

public class CallByValue {

  public static void main(String[] args) {
    Person p = new Person("wonwoo");
    System.out.println("p.name: " + p.name);
    callByValue(p);
    System.out.println("p.name: " + p.name);
  }

  public static void callByValue(Person p) {
    p = new Person("kevin");
  }
}

class Person  {
  String name;

  public Person(String name) {
    this.name = name;
  }
}

callByValue 메서드부분만 바뀌었다. callByValue 메서드를 보면 이름을 kevin으로 다시 생성해서 할당한다. 만약 자바가 call by reference라면 아까와 동일하게 출력 되어야만 한다. 하지만 이 코드를 출력해보면 다음과 같다.

p.name: wonwoo
p.name: wonwoo

실제로 Person은 변경되지 않았다. call by reference가 아닌 또다른 이유는 자바에서는 객체의 주소를 가져오는 방법이 없다. 만약 call by reference 지원한다면 주소를 가져오는 방법을 지원해야 할 것인데 말이다.

그럼 우리는 call by reference가 어떤건지 보자. c는 call by reference 를 지원하니 c코드를 보자. 정확히는 c++.. 오랜만에 c로 코딩할려니 문법조차 다 까먹었다.. Xcode도 거의 4년? 5년만에 열었..

#include <iostream>

using namespace std;

class Person 
{

    public :
    string name;

    Person (string name) {
        this->name = name;
    }
};

int add(int a, int b)
{
    return a + b;
}

void callByReference(Person *p)
{
    *p = Person("kevin");
}

void callByValue(Person p)
{
    p = Person("kevin");
}

int main(int argc, const char * argv[]) 
{
    Person p("wonwoo");
    cout << "p.name: " << p.name << endl;
    callByReference(&p);
//    callByValue(p);
    cout << "p.name: " << p.name << endl;
    return 0;
}

아까 자바와 동일하게 만들었다. 실제 callByReference() 함수를 호출하면 실제 바뀐 내용이 출력 되지만 callByValue() 함수를 호출할 경우에는 자바와 동일하게 wonwoo가 두 번 출력 된다. 이로써 java는 call by reference가 아니라는게 증명? 되었을 것이라고 생각된다.

오늘은 이렇게 자바의 call by value와 call by reference(?) 에 대해서 알아봤다. 만약 call by value와 call by reference에 대해서 더 자세히 알고 싶다면 인터넷으로 찾길 바란다. 필자는 역량은 여기까지다.. ㅜㅜ
자바가 call by reference라는 오해를 할 수 있다. 필자 역시 초보 시절에는 자바가 call by reference가 되는 줄 알았기 때문이다. 어떻게 읽고 쓰냐에 대해서 오해의 소지가 있을 수 있으니 조심해야 될 듯 싶다.

오늘은 여기서 이만..