자바 separate chaining in HashMap

HashMap 에서 HashTable 을 관리하는 방법과 seperate chaining 이해를 위한 목적의 글입니다.

 

/** The table, initialized on first use, and resized as necessary. When allocated, length is always a power of two.  (We also tolerate length zero in some operations to allow bootstrapping mechanics that are currently not needed.)
**/
transient Node<K,V>[] table;

HashTable 은 내부에 table 맴버 변수를 가지고 있고 이 변수가 HashTable 의 역할을 수행합니다.

 

put(key, value) 를 호출하였을때 HashTable 의 index 로는 key.hashcode() 가 사용된다.

key 는 다르지만 key.hashcode() 가 같은 경우에 해쉬 충돌 (hash collision) 이 발생하여 HashMap 에서는 Seperate Chaining 을 통하여 해결하였다.

 

HashMap 에서 Hash Collision 이 발생하는 과정과 Seperate Chaining

public class MyClass {
	public Integer number;
	
	public MyClass(int n) {
		this.number = n;
	}
	@Override
	public int hashCode() {
		return 1;
	}
}

MyClass 는 Key 로 사용될 클래스이며 모든 MyClass 객체는 hashCode() 리턴값이 1 로 고정되어있다.

		HashMap<MyClass, Integer> map = new HashMap<>();
		for (int i = 0; i < 1000 ; i++) {
			map.put(new MyClass(i), i);
		}

반복문을 수행하면서 Key 로는 MyClass 를 전달하고 Value 로는 i 를 전달한다.

 

HashMap 의 table 상태

1. ( i = 0 ) -> map.put(new MyClass(0), 0);

 - HashTable 에 key.hashcode() 결과인 1 에 Node 가 저장됨.

put() 된 후 table 상태

 

2. ( i = 1 ) -> map.put(new Myclass(1), 1);

 - MyClass 의 hashcode() 리턴값은 모두 1로 동일하므로 HashTable 에 key.hashcode() 결과인 1 에 Node 가 저장됨.

 - 1 번 HashTable 자리에 이미 element 가 존재하므로 Seperate Chaining 에 의하여 Node.next 로 Link.

Node.next 에 1 을 가진 Node 주소가 저장.

3. ( i = 2 ) -> map.put(new MyClass(2), 2);

 - MyClass 의 hashcode() 리턴값은 모두 1로 동일하므로 HashTable 에 key.hashcode() 결과인 1 에 Node 가 저장됨.

 - 1 번 HashTable 자리에 이미 element 가 존재하므로 Seperate Chaining 에 의하여 Node.next 로 Link.

 

Sperate Chaining 으로 저장된 key 를 조회하는 과정

1. get(MyClass(2)) 호출

HashMap 의 HashTable 상태

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) --- (1)
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode) --- (2)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) --- (4)
                    return e;
            } while ((e = e.next) != null); --- (3)
        }
    }
    return null;
}

 

1-1. HashTable 에서 hashcode() 에 해당하는 첫번째 데이터 확인. --- (1)

 - MyClass 의 hashcode() = 1 이므로 HashTable 에서 [1] 의 자리에 해당하는 객체와 Key 와 hashcode 비교

 - hashcode 는 일치하나 Key 가 불일치.

 - 일치 여부 조건문 : if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))

 - hash 값과 equals() 혹은 == 으로 비교

1-2. hashcode 는 일치하나 key 가 일치하지 않을 경우 node.next 를 호출하여 다음 chain 에 있는 키와 비교 --- (4)

 - first.next 가 존재할 경우에 spereate chaining 된 key 가 있는 것이므로 next node 와 key 를 비교

1-3. 반복문을 돌면서 1-2 과정을 반복하여 일치하는 키를 찾는다. --- (3)

 - 마지막 Linked 된 Node 의 key 와 조회하고자 하는 key 가 일치하여 해당 Value 를 리턴

2. (2) 코드를 보면 Node 의 타입이 TreeNode 인 경우를 찾는데 어떤 경우게 TreeNode 가 사용되는 것인가.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) --- (1)
            e = p;
        else if (p instanceof TreeNode) --- (2)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { --- (4)
                    p.next = newNode(hash, key, value, null); --- (5)
                    if (binCount >= TREEIFY_THRESHOLD - 1)  --- (6)
                        treeifyBin(tab, hash); --- (7)
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) --- (3)
                    break;
                p = e;
            }
        }
    ....
}

1. put() 과정 중에 HashTable 에 넣고자 하는 hashcode 가 존재(Hash Collision)하는 경우 (1) 까지 도달하게 된다.

2. (1) 조건문에서는 넣고자 하는 key 와 이전에 존재했던 key 가 일치하는 경우.

3. (2) 조건문은 HashTable 이 이미 Tree 구조로 변경된 경우.

4. (1), (2) 조건문에 걸리지 않게 되면 else 로직을 타게 된다.

5. (4) 해시충돌이 발생하여 Seperate Chaining 을 적용하기 위해 Node.next 를 확인하고 비어있다면 Node.next 에 넣고자 하는 key 를 저장.

6. (4) 조건에 부합하지 않아 (Node.next 에 Node 가 이미 존재) (3) 조건문까지 도달하게 되었고 넣고자 하는 키고 동일한지 확인.

7.  (3) 조건에 부합하여 이전에 저장되어있던 키와 저장하고자 하는 키가 동일하다면 반복문을 탈출하여 value 를 덮어 쓴다.

8. (3) 조건에 부합하지 않아 binCount 가 하나씩 증가하면서 위 조건들을 검사.

9. 반복문이 계속 실행되다가 (6) 조건문을 만족하면 (7) 함수가 호출되면서 HashTable 이 Tree 구조로 변경된다.

 

HashTable 에서는 해시충돌(Hash Collision) 에 의해서 Seperate Chaining 을 적용하였고 Chain 의 수가 TREEIFY_THRESHOLD (8) 을 초과하면 HashTable 성능이 떨어진다고 판단하여 HashTable 을 red black tree 구조로 변경한다.