[JAVA] HashMap, HashTable, ConcurrentHashMap 간의 차이는 무엇일까

1.HashMap은 null 키와 null 값을 허용한다.

public static void main(String[] args) {

    HashMap<String, Object> stringObjectHashMap = new HashMap<>();
    stringObjectHashMap.put(null,"123");

    System.out.println("stringObjectHashMap = " + stringObjectHashMap.get(null));

}

결과

stringObjectHashMap = 123

 

2. 정렬된 컬렉션이 아니다. iter가 추가된 순서를 보장하지 않는다.

3. 동기화와 null 키와 값을 허용한다는 점을 제외하면 HashTable과 유사하다.

4. 기본 버킷 수는 16이다.

5. get, put 메서드는 hashcode(), equals()를 사용한다.

6. 다중 스레드 환경에 적합하지 않다.

 

 

---

put에서 hashcode()를 이용하여 사용할 버킷을 결정한다. 동일한 hashcode를 가지는 노드가 있는지 확인한다. 없다면 매핑이 버킷에 삽입되고 있다면 equals를 사용하는데 true라면 값을 덮어쓰고 true가 없다면 새로운 노드를 삽입한다.

따라서 equals를 오버라이드한다면 hashcode도 같이 오버라이드해야 hash 기반의 컬렉션에서 정상적으로 동작할 수 있다.

 

 

 

 

기본 버킷 수는 2^4 = 16개이며 최대 버킷 수는 2^30이다. 버킷 수는 2^K으로 증가한다.

로드팩터는 버킷의 수를 확장하는데 사용된다.

버킷수 16개에서 12개(16*0.75 = 12)개에 매핑이 있다면 32개로 확장된다.

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

 

 

 

 

HashMap의 특정 버킷이 너무 길어지면 내부적으로 이진트리로 구성한다.

빈의 길이(빈에 연결된 싱글 리스트)가 8이상이면  이진트리로 변경한다.

빈의 길이가 6이하이면 싱글 리스트로 변경한다.

빈의 길이가 8이상이더라도 빈의 개수가64개보다 작다면 해당 빈을 트리화하는 것이 아니라 빈의 개수를 늘린다.

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

 

 

 

---

HashTable

 

HashMap과 비교

1. 키와 값에 null 허용하지 않음

2. 동기화된다. (다중 스레드 사용 가능)

 

왜 키와 값에 null이 허용되지 않는가?

HashTable에서는 검색, 저장을 위해 키로 사용되는 객체가 hashcode(),equals() 메서드를 구현해야 했다. null은 구현을 할 수 없으므로 사용이 불가능했지만 HashMap은 이를 보완하여 작성되었기 때문이다.

 

 

동기화

하나의 Lock을 이용하기 때문에 Thread-safe하지만 성능이 좋지 않다.

 

 

---

ConcurrentHashMap

1. 키와 값에 null을 허용하지 않는다.

2. 동기화된다.

 

버킷 단위의 Lock을 하기 때문에 Thread-safe하고 성능이 좋아서 HashTable보다 멀티스레드 상황에서 선호된다.

 

+추가) ConcurrentHashMap에서는 왜 키와 값에 null을 허용하지 않을 까?

ConcurrentHashMap은 동시성을 가지기 때문에 아래와 같은 코드에서 문제가 발생할 수 있다.

m.containsKey(k)과 return m.get(k)사이에서 k가 삭제된다면 null을 반환할 것이다.

if (m.containsKey(k)) {
	   // here 
       return m.get(k);
    } else {
       throw new KeyNotPresentException();
    }

키와 값에 null을 허용한 환경이었다면

return 된 null은 2개의 의미를 가지게 된다.

1. 값이 null인 경우

2. 키가 삭제된 경우

즉, 값의 의미가 모호해진다.

 

키와 값에 null을 허용하지 않는 환경이라면

return 된 null은 1개의 의미를 가진다.

1. 키가 삭제된 경우

 

결론적으로 모호성을 없애기 위해 키와 값에 null을 허용하지 않는다는 것을 확인할 수 있다.

 

https://kr.coderbridge.com/questions/2d274d42815b426ea07e88e85089a266

동시 해시 맵이 null 키 또는 null 값을 허용하지 않는 이유 (Why Concurrent hash map does not allow null key or