하 쉬 맵 을 깊이 파다

머리말
자바 개발 을 한 친구 들 은 모두 HashMap 과 같은 종 류 를 잘 알 고 있다 고 믿 습 니 다.이것 은 hashing 원 리 를 바탕 으로 Key-Value 키 쌍 을 저장 하 는 집합 입 니 다.그 중의 모든 키 는Entry이 라 고 합 니 다.이 키 들 은 각각 한 배열 에 저장 되 어 있 습 니 다.시스템 은hash방법 에 따라 Key-Value 의 저장 위 치 를 계산 하고 key 를 통 해 value 를 빠르게 액세스 할 수 있 습 니 다.HashMap 은 hashing 원 리 를 바탕 으로 키 값 쌍(Key-Value)을put방법 으로 전송 할 때 이 keyhashcode방법 으로 key 의 hashcode 값 을 계산 한 다음 이 hashcode 값 에 따라 배열 의 위 치 를 찾 아 저장 대상(HashMap 은 링크 를 사용 하여 충돌 문 제 를 해결 합 니 다.충돌 이 발생 하면...대상 은 링크 의 다음 노드 에 저 장 됩 니 다.링크 의 모든 노드 에 저 장 됩 니 다Entry대상 은 JDK 1.8+에서 링크 의 노드 개수 가 일정 치 를 초과 할 때 빨간색 과 검은색 트 리 로 저 장 됩 니 다).get방법 으로 key 에 들 어가 해당 하 는 값 을 얻 을 때또한 키 의hashcode방법 을 통 해 배열 에 저 장 된 위 치 를 찾 은 다음 키 대상 의eqauls방법 으로 대응 하 는 value 값 을 찾 습 니 다.다음은 그 내부 의 실현 세부 사항 을 살 펴 보 자.PS： JDK 1.8 ）
1.2 왜 용량 은 항상 2 의 정수 차 멱 입 니까?
키 가 배열 에 대응 하 는 아래 표 시 를 가 져 오 는 것 은 키 의 해시 값 과 배열 의 길 이 를 줄 여 연산 을 통 해 확인 되 기 때 문 입 니 다tab[(n - 1) & hash].배열 의 길이 n 이 2 인 정수 차 멱 이 이렇게 n-1 연산 을 한 후에 이전 1 인 비트 뒤 에는 모두 1 이 었 다.그러면(n - 1) & hash이후 해당 비트 의 값 이 1 일 수도 있 고 0 일 수도 있다 는 것 을 보증 할 수 있다.이것 은 key 의 해시 값 에 달 려 있다.그러면 산열 의 균일 성 을 확보 하고 같은 시간 에 연산(비트 연산)과 효율 이 높다.배열 의 길이 n 이 2 의 정수 차 멱 이 아니라면 더 많은 hash 충돌 을 일 으 킬 수 있 습 니 다.HashMap 은 다음 과 같은 네 가지 무 거 운 구조 방법 을 제공 하여 서로 다른 사용 장면 을 만족 시 켰 다.

무 참 구조:HashMap()이 방법 을 사용 하면 모두 HashMap 의 기본 설정 매개 변수

를 사용 합 니 다.

지정 용량 초기 값 구조:HashMap(int initialCapacity),HashMap 초기 화 시 용량 크기 지정

용량 초기 값 과 확장 인자 구 조 를 지정 합 니 다.HashMap(int initialCapacity, float loadFactor)사용자 정의 초기 화 용량 과 확장 인자

를 사용 합 니 다.

Map을 통 해 HashMap:HashMap(Map extends K, ? extends V> m)을 구성 하고 기본 적 인 확장 인 자 를 사용 하 며 용량 크기 는 들 어 오 는Map크기 로 결정 한다

.
앞의 세 가지 구조 방법 은 최종 적 으로 세 번 째,즉 사용자 정의 용량 초기 값 과 확장 인자 구조HashMap(int initialCapacity, float loadFactor)를 호출 하 는데 그 소스 코드 는 다음 과 같다.

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

원본 코드 의 실현 을 통 해 알 수 있 듯 이 만약 에 우리 가 들 어 오 는 초기 용량 치가MAXIMUM_CAPACITY보다 크 면 용량 을MAXIMUM_CAPACITY으로 설정 하고 그 값 은 다음 과 같다.

