제 홈페이지의 모든 글은 anti-nhn license에 따릅니다.



java.util.HashMap분석

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()가 호출되고(정확히 말하면 이미 저장된 데이터에 대해서는 따로 꼬불쳐논 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가지의 멤버 변수로 구성이 됩니다.(사실은 key에 대한 hashCode() 값도 가지고 있습니다. 이것은 hashCode()를 여러 번 호출하지 않기 위해서 있는 캐쉬의 개념으로 이해하시면 되고 데이터로의 의미는 없습니다. get, put 작업이나 rehashing 작업에서 이미 꼬불쳐 놓은 hash값을 씁니다. String의 hashCode()도 이와 유사하게 꼬불치는 방식을 씁니다.) 여기서 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 번호가 작은 놈이 먼저 나오고, 그 중에서는 나중에 들어간 놈이 먼저 나옵니다. 즉, 넣는 순서에 따라 순서가 달라질 수도 있다는 겁니다.

by 삼실청년 | 2008/06/30 19:21 | 컴터질~ | 트랙백 | 핑백(5) | 덧글(22)

트랙백 주소 : http://iilii.egloos.com/tb/4457500
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Linked at 건실성실착실 3실 청년! : .. at 2008/08/07 17:06

... 지난 시간에 썼던 java.util.HashMap 분석과 이어지는 내용입니다. 안 읽으셨다면 먼저 읽으시기 바랍니다.TreeMap은 keySet()으로 키 데이터 키의 Set을 가져올 때, 정렬된 상태로 가 ... more

Linked at Recent URLs tagg.. at 2008/10/27 11:01

... recorder home features faq feedback privacy Recent public urls tagged "hashmap" &rarr; java.util.HashMap분석 recorded first by sakuragirlhottieme on 2008-10-26&rarr; Sorting and paginating in ... more

Linked at 건실성실착실 3실 청년! : .. at 2010/03/05 12:56

... 요소들을 나눠서 저장해 놓으면, a와 hashCode가 같은 요소들만 뽑아서 a와 비교해 보면 됩니다. 비교할 대상을 확 줄일 수 있다는 것이지요. 자세한 것은 HashMap 분석을 참조하세요.hashCode가 몰래몰래 호출되는 경우가 있다고 했습니다. 그런 경우를 살펴보도록 하죠.HashMap이나 HashSet, Hashtable과 ... more

Linked at 건실성실착실 3실 청년! : .. at 2012/03/29 02:05

... 방식과 hash 방식이 있으며 일반적으로는 binary 방식이 많이 쓰입니다.binary 방식은 tree를 구성해서 "순서대로" 정렬하는 것이고, hash 방식은 hashmap 같은 방식이라고 보시면 됩니다.따라서 hash 방식은 범위 검색이 안 됩니다. 정확히 = 검색만 됩니다. 부등호 표시는 안 됩니다. db engine에 따라 ... more

Linked at ryukato : Set in.. at 2012/10/30 17:29

... 할때마다 이 bucket을 늘리게 되면,bucket을 늘리는 시간이 걸리게 되므로 시간이 낭비된다는 것입니다. HashMap에 더 자세한 설명은 http://iilii.egloos.com/4457500 이곳을 보시면 상세하게 나와있습니다. ) 아래는 HashSet의 기본 생성자와 HashMap member 변수 입니다.private tr ... more

Commented by 소내기 at 2008/07/01 11:05
Map이 단순한 구조라 HashMap도 별거 아닌줄알았는데, HashMap 내부에 bucket이 있다는걸 처음 알았습니다. 땡스! 그리고 Collections.synchronizedMap을 저럴때 쓰는군요!!
Commented by 삼실청년 at 2008/07/01 11:59
하핫. 부족한 글 칭찬해주셔서 고맙습니다^^
(방금 글 잘못쓴 부분 찾아서 수정했습니다. 눈치 못채셨기를..-_-; )
Commented by alchan at 2008/07/21 18:30
좋은 글 잘 읽고 갑니다.

anti-NHN라이센스.. 멋진데요. ^^
Commented by 삼실청년 at 2008/07/23 07:07
^^ 부족하지만 도움이 되셨길 빕니다. 열심히 올릴께요.
네이버에 대한 게길레이션은 멈추지 않습니다ㅋㅋ
Commented by 곰처럼 at 2009/05/06 09:11
제 블로그에 퍼가도 되겠습니까?? 출처 밝히고 비공개로 해 놓겠습니다.
Commented by 삼실청년 at 2009/05/07 18:23
네이버만 아니면 괜찮습니다. 네이버면 무조건 안 되요.
네이버 아니면, 출처를 남기건 말건, 공개를 하건 말건 상업적으로 쓰건 말건.. 전혀 시비걸지 않습니다.
Commented by 곰처럼 at 2009/05/08 10:35
아 네이버는 아닙니다. t스토리 입니다.

좋은 자료 감사하고 복받으세요.
Commented by 삼실청년 at 2009/05/19 20:49
^^ 복받을께요. 고맙습니다. 곰처럼님도 복 받으세요~
Commented by 나모 at 2010/02/04 17:13
동기화된 맵을 사용한다면 자바 5.0 이후에 나온 java.util.concurrent패키지를 사용하면 됩니다.
ConcurrentHashMap 같은 클래스를 요..
Commented by 삼실청년 at 2010/02/08 23:14
네. synch 잡는 부분이 좀 더 최적화되어있어서 hashtable이나 synchronizedMap 보다 성능이 좋다고 하더군요.
Commented by 이재영 at 2010/09/09 11:04
너무나 좋은 정보 감사합니다. 재밌게 읽고 갑니다.
Commented by 삼실청년 at 2010/09/09 19:22
제 블로그 중에선 이 글이 젤 잘 팔리는 글인 것 같네요ㅋㅋ
재밌으셨다니 다행~^^
Commented by 한귀순 at 2010/12/17 10:24
HashMap 보러 왔는데요.. anti-nhn licesnse 글 보고 멋지신 분이란 생각이 들어서 글 남깁니다. ^^
물론 HashMap 설명도 잘 들었구요.. 고맙습니다. ^^
Commented by 삼실청년 at 2010/12/17 21:58
으하하~ 멋진 남자에겐 아름다운 여자가 어울리죠.
제가 멋지다고 생각하신다면 아리따운 아가씨 좀...ㅜㅜ
찾아주셔서 감사합니다^^
Commented by asddda at 2012/04/11 11:59
hashmap 키값 이용해서 뽑을때 순서대로 뽑아야하나요??;;
제일 위에것만 뽑아지더라구요..
queue기능도 그래서 지금 엎고 다시하는중인데...하
Commented by 삼실청년 at 2012/04/12 22:49
Map<String , String> map = new HashMap<String, String>();
map.put 을 왕창 반복
for(String key : map.keySet()){
System.out.println(key +":"+ map.get(key));
}

대략 위와 같이 iteration을 도는 걸 원하시는 건가요?

아니면..

map.put("key" , "value1");
map.put("key" , "value2");

map.get("key") 하면 마지막에 엎어쓴 value2 가 나오는 게 문제인가요?

질문을 잘 이해를 못하겠습니다.ㅜㅜ
Commented by 나그네 at 2012/05/15 07:04
hashmap 검색을 하다 우연치 않게 보게 되었는데

정말 도움이 많이 되는글 같습니다..

^^
잘봤습니다.~
Commented by 삼실청년 at 2012/06/16 23:43
^^
감사합니다.
Commented by 진무라마사 at 2012/05/21 10:00
좋은글 잘 읽었습니다 ^^
Commented by 삼실청년 at 2012/06/16 23:43
감사합니다^^
Commented at 2012/09/10 13:38
비공개 덧글입니다.
Commented by 삼실청년 at 2012/09/12 14:23
고맙습니다. 수정했어요^^

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