[CS] 해시테이블(HashMap)이란 - 내부 동작 원리

티스토리용 설명(메타 설명)

HashMap이 어떻게 빠르게 조회하는지, 해시 충돌이 생기면 어떻게 처리하는지 자바 기준으로 정리했습니다.

태그: HashMap, 해시테이블, 자료구조, 자바, 해시충돌

---

 

해시테이블이란

key를 해시 함수에 넣어서 나온 숫자를 배열의 인덱스로 사용해, key-value를 저장하는 자료구조입니다. 배열에서 인덱스로 바로 접근하면 O(1)이라는 점을 이용해서, key로도 평균 O(1)에 가까운 빠른 조회를 가능하게 만든 것입니다.

 

 

java

Map<String, Integer> map = new HashMap<>();
map.put("하늘", 30);
map.put("철수", 25);

System.out.println(map.get("하늘")); // 30, 내부적으로 해시값 계산 후 바로 그 위치로 접근

 

동작 원리: hashCode → 인덱스

1. key("하늘")의 hashCode() 계산 → 정수값 나옴
2. 그 값을 배열 크기로 나눈 나머지 등으로 "버킷 인덱스"를 구함
3. 그 인덱스 위치에 key-value를 저장
4. 조회할 때도 같은 과정을 거쳐 바로 그 인덱스로 찾아감

배열을 처음부터 끝까지 순회하지 않고, 계산 한 번으로 저장 위치를 바로 알아낼 수 있다는 게 핵심입니다.

 

해시 충돌(Collision)이 생기면

다른 key인데 해시값을 계산했더니 같은 버킷 인덱스가 나오는 경우가 있습니다. 이걸 해시 충돌이라고 합니다.

 

java

class Point {
    int x, y;
    @Override
    public int hashCode() { return x + y; } // 충돌 나기 쉬운 예시
}
// Point(1,2)와 Point(2,1) → hashCode 둘 다 3, 같은 버킷에 들어감

자바의 HashMap은 이 경우 같은 버킷 안에 **연결 리스트(LinkedList)**로 여러 개를 매달아 둡니다. 조회할 때는 그 버킷 안의 리스트를 순서대로 돌면서 실제 key가 일치하는지(equals()) 확인합니다.

 

버킷[3] → Point(1,2)=A → Point(2,1)=B   (연결 리스트로 이어짐)

자바 8부터는 한 버킷에 쌓인 데이터가 일정 개수(기본 8개)를 넘으면, 연결 리스트 대신 레드-블랙 트리로 바꿔서 최악의 경우에도 조회 속도가 O(n)이 아니라 O(log n)이 되도록 개선했습니다.

 

버킷 개수가 늘어나는 이유 (리사이징)

데이터가 계속 쌓여서 버킷 하나당 평균 데이터 개수(load factor, 기본 0.75)를 넘으면, 내부 배열 크기를 두 배로 늘리고 모든 데이터를 다시 배치합니다. 버킷이 넉넉해야 충돌이 줄고, 충돌이 줄어야 O(1)에 가까운 조회 속도가 유지되기 때문입니다.

 

마무리

HashMap은 "key를 숫자로 바꿔서 배열 인덱스로 바로 찾아가는" 방식으로 빠른 조회를 실현합니다. 다른 key가 같은 인덱스로 몰리는 해시 충돌은 피할 수 없지만, 자바는 이를 연결 리스트(또는 데이터가 많으면 트리)로 처리해서 최악의 경우에도 성능이 급격히 나빠지지 않도록 설계되어 있습니다.