Java 에서 자료를 저장하고 검색하기 위해 가장 많이 사용하는 자료구조인 HashMap 이 내부적으로 어떻게 구현 되고 동작하는지 알아보자. 모든 부분은 설명하지 않고 중점적으로 사용되는 부분만을 볼 예정.
먼저 HashMap 에 저장되는 가장 기본적인 자료구조는 key, value 값을 저장하고 있는 Entry 가 있다.
Entry<K,V> {
int hash; //hashMap 내부에서 계산된 hash 값
final K key; // 입력된 key
V value; // 입력된 value
Entry<K,V> next; // linkedList 형태
}
그리고 각 entry 들을 저장하기 위한 array 인 table 이 있다.
Entry<K,V> [] table;
그 외 중요 변수로는
final float loadFactor;
int threshold;
int modCount;
1. put
put() 메소드를 통해 key, value 값이 저장되면 내부적으로 아래와 같은 모습으로 저장된다.
이미지 출처 : https://mkbansal.wordpress.com/2010/06/24/hashmap-how-it-works/
저장되는 순서는 아래와 같다.
1) key 객체의 hashCode() 값을 이용하여 내부적으로 새로운 hash 값을 구한다.
2) 새로운 hash 값을 이용하여 table 배열에서 몇번째 index 에 저장할지 index 를 찾는다. ( indexFor 함수 )
3-1) 구해진 index 에 entry 가 이미 존재하면 linked-list 형태로 연결한다.
3-2) 구해진 index 에 entry 가 없으면 그냥 assign 한다.
4) 만약 key 가 기존에 존재하던 값이면 value 만 replace 하고 이전 value 값을 리턴한다.
2. doubling
위에서도 볼 수 있듯이 hashMap 에서는 entry 를 저장할 수 있는 table 배열의 크기가 정해져 있기 때문에 많은 수의 entry 가 입력되면 collision 이 자주 발생하게 되고 이는 성능저하를 가져오게 된다. 이를 방지하기 위해서 HashMap 은 table 배열의 사이즈를 doubling 하게 된다. ( 배열의 크기는 항상 2의 제곱수를 유지한다 )
1) entry 저장 시 entry 개수가 threshold ( table.size * loadFactor ) 를 넘어서면 table 을 doubling
2) table 사이즈가 커졌기 때문에 기존에 저장된 모든 entry 에 대해서 rehash 를 수행하여 entry 분산
3) table.size 가 maximum_capacity 를 넘어가면 doubling 하지 않음.
doubling 은 기존 배열의 두배 크기의 배열을 새롭게 만들고 기존의 entry 를 rehash 하며 옮겨오는 방식으로 진행된다.
3. indexFor
앞서 설명했듯이 내부적으로 새롭게 계산된 hash 값을 이용하여 table 에 저장된 index 값을 구하게 되는데 이를 위해 indexFor 함수를 호출한다. 일반적으로 table size 만큼 entry 를 분산해야 하기 때문에 modular 방식을 생각할 수 있겠으나 좀 더 효율적인 분산을 위해 아래와 같은 방법으로 구현되어 있다.
static int indexFor ( int h, int length ){
return h & ( length -1 );
}
h 는 hash 값, length 는 table 배열의 size 이다.
table 의 length 는 2의 제곱수이기 때문에 length – 1 은 모든 비트가 1로 채워진 수가 된다. 그 값과 h 값을 & 연산을 통해서 index 값을 구하게 된다. 이런 방식을 취하면 length 값이 두배로 증가하였을때는 상위 하나의 비트가 더 추가된 값과 h 값이 & 연산을 하게 된다. 그 결과는 반드시 기존 index 값과 같거나 doubling 으로 새롭게 추가된 영역의 index 만을 가지게 되기 때문에 좀 더 효율적인 entry 의 분산을 기대할 수 있다.
4. ConcurrentModificationException
HashMap 은 thread-safe 한 자료구조가 아니다. 즉, 특정 thread 가 자료를 읽는 중에도 다른 thread 가 map 내부의 자료를 삭제할 수 있다. 이는 multi-thread 환경에서 분명 문제가 된다. 이같은 문제 때문에 HashMap 에서는 entry 들을 iteration 하는 도중 자료구조에 변경이 일어나면 ConcurrentModificationException 을 발생시켜 해당 문제를 알려준다.
이를 위해서 HashMap 내부에 modCount 라는 변수를 두고 HashMap 의 모든 업데이트의 발생시 modCount 를 증가시켜 준다. 그리고 entry 의 iteration 을 시작하기 전에 modCount 값을 다른 임시 변수에 복사 해 두고 매번 next 호출때 마다 두 변수 값을 비교하여 차이가 발생하면 ConcurrentModificationException 을 발생시킨다
5. get
인자로 받은 key 에 매핑되는 value 값을 찾는 방식은 put 의 방식과 유사하다.
1) key 객체의 hashCode() 값을 이용하여 내부적으로 새로운 hash 값을 구한다.
2) 새로운 hash 값을 이용하여 table 배열에서 몇번째 index 에 저장되어 있는지 찾는다. ( indexFor 함수 )
3-1) 구해진 index 에 entry 의 key 와 동일한 객체인지 equals 를 이용하여 비교하여 동일하면 entry 의 value 를 리턴한다.
3-2) equals 결과가 false 이면 entry 의 next 링크를 계속 따라가며 동일한 key 를 가진 entry 를 찾는다.
일반적인 hash 의 자료구조는 위와 같은 방식으로 구현되어 있다.
주의해서 알아야 할점은 entry 의 개수가 많아지면 doubling 이 자주 일어나고 이 때 새로운 table 을 위한 memory 공간 확보, 기존의 모든 entry 에 대해서 rehash 등으로 인한 오버헤드가 발생한다. HashMap 생성시 entry 의 개수를 미리 예측할 수 있다면 doubling 으로 인한 오버헤드를 줄일 수 있다. 또한 doubling 으로 인한 memory 낭비가 있을 수 있기 때문에 정적인 데이터의 경우 loadFactor 값을 높게 조정해 볼 수도 있을것이다.
minchang's dev note 