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