HashMap의 내부 동작을 알아보자

[suna-ji]

📝 HashMap

📚 주제:

해시맵 자료구조

📍요약

✅ key의 해시값(hashCode)이 같고 equals()도 같으면 → 기존 키의 value를 덮어씀
✅ key의 해시값(hashCode)이 같지만 equals()가 다르면 → 새로운 노드로 추가됨
✅ 해시 충돌 발생 시 → 처음에는 Linked List, 이후 노드가 많아지면 Tree로 변경 (Java 8 이상)
✅ 해시맵의 로드 팩터(Load Factor) -> 해시맵이 얼마나 차면 리사이징 할지를 결정하는 기준 값 (기본값 0.75)

📖 핵심 내용:

HashMap 자료구조

HashMap은 키-값 쌍을 저장하는 자료구조로, 내부적으로 해시 함수를 사용하여 데이터를 빠르게 검색할 수 있도록 설계되어 있습니다.
키를 기반으로 해시값을 생성하고 이를 이용해 특정 버킷에 데이터를 저장합니다.
동일한 해시 값이 여러 개 존재할 경우 보통 링크드 리스트 또는 트리 구조를 이용하여 충돌을 해결합니다.
평균적인 get()과 put() 연산의 시간 복잡도는 O(1)이지만, 충돌이 많아지면 O(n)가지 증가할 수 있습니다.
따라서 좋은 해시 함수를 사용해야 하고, 적절한 리사이징도 필요합니다.

좋은 해시함수

자바에서 기본으로 제공하는 hashCode()는 일반적으로 충분히 좋은 해시 값을 생성하지만, 특정 상황에서는 해시 충돌이 많이 발생할 수 있습니다.
예를 들어, 문자열이나 숫자 값이 유사한 경우, 해시 값이 편향되거나 특정 패턴을 가지는 경우가 생길 수 있습니다.
이를 해결하기 위해 비트 연산과 소수(Prime Number)를 활용하여 커스텀 해시 함수를 적용하면 해시 충돌을 최소화할 수 있습니다.
특히 해시 값을 균등하게 분포시키고, 해시 테이블의 성능을 최적화하는 것이 중요합니다.

public static int hash(String key) {
        int hash = 0;
        int prime = 31;  // 소수(Prime Number) 사용 → 충돌 방지
        for (int i = 0; i < key.length(); i++) {
            hash = (hash << 5) - hash + key.charAt(i);  // 비트 연산과 곱셈 활용
        }
        return hash;
    }

해시맵의 내부 동작 원리 (자바 기준)

HashMap은 해시 함수를 사용하여 키를 해싱한 후, 해당 해시 값을 기반으로 배열의 특정 인덱스(bucket)에 값을 저장합니다.
자바 8 이전에는 해시 충돌이 발생하면 같은 버킷에 속한 요소들이 연결 리스트(Linked List) 에 저장되었습니다. 하지만 충돌이 많아질수록 탐색 시간이 O(n)으로 증가하는 문제가 있었습니다. 이를 개선하기 위해 자바 8부터는 특정 버킷에 저장된 항목이 8개 이상 충돌하면 **레드-블랙 트리(Red-Black Tree)**로 변환하여 O(log n) 시간 복잡도로 탐색 성능을 개선하였습니다. 반대로, 트리에 저장된 요소 개수가 6개 이하로 줄어들면 다시 연결 리스트로 변환되어 불필요한 메모리 사용을 줄입니다.
또한 HashMap은 적절한 성능을 유지하기 위해 로드 팩터(Load Factor)와 리사이징(Resizing) 정책을 적용합니다. 기본 로드 팩터는 0.75이며, 저장된 요소의 개수가 배열 크기의 75%를 초과하면 기존 크기의 2배로 확장하고, 기존 데이터를 새로운 해시 값에 맞게 재배치합니다. 이러한 방식으로 해시 충돌을 최소화하고 성능을 유지할 수 있도록 설계되어 있습니다.

해시맵의 로드 팩터

해시맵의 로드 팩터(Load Factor)는 해시맵이 얼마나 차면 리사이징(확장)할지를 결정하는 기준 값입니다. 기본 값은 0.75로, 해시맵이 전체 배열 크기의 75% 이상 채워지면 자동으로 크기가 2배로 증가합니다. 로드 팩터가 낮으면 충돌이 적어 성능이 좋지만 메모리 사용량이 증가하고, 높으면 공간 효율적이지만 충돌이 많아져 탐색 성능이 저하될 수 있습니다. 따라서 해시맵의 성능을 최적화하기 위해 적절한 로드 팩터 값을 설정하는 것이 중요합니다.

ConsistentHashMap

Consistent HashMap은 Consistent Hashing(일관된 해싱) 기법을 적용한 해시맵으로, 분산 시스템에서 노드 추가·삭제 시 해시 값의 재배치를 최소화하는 방식입니다. 일반적인 해시 함수는 노드 개수가 변하면 대부분의 키가 다시 매핑되어 성능 저하가 발생하지만, Consistent Hashing은 원형(Hash Ring) 구조를 사용하여 일부 키만 재배치되도록 합니다. 이를 통해 서버가 동적으로 추가되거나 삭제될 때도 부하 분산을 원활하게 수행할 수 있습니다. 대표적으로 분산 캐시 시스템(Redis, Memcached)이나 데이터베이스 샤딩에서 활용됩니다. Java에서는 직접 구현하거나, Guava의 ConsistentHashing 라이브러리 등을 사용할 수 있습니다.

ConcurrentHashMap

ConcurrentHashMap은 멀티스레드 환경에서도 안전하게 동작하는 해시맵으로, synchronized 없이도 동시 접근을 효율적으로 처리할 수 있습니다. 자바 7까지는 세그먼트 기반 락(Lock Striping) 을 사용하여 여러 스레드가 동시에 다른 버킷을 수정할 수 있도록 했으며, 자바 8부터는 CAS(Compare-And-Swap)와 레드-블랙 트리를 활용하여 성능을 최적화했습니다. HashMap과 달리 동시성 이슈 없이 안전하게 사용 가능하며, synchronized를 사용하는 Hashtable보다 성능이 뛰어납니다. 주로 멀티스레드 환경에서 캐싱이나 공유 데이터 저장소로 사용됩니다.