[CS] Java HashMap의 동작 과정
Java에서는 HashMap, HashSet 등 Hash를 사용한 자료구조를 사용하는데 HashMap의 동작 과정에 대해 알아봅시다.
우선 HashMap은 Key라는 유일한 값에 대한 Value를 O(1)의 시간복잡도로 구할 수 있습니다.
자세히 알아보기 전에 HashMap의 전체 동작과정을 확인해 봅시다.
HashMap에 값을 추가할 때 Key의 해시 함숫값으로 hashcode라는 Key에 대한 유일한 값이 나오게 됩니다.
자바의 hashcode()의 리턴은 int 형으로 2^32 수로 표현가능하지만 입력으로 주어지는 Key는 2^32개 이상일 수도 또는 모든 HashMap이 2^32개의 버킷을 가지고 있을 수 없으므로 hashcode가 중복되는 경우가 발생하는데 이것을 해쉬충돌이라고 합니다.
해시충돌이 발생하는 경우는 두 가지로 새로운 Key가 저장되는데 우연히 hashcode 값이 같을 경우와 이미 존재하는 Key에 대한 값을 수정하기 위해 참조할 때입니다.
이때는 해시충돌 이후 equals()를 통해 새로운 Key라면 Chaining 하거나 이미 존재하는 경우 해당 Key 버킷에 덮어쓰게 됩니다.
해시충돌 과정을 자세하게 알아봅시다. HashMap의 Node <K, V>라는 객체의 배열로 이루어져 있고 한 칸을 버킷이라고 합니다.
Node 객체는 int hash, K key, V value, Node<K,V> next로 이루어져 있습니다.
위의 그림과 같이 hash 값 1에서 충돌이 여러 번 발생할 때마다 새로운 Node 객체가 next에 저장되는 것을 Chaining이라고 합니다.
이러한 이유로 next 객체에 저장되면서 O(n)의 시간 복잡도를 가지게 됩니다.
자바 내부적으로 해시충돌이 자주 발생하면 red-black Tree로 구조를 재구성하면서 O(logN)의 시간복잡도를 보장합니다.