HashMap 내용물 이해하기

Map

Map이라고 하는 것은 Key 와 Value를 연결하는 자료구조로 특징적인 부분은

 

Key와 Value 중 하나만 존재하지 않고 Key는 중복되지 않지만 Value는 중복될 수 있다는 특징이 있다.

Java에서 Map은 인터페이스이며 내부적으로 구현이 되어있는 것은 아니다.

구현체로 가장 보편적인 것은 HashMap이다.

public interface Map<K, V> {
    
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
	...
}

 

HashMap

public static void main(String[] args){
	HashMap<String,String> map = new HashMap<>();
}

 

HashMap는 Key와 Hash 함수를 이용하여 index로 사용하고

이 index에 해당하는 배열 위치에 value를 넣는 자료형이다.

 

즉

HashMap<String,String> map = new HashMap<>();
map.put("key1","value1");

 

위와 같이 HashMap에 저장한다고 해서

전체를 탐색해서 A를 찾고 그에 맞는 Value를 찾는 것이 아닌

 

'key1'를 Hash 함수를 통해 특정한 인덱스, 예로 3이 나왔다면

배열 3번 방에 위치한 값을 꺼내보면 'value1' 가 들어있는 것이다.

 

 

저장하는 로직부터 한번 찾아가 보자.

public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}

 

put 메서드를 호출하게 되면 내부적으로 Key를 hash 메서드에 넣고

putVal 메서드를 호출하여 결과를 반환한다.

 

 

static final int hash(Object key) {
	int h;
	return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

 

key가 null이라면 0을 반환하고 아니라면

key의 hashCode 값과 해당 값을 시프트 16한 값을 XOR 연산하여 해시값을 만든다.

 

즉 key1이라는 값을 넘겨주면

1100100010110110110010 ^ 110010 = 1100100010110110000000

 

위와 같은 처리가 이루어진다.

 

이제 이 값을 이용하여 putVal 메서드를 실행시킨다.

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))))
			e = p;
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}

 

어...

if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;

 

transient Node<K,V>[] table;

 

멤버 변수 table를 변수 tab에 넣으면서 값이 null 이거나 길이가 0 인지 확인한다.

 

값을 넣은 적이 있다면 null 이 아니겠지만 지금 처음 넣는 것이기 때문에 이 로직이 동작할 것이다.

 

먼저 tab에 링크 리스트 초기화가 진행되고

if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);

 

해당 인덱스에 아무 값이 없다면 새로운 노드를 넣게 된다.

 

만약 해당 인덱스에 값이 있다면

else {
	for (int binCount = 0; ; ++binCount) {
		if ((e = p.next) == null) {
			p.next = newNode(hash, key, value, null);
			if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
				treeifyBin(tab, hash);
			break;
		}
		if (e.hash == hash &&
			((k = e.key) == key || (key != null && key.equals(k))))
			break;
		p = e;
	}
}

 

해당 링크 리스트 마지막에 노드를 연결하는 작업이 수행되는데

 

만약 키값이 같다면

if (p.hash == hash &&
			((k = p.key) == key || (key != null && key.equals(k))))
			e = p;

 

노드를 교체한다.

 

 

이번엔 값을 가져오는 로직을 살펴보자

public V get(Object key) {
	Node<K,V> e;
	return (e = getNode(hash(key), key)) == null ? null : e.value;
}

 

key를 해서 하여 getNode 메서드를 통해 값을 가져온다.

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 && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

 

if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) 

 

먼저 table 자체가 값이 존재하는지를 검사하는 로직이다.

이 로직을 통과 못하면 해당 HashMap에는 아무 값이 없다는 것이다.

 

if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;

 

해시에 해당하는 노드를 꺼내서 해당 해시가 같은지 먼저 비교하고

key가 같은지 비교하여 같다면 해당 노드를 꺼내서 반환한다.

 

결국 나의 의문점은

해시를 이용하여 해당 노드를 찾는 것으로 결국 저장한 value를 꺼낼 때

해시 충돌이 나면 이것을 링크드 리스트로 연결한다는 것까지는 알고 있었으나

링크드 리스트에서 어떻게 원하는 값을 찾는가 가 궁금했었는데

static class Node<K,V> implements Map.Entry<K,V> {
	final int hash;
	final K key;
	V value;
	Node<K,V> next;
...

 

노드 자체에 hash 와 key가 둘 다 있어서

hash를 통해 해당 링크드 리스트를 찾아오고

여기서 key가 같은 것을 찾아온다는 것을 알게 되었다.