해쉬맵(hashmap) 설명 정리

1. 해쉬맵(hashmap)과 해쉬테이블(hashtable)의 차이

해쉬맵은 해쉬테이블과 기본적으로 동일하다.

하지만 아래 3가지 다른점이 있다.

1) 해쉬맵은 UNSYNCHRONIZE 하다 

  동기화 하기 위해서는 다음과 같이

  Map m = Collections.synchronizedMap(new HashMap(…));

2) 해쉬맵은 null을 permit 한다.

3) 해쉬테이블은 thread safe 한 객체이지만 해쉬맵은 아니다.

  multi-thread 환경에서는 해쉬맵은 문제가 생길 수 있고, 

  single-thread 환경에서는 해쉬테이블은 성능이 저하된다.

2. 해쉬맵의 구현

HashMap hashmap = new HashMap();

hashmap.put(“jakarta”, “project”);

hashmap.put(“apache”, “tomcat”);

Set set = hashmap.entrySet();

Iterator keys = set.iterator();

while (keys.hasNext()) {

   key = (String)keys.next();

   System.out.println(hashmap.get(key));

}

 

3. bucket 

해쉬맵에서 bucket 은 map 이 가지는 element 들을 적당히 분산시켜 놓은 것

bucket 이 많으면 한 bucket 에 들어가는 element 의 수가 적어져서 속도 향상

bucket 이 적으면 메모리 낭비가 적다

 

4. capacity 와 load factor 

capacity 는 bucket 의 수, element 의 수가 아님, 기본값은 16

laod factor 는 얼마나 hashmap이 찾는지를 비교해서 자동적으로 capacity 가 늘게 한다. 

기본값은 0.75 이고, 0.75 offers a good tradeoff between time and space costs

put method 가 실행될 때 용량의 75%가 넘어서게 되면, bucket 수를 2배로 늘리고, 모든 element 에 대해 다시 hashcode 를 호출하여 어느 bucket 으로 들어갈 것인지 계산을 한다.

이것을 rehashing 이라고 하고 부하가 크다.

load factor 를 높이면 메모리는 정략되지만 속도가 느려짐

load factor 를 낮추면 메모리는 낭비, 속도는 향상

 

http://en.wikipedia.org/wiki/Hash_table