/**
  * The maximum capacity, used if a higher value is implicitly specified
  * by either of the constructors with arguments.
  * MUST be a power of two <= 1<<30.
  */
static final int MAXIMUM_CAPACITY = 1 << 30;

즉 용량 의 최대 치가 2 인 30 제곱1 << 30이다.우 리 는 HashMap 의 용량 이 항상 2 의 정수 차 멱 이라는 것 을 알 고 있 습 니 다.우리 가 들 어 오 는 초기 용량 이 무엇 이 든 이 값 에 가장 가 깝 고 2 의 정수 차 멱 을 HashMap 의 초기 용량 으로 사용 합 니 다.이 단 계 는tableSizeFor방법 을 통 해 이 루어 집 니 다.우리 가 그것 의 소스 코드 를 보 겠 습 니 다.
방법의 주석 을 통 해 우 리 는 ~~~을 알 수 있 습 니 다.이 방법의 반환 치 는 항상 2 의 정수 차 멱 입 니 다.그것 은 어떻게 하 는 것 입 니까?다음 에 우 리 는 하나의 예 를 통 해 한 걸음 한 걸음 보면 우리 가 들 어 오 는 초기 용량 크기cap의 값cap이 15 라 고 가정 한다.
① 단계:cap - 1후n의 값 을 14(15-1)로 한다.
② 단계:n의 값 을 오른쪽으로 1 자리 옮 긴 후n와 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
③ 단계:n의 값 을 오른쪽으로 2 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)한다.다음은 구체 적 인 계산 과정 이다.
④ 단계:n의 값 을 오른쪽으로 4 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
]
⑤ 단계:n의 값 을 오른쪽으로 8 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
⑥ 단계:n의 값 을 오른쪽으로 16 자리 옮 긴 후n와 (둘 다 0 결과 0,다른 상황 은 1)진행 합 니 다.다음은 구체 적 인 계산 과정 입 니 다.
]
마지막 으로n의 값 이0보다 작 으 면 1 을 되 돌려 주 고 최대 치MAXIMUM_CAPACITY보다 크 면MAXIMUM_CAPACITY를 되 돌려 주 며 그렇지 않 으 면 되 돌려 준다n + 1.현재 n 은 15 이기 때문에 n+1(16)로 돌아 가 고 16 은 2 의 4 차 멱 이다.어떤 친구 들 은 방금 위 에서 가설 한 초기 용량 크기cap가 15 이 고 원래 2 의 정수 차 멱 이 아니 라 고 물 을 수 있 습 니 다.만약 에 제 가 초기 용량 에 들 어간 것 이 2 의 정수 차 멱 이 라면 어떻게 되 겠 습 니까?현재 전 송 된 초기 용량 크기 의 32(2 의 5 제곱)를 가정 하여 결과 가 무엇 인지 봅 시다.
① 단계:cap - 1후n의 값 을 31(32-1)로 한다.
② 단계:n의 값 을 오른쪽으로 1 자리 옮 긴 후n와 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
③ 단계:n의 값 을 오른쪽으로 2 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)한다.다음은 구체 적 인 계산 과정 이다.
④ 단계:n의 값 을 오른쪽으로 4 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
]
⑤ 단계:n의 값 을 오른쪽으로 8 자리 옮 긴 다음n과 (둘 다 0 결과 0 이 고 다른 상황 은 1)구체 적 인 계산 과정 이다.
]
⑥ 단계:n의 값 을 오른쪽으로 16 자리 옮 긴 후n와 (둘 다 0 결과 0,다른 상황 은 1)진행 합 니 다.다음은 구체 적 인 계산 과정 입 니 다.
]
상기 6 단계 계산 을 통 해 n 의 수 치 는 31 이 고 0 보다 작 으 며MAXIMUM_CAPACITY반환n + 1보다 작 기 때문에 계산 을 거 친 초기 용량 크기 의 32 이다.조금 만 정리 하면 우 리 는 우리 가 들 어 오 는 초기 용량 의 크기 가 2 의 정수 차 미터 가 아니라면 계산 을 거 친 초기 용량 의 크기 는 우리 가 들 어 오 는 초기 용량 의 최소 값 보다 크 고 2 의 정수 차 미터 라 는 것 을 알 수 있다.세심 한 친 구 는 왜 첫 번 째 단계cap - 1의 조작 을 해 야 하 는 지 알 게 될 것 이다.그것 은-1 연산 을 하지 않 으 면 우리 가 들 어 오 는 초기 용량 크기 가 2 의 정수 차 멱 일 때 상기 절 차 를 통 해 계산 한 결과 값 이 들 어 오 는 값 의 2 배 이기 때문이다.만약 에 우리 가 들 어 오 는 초기 용량 의 크기 가 32 이 고 이때 ① 단계cap - 1의 조작 이 없다 고 가정 하면 상기 ②,③,④,⑤,⑥ 를 통 해63를 한 다음 에n + 1조작 을 한 결과64는 전달 치 32 의 2 배 로 예상 결과32와 일치 하지 않 는 다.이 초기 용량 을 계산 하 는 알고리즘 은 매우 교묘 하 다.먼저-1 의 조작 을 하여 초기 용량 값 이 2 인 정수 차 멱 에 들 어 갈 때 들 어 오 는 원시 값 을 되 돌려 준다.
1.3 hash 방법 은 어떻게 실현 되 었 습 니까?get방법 을 통 해 key 에 대응 하 는 Value 값 을 얻 거나put방법 으로 Key-Value 키 값 을 저장 할 때 키 의 해시 값 에 따라 배열 의 위 치 를 찾 습 니 다.HashMap 의hash방법 이 어떻게 실현 되 는 지 살 펴 보 겠 습 니 다.소스 코드 는 다음 과 같 습 니 다.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key 가null일 때 0 을 되 돌려 줍 니 다.그렇지 않 으 면h = key.hashCode()) ^ (h >>> 16연산 을 합 니 다.먼저 key 의hashCode방법 으로 key 의 해시 값 을 얻 은 다음 에 key 의 해시 값 과 오른쪽으로 16 비트 이동 한 후의 값 을 이동 하거나 연산 합 니 다(같은 0,다른 1,약칭 .왜 key 의 해시 값 을 얻 으 려 면 이 또는 연산 을 해 야 합 니까?key 의 해시 값 을 직접 되 돌려 주 는 것 도 문제 가 없 는 것 같 습 니 다.뒤의 차이 나 연산 이 없 으 면 해시 값 을 직접 되 돌려 줍 니 다.우 리 는 배열 의 길이 가 16 이 라 고 가정 합 니 다.현재 HashMap 에 저장 할 세 개의 키 쌍 의 key 의 해시 값 은 각각 32831,33554495,2097215 이 고 hash 방법 에 따라 값 을 되 돌려 배열 의 위치(n - 1) & hash로 찾 습 니 다.상기 세 개의 값 과 15(16-1)진행& （ 1 1， 0）은 다음 과 같다.
]
상기 세 개의 해시 값 이 모두 포 지 셔 닝 된 배열 아래 15 로 표 시 된 위 치 를 발견 할 수 있 습 니 다.따라서hash방법 이 뒤에 해시 값 과 오른쪽으로 16 비트 이동 한 후의 값 과 다른 값 이나 연산 을 하지 않 으 면 배열 의 길이 가 시간 을 비교 하면 쉽게 발생 한다 .즉,여러 key(서로 다른 해시 값)는 배열 의 같은 위치 에 위치 하 게 된다.즉,같은 링크 나 빨 간 검 은 나무 에 넣 는 것 이다.이때 키 의 해시 값 은 낮은 비트 만 연산 에 참여 할 수 있 기 때문에 우리 의 기대 와 맞지 않 는 다.이 를 통 해 알 수 있 듯 이hash방법 은 key 의 해시 수 치 를 오른쪽으로 16 비트 이동 한 후에 이 또는 연산 을 하면 해시 충돌 횟수 를 줄 이 고 높 은 위치 와 낮은 위 치 를 모두 연산 에 참여 하여 분산 성 을 높 일 수 있다.
총화
HashMap 은 사실 우리 가 깊이 연구 해 야 할 점 이 많 습 니 다.위의 두 가지 방법 을 알 아 본 후에 작가 의 코드 디자인 능력 에 탄복 할 수 밖 에 없습니다.JDK 에는 우수한 소스 코드 가 많 습 니 다.코드 를 볼 때 몇 번 을 더 보고 몇 가지 이 유 를 물 어 봐 야 합 니 다.특히 전형 적 인 소스 코드 를 본 다음 에 이런 사상 을 우리 의 실제 업무 에 활용 해 야 합 니 다.