개발 학습 실습실

이 사이트의 실습은 자바스크립트를 켜야 움직입니다. 아래는 같은 내용을 글로 적은 것입니다.

공부 › Java › 컬렉션

HashMap 내부

HashMap은 키를 어디에 넣고 어떻게 찾나

키의 hashCode로 버킷 번호를 정해 넣습니다. hashCode로 정한 버킷 번호가 겹치면 한 버킷에 줄줄이 달리고, 항목이 많아지면 버킷을 두 배로 늘립니다.

실행으로 대조 · JDK 21의 실제 HashMap 내부와 360단계 대조

이 실습에 나오는 개념

해시 테이블과 HashMap
키를 해시 함수에 넣어 나온 값으로 저장 위치(버킷)를 정하는 자료구조다. 키만 알면 위치를 바로 계산할 수 있어 조회, 삽입, 삭제가 평균 O(1)이다. 자바의 HashMap이 이 구조이며, 순서를 보장하지 않고 스레드 안전하지 않다.
해시 충돌
서로 다른 키가 같은 버킷에 배정되는 현상이다. 버킷 수는 유한하므로 피할 수 없다. 자바의 HashMap은 같은 버킷의 엔트리들을 연결 리스트로 이어 두고, 한 버킷에 너무 많이 몰리면 레드-블랙 트리로 바꿔 탐색 시간을 줄인다. 충돌이 많을수록 성능이 떨어지므로 hashCode가 값을 고르게 분산해야 한다.
로드 팩터와 리사이즈
로드 팩터는 해시 테이블이 얼마나 찼을 때 크기를 늘릴지 정하는 비율이다. HashMap의 기본값은 0.75로, 저장된 엔트리 수가 버킷 수의 75%를 넘으면 버킷 수를 두 배로 늘리고 엔트리들을 다시 배치한다(리사이즈). 리사이즈는 비용이 크므로 넣을 양을 알면 초기 용량을 미리 지정하는 것이 좋다.
레드-블랙 트리
스스로 균형을 맞추는 이진 탐색 트리의 한 종류다. 삽입과 삭제 때마다 규칙에 따라 구조를 조정해 한쪽으로 치우치지 않게 하므로 조회, 삽입, 삭제가 항상 O(log n)이다. 자바의 TreeMap과 TreeSet, 그리고 충돌이 많은 HashMap 버킷에 쓰인다.
equals와 hashCode 규약
equals()로 같다고 판단되는 두 객체는 반드시 같은 hashCode() 값을 반환해야 한다는 규칙이다. HashMap이나 HashSet은 먼저 해시 값으로 저장 위치를 찾고 그 안에서 equals로 비교하기 때문에, equals만 재정의하면 내용이 같은 객체를 찾지 못한다. 따라서 두 메서드는 항상 같은 필드를 기준으로 함께 재정의한다.

이렇게 바꿔 보세요

