HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
		...
}

• Map 인터페이스의 구현체이다.
• AbstractMap 을 상속받는다.

HashMap 는 순서가 아닌 수행 시간의 가장 큰 장점을 가지고 있다. add, remove, find 에 평균 O(1) 의 속도를 발휘한다. (TreeMap 은 O(logN) 이다.)

HashMap 은 외부에서 볼 때 항상 같은 형태를 띨 것 같지만, capacity 와 load factor 를 통해 동적으로 변화한다.

capacity 는 해시테이블의 버킷 수이다. load factor 는 해시 테이블의 용량이 자동으로 증가하기 전에 해시 테이블이 얼마나 가득 차도록 허용되는지를 측정한 것이다.

 

이 값을 설정하지 않을 경우 기본값

• initial capacity : 16
• load factor : 0.75

해시 테이블의 항목 수가 load factor 와 현재 capacity 의 곱을 초과하면 resize() 를 통해 해시 테이블을 다시 해시하여 해시 테이블의 버킷 수가 약 2배가 되도록 한다.

해시 테이블에 저장되는 Node

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

동일한 해시코드를 가진 객체일 경우 (해시충돌) 한 버킷에 LinkedList 형태로 추가된다. (next 파라미터에 다음 객체를 저장)

이런 방식을 세퍼레이트 체이닝(Separate Chaining)이라고 한다.

 

 

get() 했을 경우

해당 key 가 있는 버킷에 1개의 노드만 있는 경우 바로 해당 노드의 value 값을 반환한다.

2개 이상의 노드가 있을 경우 첫 번째 노드부터 시작해서 key 값이 같은지 equals() 로 비교한다. 해당 key 값을 가지고 있는 노드를 발견하면 해당 노드의 value 를 반환한다.

 

만약 60만 개의 데이터가 있다면?

bucket 이 16개라면 평균적으로 한 버킷당 1000개의 노드가 저장되며, get() 한 번당 평균 5000번의 equals() 가 실행되어야 한다.

따라서 저장된 데이터 수 > load_factor * capacity 이면 버킷 크기를 2배로 늘리는 것이다.

load factor의 기본값이 0.75라는 말은 ‘한 공간에 저장된 데이터의 평균 수가 0.75개, 즉 1도 안되어서 버킷의 크기를 늘려버린다.’ 라고 해석할 수 있다.

데이터들이 이 공간에 균등하게 퍼져서 저장돼서 한 공간에 저장된 데이터 수 <= 1 이기 때문에 get() 도 빠르게 진행되고, equals() 가 호출되는 경우가 줄어들기 때문이다.

 

capacity 를 크게 잡으면?

• 빈 공간이 많으니 메모리가 낭비된다.
• Iteration (객체의 모든 데이터를 조회해봐야 하는 경우) 성능이 저하된다.
  • Iteration 의 부하는 capacity + 저장된 데이터 수 와 비례하기 때문이다.

load factor가 작으면, 그만큼 capacity가 커지므로 메모리는 많이 차지하지만 검색 속도가 빨라진다.

load factor가 커지면, 그만큼 capacity가 덜 커지므로 메모리는 적게 차지하지만 검색 속도는 느려진다.

→ 만약 자신이 개발하는 애플리케이션이 ‘메모리는 좀 많이 잡아먹어도 괜찮으니 검색 속도가 빨랐으면 한다’ 라고 하면 load factor를 작게 설정하면 된다.

 

HashMap에 저장될 데이터의 수가 짐작 가능하다면 객체를 생성할 때 capacity를 그 값에 맞게 설정해주는 게 좋다.

만약 들어올 데이터 수는 16만 개인데 초기 capacity 를 기본값 16으로 설정한다면 capacity 증가 작업이 매우 많이 일어날 것이기 때문이다.

이 capacity 증가는 bucket의 크기만 증가시키고 끝나지 않는다. capacity 값이 변경됐으니, 기존에 저장되어 있던 모든 데이터의 hashCode() % capacity 값을 다시 계산하고, 그 값에 따른 공간 배치를 새로 다 해야 한다. 이 과정을 rehashing이라고 하는데 이 과정이 부하가 엄청나기 때문이다.

 

따라서, 초기 capacity 값을 설정해주는 것이 중요하다고 볼 수 있다.