[F-Lab 모각코 챌린지 18일차] HashMap이 같은 Object를 판단하는 과정 / 주요 operation의 시간복잡도

TIL

1. HashMap 특징
2. HashMap이 같은 Object를 판단하는 과정
3. HashMap 주요 메소드의 시간복잡도

 

---

HashMap 특징

• 키-값 쌍으로 데이터를 보관하는 자료구조이다.
• 키는 중복을 허용하지 않고 값은 중복되도 상관 없다.
• 배열에 LinkedList가 연결 된 Separate Chaining 구조이다.
  
  
• HashMap 해시버킷의 default size는 16이다.

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

 

• 현재 데이터 개수가 load factor * 현재 해시버킷 개수에 다다를 때마다 해시버킷 size가 2배씩 증가된다.
  • default load factor가 0.75f니까 약 3/4 정도 차게 되면 해시버킷 size가 증가된다.
    (load factor를 건드리지 않았다는 전제하에)
  • 어떻게 보면 16 size는 적은 용량인데 이렇게 적게 설정한 이유는 int 타입의 해시코드를 해시버킷과 1:1 매칭 시키려면 약 2^32개의 배열 방을 만들어야 한다. HashMap 객체를 생성할 때마다 이 정수형 범위 크기의 배열을 만든다고 생각해보면 OutOfMemoryError가 발생할 수도 있다.
    
    
• inner class로 Node 클래스를 가지고 있다. 이 노드 타입으로 LinkedList를 만든다.

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

 

 

 

HashMap이 같은 Object를 판단하는 과정

// HashMap put() 코드 중 일부
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
    e = p;
}

hash 값을 사용하는 Collection(HashMap, HashSet, HashTable)은 객체가 논리적으로 같은지 비교할 때, 이와 같은 과정을 거친다.

1. HashMap에 데이터가 추가되면 해당 데이터의 해시를 가지고 있는지 찾아본다.
2. 이미 저장 된 데이터의 해시와 해당 데이터의 해시를 비교한다. 만약 두 해시값이 같으면 3단계로 넘어간다.
3. 비교 대상인 두 데이터의 참조가 같거나 equals() 리턴값이 같다면 두 객체는 동일하다고 판단한다.
   (* 해시는 무조건 같아야 한다. equals()가 같아도 hash 값이 다르면 두 객체는 다르다고 판단하기 때문이다.)

 

 

 

HashMap 주요 메소드의 시간복잡도

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

객체의 해시함수 값이 균등 분포 상태라고 할 때, 각 데이터의 key값은 해시함수에 의해 해시값을 갖게 되고 그 해시값은 고유한 index로 변환 되어 해시버킷에 바로 접근할 수 있으므로 평균 O(1)의 시간복잡도로 데이터를 조회할 수 있다.

하지만 해시충돌이 발생한 경우 Chaining에 연결된 리스트들까지 검색을 해야하므로 최악의 경우 O(N)까지 시간복잡도가 증가할 수 있다.

 

 

 

위 예제인 경우, 탐색 횟수는 12 / 3이므로 네 번 탐색해야 한다.
하지만 Java8에서 데이터의 개수가 많아지면 LinkedList 대신 Tree를 사용한다. Tree를 사용할 때 시간복잡도는 이와 같다.

LinkedList 대신 Tree를 사용하면 두 번 탐색만으로 value 값을 가져올 수 있다.

이 외에도 데이터를 삽입하는 put() 메소드, 데이터를 삭제하는 remove() 메소드 역시 평균적으로 O(1)의 시간복잡도를 가지며 최악의 경우엔 O(N) 시간복잡도를 가질 수 있다.

 

 

 

 

📚 참고
해시맵(Hash Map) 정리 및 구현하기
https://woodcock.tistory.com/24