처음 설정으로 실행하면

  1. put(id 3817). hashCode는 3817, 버킷 번호는 9번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  2. put(id 9204). hashCode는 9204, 버킷 번호는 4번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  3. put(id 1466). hashCode는 1466, 버킷 번호는 10번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  4. put(id 7531). hashCode는 7531, 버킷 번호는 11번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  5. put(id 2890). hashCode는 2890, 버킷 번호는 10번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 이미 1개가 들어 있는 버킷입니다(충돌). 앞에서부터 하나씩 비교한 뒤 맨 끝에 붙였습니다.
  6. put(id 6043). hashCode는 6043, 버킷 번호는 11번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 이미 1개가 들어 있는 버킷입니다(충돌). 앞에서부터 하나씩 비교한 뒤 맨 끝에 붙였습니다.
  7. put(id 5178). hashCode는 5178, 버킷 번호는 10번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 이미 2개가 들어 있는 버킷입니다(충돌). 앞에서부터 하나씩 비교한 뒤 맨 끝에 붙였습니다.
  8. put(id 8312). hashCode는 8312, 버킷 번호는 8번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  9. put(id 4725). hashCode는 4725, 버킷 번호는 5번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  10. put(id 1039). hashCode는 1039, 버킷 번호는 15번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  11. put(id 6654). hashCode는 6654, 버킷 번호는 14번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  12. put(id 3391). hashCode는 3391, 버킷 번호는 15번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 이미 1개가 들어 있는 버킷입니다(충돌). 앞에서부터 하나씩 비교한 뒤 맨 끝에 붙였습니다.
  13. put(id 7968). hashCode는 7968, 버킷 번호는 0번(hashCode의 위아래 비트를 섞은 값을 버킷 수 16개로 나눈 나머지)입니다. 비어 있는 버킷이라 바로 넣었습니다.
  14. 저장된 개수 13개가 기준 12개(버킷 16개 × 로드 팩터 0.75)를 넘었습니다. 버킷을 16개에서 32개로 늘리고 모든 항목의 자리를 다시 정했습니다. 13개 중 8개가 새 버킷으로 옮겨 갔습니다. 다음에 늘리는 기준은 24개 초과입니다.
  15. 같은 id 3817로 새 키 객체를 만들어 다시 put. hashCode는 3817, 버킷 번호는 9번(hashCode의 위아래 비트를 섞은 값을 버킷 수 32개로 나눈 나머지)입니다. 버킷 안에서 해시가 같고 equals도 true인 키를 찾았습니다. 새 항목을 만들지 않고 값만 바꿉니다. 저장된 개수는 그대로 13개입니다.
  16. get: id 3817로 새 키 객체를 만들어 조회합니다. hashCode는 3817, 버킷 번호는 9번(hashCode의 위아래 비트를 섞은 값을 버킷 수 32개로 나눈 나머지)입니다. 버킷 안에서 1번째 노드까지 비교해 키를 찾았습니다. 값을 돌려줍니다.

실행 결과

코드

class MemberKey {
    final int id;
    MemberKey(int id) { this.id = id; }

    @Override public boolean equals(Object o) {
        return o instanceof MemberKey k && k.id == id;
    }

    @Override public int hashCode() {
        return Integer.hashCode(id);   // id 그대로
    }
}

Map<MemberKey, String> map = new HashMap<>(16, 0.75f);
for (int id : ids) {                 // id 13개
    map.put(new MemberKey(id), "회원");
}

// 처음 넣은 것과 같은 id로 새 객체를 만들어서
map.put(new MemberKey(ids[0]), "수정");
map.get(new MemberKey(ids[0]));

이 모형의 전제

초기 버킷 수는 16개로 고정했습니다. 버킷 번호 계산(해시의 위쪽 16비트를 아래쪽에 섞은 뒤 버킷 수로 나눈 나머지), 늘리는 기준(저장 개수 > 버킷 수 × 로드 팩터), 한 버킷에 9번째 노드가 달릴 때 버킷 수가 64개 미만이면 늘리고 64개 이상이면 트리로 바꾸는 규칙은 JDK HashMap 구현과 같습니다. 이 PC의 JDK 21에서 실제 HashMap 내부를 꺼내 본 결과와 대조했고, hashCode 세 가지 × 로드 팩터 세 가지로 40개씩 넣은 360단계 모두에서 버킷 수, 버킷별 개수, 트리 여부가 일치했습니다. hashCode를 재정의하지 않았을 때의 값은 실제로는 JVM이 객체마다 정하는 값이며, 여기서는 임의의 수로 대신했습니다.

앞 실습: ArrayList와 LinkedList · 다음 실습: Set과 Map의 종류

이 실습에 나오는 개념

이 실습에서 보는 것

설정

코드


      
    


    

      
그림

      

      

    


    

      

      

      

    


  


  

    

      
실행 비교

      

      

    

    

      
이렇게 바꿔 보세요