JAVA] Java.util.HashMap() 분석

원본 출처 : http://iilii.egloos.com/4457500


HashMap은 Object.hashCode()를 이용하는 java.util.Map 인터페이스의 구현체입니다. 대표적인 Map의 구현체입니다. Map의 주요 구현체는 이 외에 Hashtable과 TreeMap이 있습니다. Hashtable은 이 글에서 함께 설명할 것이고, TreeMap의 구현에 대해서는 따로 정리를 하겠습니다.

일단 Map의 기본 컨셉은 Key-Value입니다. 주민등록번호와 개인 정보같은 경우를 생각하시면 됩니다. 어떤 주민등록번호를 입력하면, 그 사람의 개인정보를 볼 수 있도록 하겠다는 겁니다. 맵에 정보를 추가하는 것은 put(K key, V value)로 정의됩니다. K는 Key의 타입이고 V는 Value의 타입입니다. 주민번호의 예를 들자면, K는 주민등록번호 객체가 될 것이고, V는 개인정보 객체가 될 것입니다. 그리고, 맵에서 정보를 조회하는 것은 get(K key)입니다. put(key, value)로 저장이 된 value는 get(key)를 하면 가져올 수 있다는 겁니다.

간단한 코들를 보여드리자면, 아래와 같습니다.

Map<String, String> map = new HashMap<String, String>();
map.put("key", "value");
String b = map.get("key");

위의 코드에서 b는 "value"라는 String을 가집니다.

HashMap과 Hashtable의 큰 차이는 두 가지입니다.
첫째, HashMap은 null키와 null값을 허용합니다. 허나, Hashtable은 허용하지 않습니다.
둘째, HashMap은 synchronized가 없습니다. 하지만 Hashtable은 대부분의 method가 synchronized로 처리가 됩니다.

이제부터는 HashMap을 중심으로 얘기할 것이며, 위에서 얘기한 두 가지 차이점을 제외하고는 Hashtable도 거의 유사하다고 보시면 됩니다.

1. 순서 보장하지 않음

Map 에 보면, keySet()이라는 메쏘드가 있습니다. 어떤 키값들이 들어있는지 알려주는 겁니다. HashMap의 경우 keySet()으로 받아온 데이터는 입력한 순서와 무관하며, 호출할 때마다 순서가 달라질 수도 있습니다. 따라서 어떠한 순서에도 의존해서는 안 됩니다. 입력한 순서대로 데이터를 받아오고자 한다면, LinkedHashMap을 사용하셔야 하며, 정렬된 순서대로 쓰고자 한다면 TreeMap을 써야 합니다.

2. hashCode()와 equals()

put, get에 있어서 모두 hashCode()와 == 연산 및 equals()를 사용합니다. value와는 전혀 상관없고, key에 대해서만 이런 방식을 씁니다. hashCode()를 사용하는 것은 두 가지 의미가 있는데, 첫째는 equals()에 비해 부하가 적다는 것입니다. 두번째는 hashCode() 값을 기준으로 분류가 가능하다는 것입니다. 두번째의 의미가 훨씬 큽니다. 잠시 후 자세히 설명하겠습니다.
일단 hashCode()를 가지고 비교를 하고 == 로 비교해서 true를 리턴하거나 equals()로 비교해서 true를 리턴하는 지 체크해서 기존 element를 덮어 쓸 것인지를 결정합니다.
hashCode()는 java.lang.Object에 정의가 되어 있으며, 여기에 정리가 되어있습니다.

3. bucket

HashMap은 내부적으로 bucket을 사용합니다. bucket은 Map이 가지는 element들을 적당히 분산시켜 놓는 것입니다. Map이 서랍장이라면, bucket은 각각의 서랍이 라고 생각하시면 됩니다. 첫번째 서랍에는 양말이 두번째 서랍에는 티셔츠가 세번째 서랍에는 바지가 있다면 서랍장 전체를 뒤지지 않아도 찾고자하는 것을 찾을 수 있을 겁니다. 즉, "파란 양말"을 찾기 위해서는 양말 서랍만 찾으면 됩니다.
element가 어떤 bucket에 들어가게 될지는 그 element의 hashCode()값에 의해 결정됩니다. bucket이 n개가 있다면, element는 그 hashCode()%n 번째 bucket에 들어갑니다.(대략적으로 그렇단 얘기고, 정확히 얘기하면 비트연산으로 처리됩니다.) element를 가져올 때 입력되는 키는 같은 bucket에 있는 element 들만 비교를 하게 됩니다. bucket 수가 많으면 한 bucket에 들어가는 element의 수가 적을 것이고, 이는 속도를 향상시키는 길이 됩니다.
데 이터를 이래저래 추가하고 한 번에 뽑아서 따로 저장하는 로직을 생각해봅시다. 데이터를 추가하는 부분에 비해 뽑아쓰는 부분이 적기 때문에 bucket을 작게 유지하는 게 유리해 보이지만 그렇지 않습니다. 왜냐하면, get()이 호출될 때 뿐만 아니라 put()이 호출될 때도 기존에 데이터가 있는 지 확인하는 작업이 다시 한번 실행된다는 것입니다. 키값이 기존에 있던 것과 동일하면, 새로운 입력되는 값이 기존 값을 덮어쓰게 됩니다. 따라서 새로운 element가 추가될 때 그 버킷 안의 모든 element에 대해 새로 추가될 element와 같은 것인지 검사를 합니다. 다시 말해 그 bucket의 모든 element에 대해 hashCode()가 호출되고, 추가될 element와는 == 연산이나 equals()를 통해 비교를 하게 됩니다.

4. 용량과 load factor

