[JAVA] HashMap의 심층 작동 원리 : 성능 최적화와 내부 구조의 이해

HashMap의 작동 원리

 

자바 프로그래밍에서 데이터를 효율적으로 관리하기 위해 가장 빈번하게 사용되는 자료구조 중 하나가 바로 HashMap입니다. 단순히 put()과 get() 메서드를 사용하는 것을 넘어, 그 내부에서 어떤 알고리즘이 동작하고 어떻게 성능을 최적화하는지 이해하는 것은 고성능 애플리케이션 개발을 위한 필수적인 과정입니다. 오늘날의 복잡한 시스템 아키텍처에서 HashMap의 메커니즘을 정확히 파악하는 것이 왜 중요한지 심층적으로 살펴보겠습니다.

1. HashMap의 근간: 해싱(Hashing)과 버킷(Bucket)

HashMap은 기본적으로 해시 테이블(Hash Table) 자료구조를 기반으로 합니다. 데이터를 저장할 때 '키(Key)' 값을 해시 함수에 대입하여 '해시 코드(Hash Code)'를 생성하고, 이 코드를 배열의 인덱스로 변환하여 '값(Value)'을 저장하는 방식입니다. 이때 데이터가 저장되는 각 배열 요소를 버킷(Bucket)이라고 부릅니다. 이 구조의 가장 큰 장점은 데이터의 양에 관계없이 평균적으로 O(1)이라는 경이로운 시간 복잡도로 데이터에 접근할 수 있다는 점입니다.

2. 해시 충돌(Hash Collision)과 해결 전략

이론적으로는 모든 키가 고유한 인덱스를 가져야 하지만, 실제로는 서로 다른 키가 동일한 해시 코드를 생성하거나 다른 해시 코드가 동일한 인덱스로 매핑되는 해시 충돌이 발생합니다. 자바의 HashMap은 이를 해결하기 위해 두 가지 핵심 전략을 사용합니다.

2.1 Separate Chaining (연결 리스트)

충돌이 발생하면 해당 버킷에 데이터를 연결 리스트(LinkedList) 형태로 이어 붙이는 방식입니다. 자바 7까지는 이 방식만을 사용했습니다.

2.2 Treeification (레드-블랙 트리 전환)

자바 8부터는 성능 최적화를 위해 획기적인 변화가 도입되었습니다. 하나의 버킷에 데이터가 일정 개수(기본값 8개) 이상 쌓이면, 연결 리스트를 레드-블랙 트리(Red-Black Tree)로 변환합니다. 이는 최악의 경우 O(n)까지 떨어질 수 있는 조회 성능을 O(log n)으로 보장하기 위함입니다.

3. HashMap vs Hashtable: 결정적 차이점

많은 개발자가 혼동하는 두 자료구조의 차이점을 명확히 정리해 보겠습니다. 실무에서는 특별한 이유가 없다면 HashMap을, 멀티스레드 환경에서는 ConcurrentHashMap을 권장합니다.

비교 항목	HashMap	Hashtable
동기화 (Synchronization)	비동기 (Not Synchronized)	동기화 (Synchronized)
Null 허용 여부	Key, Value 모두 Null 허용	Null 허용 안 함
성능	빠름 (오버헤드 적음)	느림 (락 오버헤드 발생)
반복자 (Iterator)	Fail-fast Iterator	Enumerator (Not Fail-fast)

4. 해시 맵의 동적 확장: Resizing

HashMap은 초기 용량(Initial Capacity)과 부하 계수(Load Factor)를 가집니다. 부하 계수의 기본값은 0.75입니다. 즉, 전체 버킷의 75%가 차게 되면, HashMap은 버킷의 크기를 두 배로 늘리고 기존의 데이터를 재배치하는 Rehashing 과정을 거칩니다. 이 과정은 비용이 많이 들기 때문에, 저장할 데이터의 양을 미리 알고 있다면 초기 용량을 적절히 설정하는 것이 성능 최적화의 팁입니다.

5. 결론: 효율적인 HashMap 사용을 위한 가이드

• Key 객체의 불변성: Key로 사용할 객체는 hashCode()와 equals()를 반드시 재정의해야 하며, 가급적 String이나 Integer 같은 불변 객체를 사용하는 것이 안전합니다.
• 초기 용량 설정: 대량의 데이터를 다룰 때는 new HashMap(expectedSize / 0.75 + 1)과 같이 초기 용량을 지정하여 리사이징 횟수를 줄이세요.
• 멀티스레드 주의: 스레드 안전이 필요하다면 Hashtable보다는 Collections.synchronizedMap이나 성능이 더 뛰어난 ConcurrentHashMap을 사용하십시오.

---

참고 출처

1. Oracle Java Documentation: Class HashMap<K,V>
2. OpenJDK Source Code: java.util.HashMap.java
3. Brian Goetz, Java Concurrency in Practice, Addison-Wesley Professional.