HashMap의 동작방법

이 아티클은 Jackson Joseraj가 DZone에 게시한 How HashMap Works in Java 에 대한 번역물입니다.

 

HashMap이 내부적으로 어떻게 동작하는지에 대한 질문은 면접 때에 가장 인기 있는 질문입니다. 대부분의 사람들은 HashMap을 사용할 줄 알거나 HashMap과 HashTable의 차이는 알고 있습니다. 그러나 "HashMap이 내부적으로 어떻게 동작하는가?"에 대한 질문에 대해서는 어려워합니다.

질문에 대한 해답은 해싱 원리에 기반하여 작동한다는 것이지만 말처럼 간단한 문제는 아닙니다. 해싱은 쉽게 반복하는 알고리즘을 사용하면서 유니크한(유일무이한) 코드를 변수 또는 속성에 할당하는 매커니즘으로, 해싱 메커니즘에 같은 객체를 적용시켰을 때, 항상 같은 hashcode()를 반환해야 합니다.

그러면 다음과 같은 질문을 할 수 있습니다.

"해싱이 HashMap에서 저장하고 값을 검색할 수 있도록 할까?"

많은 사람들은 이렇게 대답할 것입니다. "바구니에 값들이 저장될 것이고 키를 통해 검색한다." 만약 당신도 이렇게 생각하고 있었다면 잘못 알고 있었던 것입니다. 그것을 입증하기 위해서 HashMap 클래스를 살펴보겠습니다.

transient Entry[] table;

HashMap에서 Entry[]를 어떻게 사용할까요? HashMap은 키-값 쌍을 저장하는 것이 아니라 Entry 인스턴스와 같은 객체를 저장합니다.

 

---

Entity Class란?

HashMap은 키와 값을 가지는 Entry Class를 내부 클래스로 가집니다. 그리고 이 클래스는 next라는 이름을 가지고 있는데 이에 대해서는 곧 설명하겠습니다.

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

ashMap이 배열 내에서 키-값의 쌍이 아니라 Entry 인스턴스를 저장한다는 것은 위에서 말했습니다.

값을 저장하기 위해서는 HashMap의 put() 메서드를 이용할 텐데 지금부터 put() 이 어떻게 동작하는지 파헤쳐 보겠습니다. 

 

---

put() 메서드는 내부적으로 어떻게 동작할까?

다음 코드는 put()  메소드의 구현부입니다.

public V put(K key, V value) {
    if (key == null)
       return putForNullKey(value);
  
    int hash = hash(key.hashcode());
    int i = indexFor(hash, table.length);
  
    for (Entry<K,V> e = table[i]; e != null; e = e.next){
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
             V oldValue = e.value;
             e.value = value;
             e.recordAccess(this);
             return oldValue;
          }
     }
     modCount++;
     addEntry(hash, key, value, i);
     return null;
 }

• 먼저, 키가 null인지 체크합니다. 만약 null이면 null의 hashcode는 0이기 때문에 위치 0에 저장합니다.
• 그런 다음 hashcode 메서드를 호출함으로써 hashcode를 적용합니다. 배열의 한도 내에서 값을 얻기 위해서는 key.hashcode()가 호출되는데 이때, hashcode에 대해 일부 시프팅 연산을 수행합니다.
• indexFor() 메소드는 Entry 객체를 저장할 정확한 위치를 가져올 때 사용합니다.
• 만약 두개의 다른 객체가 같은 hashcode를 가지고 같은 저장소에 저장된다면 아주 중요한 일이 일어납니다. 이를 처리하기 위해 LinkedList에서는 각각이 다음 객체를 가리키는 "next"라는 속성을 가지는데, Entry class에서 next 속성도 같은 역할을 합니다. 같은 hashcode를 가지는 객체들은 서로 옆에 위치합니다. 
• 그래서 충돌이 났을 때, HashMap은 next 속성의 값을 체크합니다. 만약 null이라면 그 위치에 Entry 객체를 넣고 null이 아니라면 next 객체가 null일 때까지 루프를 돌다가 결국 next 속성이 null이 되면 거기에 Entry 객체를 저장합니다.

---

HashMap에서 중복되는 키 값을 어떻게 막을까?

HashMap은 중복되는 중복 키를 허용하지 않기 때문에, 동일한 키로 다른 값을 넣는다면 가장 최근 값이 반환됩니다.

import java.util.HashMap;
import java.util.Map;
  
public class HashMapEg{
    public static void main(String[] args) {
            Map map = new HashMap();
            map.put(1,"sam");  
            map.put(1,"Ian");  
            map.put(1,"Scott");  
            map.put(null,"asdf");
  
            System.out.println(map); 
        }
}

위의 코드에서 map은 {null=asdf, 1=Scott} 이 될 것입니다. 어떻게 이런 일이 일어나는 것일까요?

LinkedList에서 모든 Entry객체들은 같은 hashcode를 가집니다. 그러나 HashMap은 equals()를 사용합니다. 이 메서드는 키의 값이 동일한지를 체크하는 것이고 따라서 key.equals(other key)가 true이면 Entry class 내부의 값이 대체됩니다. 그래서 중복 키를 방지할 수 있습니다. 

 

---

Get메서드는 내부적으로 어떻게 동작할까?

put() 메소드에서 적용했던 것과 유사하게, 로직이 값을 검색하는 데에도 사용됩니다.

public V get(Object key) {
    if (key == null)
       return getForNullKey();
  
     int hash = hash(key.hashcode());
     for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next){
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
             return e.value;
     }
         return null;
 }

• 저, 전달된 키 객체의 hashcode를 가져와서 버킷 위치를 찾습니다.
• 만약 찾으면 그 값을 반환합니다.
• 찾지 못하면 null을 반환합니다.

---

만약 두 키가 같은 해시코드를 가진다면 어떻게 될까?

put() 메소드 내에서 hashcode 값이 동일할 경우 충돌이 발생했을 때 해결했던 메커니즘이 동일하게 여기서 사용됩니다.

key.equals(other key)가 true일 때까지 검사하고, true인 경우 값을 반환합니다.