용량은 bucket의 수입니다. element의 수가 아닙니다. 기본값은 16입니다. 만약에 한 16만개 정도의 데이터를 16개의 bucket에 담는다면, get을 할 때 평균 1만개의 element와 비교를 해야 합니다. 굉장히 비효율적이죠. 그래서 상황에 따라 bucket의 수가 확장되어야 할 경우가 있습니다. 총 element의 수와 용량간에 어떤 연관성이 있어야 하는데, 그게 바로 load factor입니다. load factor= 총 수용가능한 element의 수 / 용량  으로 정의 됩니다.
HashMap 에는 총 수용가능 element의 수를 늘이는 메쏘드가 없습니다. put() 메쏘드 즉, element의 수를 증가시킬 수 있는 메쏘드가 실행될 때 알아서 수용가능 용량을 계산해서 이 값이 (load factor * 용량)을 넘어서게 되면, bucket 수를 대략 2배로 늘이고(즉, 용량이 2배로 늘어납니다.) 모든 element에 대해 다시 hashCode를 호출하여 어느 bucket으로 들어갈 것인지 다시 계산을 합니다. 이 과정을 rehashing이라 하며 부하가 굉장히 큽니다. element수를 감소 시키는 remove() 메쏘드는 rehashing을 하지 않습니다.
따라서 처음에 어느정도 용량이 들어갈 것인지 예측할 수 있다면, 처음부터 크기를 적절히 해서 rehashing이 가능한 한 적게 일어나도록 해야 합니다. HashMap(int initialCapacity) 생성자를 사용하면, 초기 용량이 16이 아닌 다른 값을 쓸 수 있습니다.

그 렇다고 초기 용량을 무조건 크게 잡는 것은 능사가 아닙니다. 지나치게 크게 잡을 경우 다음과 같은 문제가 생길 수 있습니다. 첫째, 메모리 낭비가 발생합니다. 둘째, key에 대한 iteration을 돌 때 부하가 커집니다. iteration의 부하는 (bucket의 수 + 실제 인스턴스의 크기) 에 비례합니다.

load factor가 크면  (즉, 한 bucket에 많은 element를 넣게 되면) 메모리 절약은 할 수 있으나, 검색이 힘들어 집니다. 반대로 너무 작으면(bucket의 수가 너무 많으면,) 검색은 빠르겠지만, 메모리 상의 낭비가 일어나게 됩니다. 그래서 가장 최적의 값은 일반적으로 0.75라고 합니다. HashMap은 load factor의 기본값을 이 값으로 하고 있지만,  HashMap(int initialCapacity, float loadFactor) 생성자를 통해 load factor를 변경시킬 수 있습니다. 메모리 좀 낭비해도 속도가 중요하다고 생각하면 load factor를 낮추면 됩니다.

5. 동기화되지 않음

처음에 말씀드렸다시피 HashMap은 동기화가 되지 않습니다. Hashtable과의 큰 차이점이죠. 단지 put, get에 대한 문제만은 아닙니다. 학생번호-몸무게 를 key-value로 가지는 HashMap 객체에 대해 학생의 몸무게 평균을 구하려고 하면, 학생의 리스트 즉, HashMap 객체의 keySet을 뽑아와야 합니다. 열심히 루프 돌면서 계산하는 와중에 다른 쓰레드에서 어떤 요소를 추가하거나 삭제하게 되면, 일이 난감해집니다. HashMap은 이런 상황에서 fail-fast 방식으로 처리합니다. (fail-fast: 어떤 에러나 또는 에러를 발생시킬 만한 상황에서 더 이상 정상적인 작업을 진행하지 않도록 해주는 거)
만약 동기화 과정이 필요하다면, Map m= Collections.synchronizedMap(new HashMap(...)); 와 같이 Collections.synchronizedMap() 을 이용하는 것이 좋습니다.

사족으로 알아도 몰라도 별로 달라질 게 없는 HashMap관련 지식 하나!

HashMap은 순서를 보장하지 않는다고 했습니다. 보장되지 않는 순서의 비밀을 파헤쳐봅시다!!
bucket은 Entry라는 내부 클래스의 array로 정의 됩니다.
각 bucket은 처음에 null로 세팅이 되어있고, 어떤 element가 들어오면 Entry 객체를 생성해서 대입합니다. bucket이 서랍이라고 설명한 것은 이해를 돕기 위한 것이고, 코드 상 정확히 말하면 bucket은 어떤 Entry를 말하는 겁니다. Entry는 key와 value 그리고 next 3가지의 멤버 변수로 구성이 됩니다. 여기서 next는 다음 Entry를 가질 수 있는 구조입니다. Linked List라는 거죠.
null이 아닌 bucket에 대해 어떤 element가 추가될 때는 그 bucket의 Entry 객체를 next로 세팅한 새로운 Entry 객체를 생성해서 bucket의 자리를 넣습니다. 뒤에 붙이는 것이 아니라 앞에 붙이는 구조가 되지요. (일반적인 Linked List는 뒤에 붙입니다.)

keySet() 얘기를 해보죠. bucket을 0번째부터 끝까지 루프를 돕니다. 즉, bucket 수만큼 루프를 돕니다. 어떤 bucket에 entry가 있으면, 그 entry의 key를 뽑아냅니다. 그리고그 entry의 next에 대해서 같은 작업을 합니다. next가 null일 때까지 루프돌고 null이면 다음 버킷으로 넘어갑니다. 즉,모든 bucket에 대해서 같은 작업을 하면 element의 수만큼 루프를 돌게 되겠지요. 결과적으로 keySet()의 비용은 (bucket의 수 + element의 수) 가 됩니다. 그리고 뽑히는 순서는 bucket 번호가 작은 놈이 먼저 나오고, 그 중에서는 나중에 들어간 놈이 먼저 나옵니다. 즉, 넣는 순서에 따라 순서가 달라질 수도 있다는 겁니다.