[JAVA] HashMap 동작원리?

코딩할때 HashMap을 자주 사용하지만 어떻게 동작 하는지 자세히 알지 못하는 것 같아 정리 해보려고 합니다.

내부적으로 어떻게 동작하는지 살펴보겠습니다.

 

1. HashMap 사용 방법

 

Key와 값으로 데이터를 관리하며 키를 이용하여 데이터를 추출 할 수 있습니다.

HashMap의 개체생성시에 key와 value의 Type을 선언하며 put 매서드로 객체를 삽입, get 매서드로 객체를 추출합니다.

// HashMap 생성
Map<String, Integer> map = new HashMap<String, Integer>();

// HashMap 데이터 삽입
map.put("펭수", 1);

// HashMap 데이터 추출
map.get("펭수")

 

2. HashMap의 저장방법

 

HashMap읜 Key, Value를 각각 저장하는 것이 아닌 Entry(Node) Class를 내부 클래스에 저장합니다.

 

java.util.HashMap을 열어보면 아래와 같이 확인이 가능합니다.

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

그렇다면 어떻게 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;
 }

 

1. 먼저 키가 null인지 체크하고 null이면 hashcode는 0이기 때문에 위치 0에 저장됩니다.

2. hascode를 매소드를 호출하여 hascode를 적용 합니다.

   배열의 한도 내에서 값을 얻기 위해 key.hashcode()가 호출되고 일부 시프팅 연산을 수행합니다.

3. indexFor() 매소드는 Entry 객체를 저장할 정확한 위치를 가져올 때 사용합니다.

4. 만약, 두개의 다른 객체가 같은 hashcode를 가진다면 충돌이 이러나기 때문에 이를 처리하기 위해 next 속성을 가집니다. 같은 haschcode를 가지는 객체들은 서로 옆에 위치하게 됩니다.

5. 충돌이 나면 next 속성의 값을 체크하고 만약 null 이면 그 위치에 Entry 객체를 넣고 null이 아니면 next 객체의 next를 다시 불러 null일때까지 확인하고 객체를 저장합니다.

 

3. 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); 
        }
}

위 예제에서는 null은 "asdf", 1은 "Scott"를 가지게 됩니다.

HaspMap 내부에서 equals를 사용하고 동일한 것을 사용하다면 값을 대체 합니다.

 

4. 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;
 }

전달된 키 객체를 hascode를 적용하고 table에서 해당 인덱스값을 가져와 그 값을 반환합니다.

못 찾는 다면 null을 반환합니다.

 

위 코드를 살펴보면 HashMap의 검색 알고리즘이 O(1) 인 것을 확인할 수 있습니다.

 

5. Hashcode는 같은 값을 가질 수 있나?

 

hashcode는 같은 값을 가질 수 있습니다.

특히 String.class를 사용할때는 같은 값을 가집니다.

 

String.class로 hashcode를 구할때 문자열의 각각의 Byte의 ASCII CODE 공식을 더해 총합을 hash 값으로 사용하는데 다른 문자열이라도 총 합이 같다면 같은 hash값을 가질 수 있습니다.

 

 

6. HashMap은 HashCode가 값이 같으면 어떻게 내부적으로 구별하나?

 

if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
}

put의 hash를 비교하는 로직을 살펴보면 그 답을 알 수 있습니다.

 

1. hash 값이 같은가? (e.hash == hash)

2. key와 입력하려는 key가 동일한 객체인가? ((k = e.key) == key)

3. key 값이 동일한가 ? (key.equals(k))

 

즉, 위 세가지 조건중 1&&2 or 1&&3 조건이 만족해야 중복 key로 확인하게 됩니다.

중복키로 확인되면 위에서 보듯 오버라이드 되는 것을 확인 할 수 있습니다.

 

hash값만 같다면 next를 이용하여 저장합니다. 

p.next = newNode(hash, key, value, null);

마지막으로..

자바 버전마다 전체 흐름을 비슷하지만 동작이 더 빠르게 변경되고 있어 로직에 차이가 있을 수 있습니다.

기본적인 동작 원리를 확인 하신 뒤 지금 자바 버전의 HashMap을 살펴보면 좋을 것 같습니다.

 

 

참고

http://wiki.sys4u.co.kr/pages/viewpage.action?pageId=7767033#space-menu-link-content

https://dzone.com/articles/how-hashmap-works-in-java

https://m.blog.naver.com/PostView.nhn?blogId=cestlavie_01&logNo=220551648015&proxyReferer=https%3A%2F%2Fwww.google.com%2F