hashmap 기반 확장 및 트 리 화 전면 분석

나무

//         
static final int TREEIFY_THRESHOLD = 8;
//         
static final int UNTREEIFY_THRESHOLD = 6;
/**
*         ：           >    ，         （            ）
*  ，        ，     ，      
*        、        ，        4 * TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;

첫 번 째 와 두 번 째 변 수 는 문제 가 없습니다.관건 은 세 번 째 입 니 다.배열 의 길이 가 64 보다 클 때 만 트 리 화 목록 을 만 들 수 있 습 니까?
실제로 이 두 변 수 는 서로 다른 장면 에 응용 된다.
링크 길이 가 8 보다 클 때 treeifyBin 방법 을 사용 하여 빨간색 과 검은색 나무 로 전환 하지만 treeifyBin 방법 내부 에서 하나의 판단 이 있 습 니 다.배열 의 길이 가 64 보다 클 때 만 트 리 화 를 할 수 있 고 그렇지 않 으 면 resize 확장 만 할 수 있 습 니 다.
왜 일 까요?
체인 시계 가 너무 길 고 배열 이 너무 짧 기 때문에 hash 충돌 이 자주 발생 할 수 있 습 니 다.이때 나무 형 화 는 사실은 기준 치 를 해결 하지 않 고 근본 적 인 원인 은 배열 이 너무 짧 기 때 문 입 니 다.트 리 화 를 실행 하기 전에 트 리 의 길 이 를 먼저 검사 하고 길이 가 64 보다 작 으 면 트 리 가 아 닌 확장 을 한다.
그래서 확 대 될 때 는 두 가지 상황 에서...
한도 값 초과
링크 길이 가 8 을 넘 지만 수치 길이 가 64 가 안 됩 니 다.
2.확장 메커니즘
hashmap 내부 생 성 과정
구조 기(매개 변 수 를 초기 화 하 는 것 만으로 도 데 이 터 를 추가 할 때 만 배열 과 링크 를 구축 하 는 것 을 의미 합 니 다)-put 방법-put 방법 은 resize 방법 을 호출 합 니 다(배열 이 비어 있 거나 한도 값 을 초과 할 때 put 방법 은 resize 방법 을 호출 합 니 다)
hashmap 는 어떻게 확장 합 니까?
1.hashmap 의 한도 값 threshold 설정
처음에는 한도 값 이 비어 있 었 습 니 다.
설명 되 지 않 은 hashmap 의 크기 를 설정 할 때 한도 값 설정 은 기본 크기 16*기본 부하 인자 0.75=12 입 니 다.
hashmap 의 크기 를 설명 할 때 한 함 수 를 호출 하여 한도 값 을 설정 값 보다 방금 큰 2 의 차방 으로 설정 합 니 다(예 를 들 어 설정 한 크기 는 1000 이 고 그 한도 값 은 1024 입 니 다).그 다음 에 resize 방법 에서 먼저 한도 값 을 용량 크기 에 부여 한 다음 에 용량 크기*0.75 를 한도 값 에 부여 합 니 다.
코드 는 다음 과 같 습 니 다:

Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

2.데이터 이동
배열 이 null 일 때 새 배열 을 만 듭 니 다.
배열 이 비어 있 지 않 으 면 용량 과 한도 값 을 모두*2 로 만 들 고 용량 이 두 배 인 배열 을 만 든 다음 에 기 존 배열 의 데 이 터 를 모두 새 배열 로 옮 깁 니 다.
확장 전의 table 크기 가 2 의 N 제곱 이 라 고 가정 하고 요소 의 table 색인 은 hash 값 의 후 N 비트 로 확정 합 니 다.
확장 후의 table 크기 는 2 의 N+1 차방 이 고 그 중에서 요소 의 table 색인 은 hash 값 의 후 N+1 비트 로 확정 되 어 원래 보다 한 자리 더 많 습 니 다.
이전 데 이 터 는 1.7 과 같이 hash 값 을 다시 계산 하지 않 습 니 다.(hash 값 을 계산 하 는 데 소요 되 는 시간 이 많 습 니 다)색인 에 추 가 된 bit 비트 가 1 인지 0 인지 만 보십시오.
0 이면 새 배열 에서 원래 위치 와 같 습 니 다.
1 이면 새 제자리+oldCap 에 있 으 면 됩 니 다.
3.용량 계산 공식
확장 은 특히 성능 을 소모 하 는 작업 이기 때문에 프로그래머 가 HashMap 을 사용 할 때 맵 의 크기 를 추산 하고 초기 화 할 때 대략적인 수 치 를 주어 맵 의 빈번 한 확장 을 피한다.
HashMap 의 용량 계산 공식:size/0.75+1.
원 리 는 바로 한도 값(배열 길이*0.75)>실제 용량 을 확보 하 는 것 이다.
HashMap 의 최대 용량 은 왜 2 의 30 제곱(1 왼쪽 이동 30)입 니까?
hashmap 의 소스 코드 를 읽 는 과정 에서 나 는 hashmap 의 최대 용량 에 대한 제한 을 보고 의문 이 생 겼 다.

    /**
     * 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;

왜 최대 용량 이 1<30 입 니까?
탐구 과정 1 C 가 왜 30 인지
우선<<<이 조작 부 호 는 이해 해 야 합 니 다.일반적인 상황 에서 11<30.그것 은 1 을 왼쪽으로 30 자리,즉 0010...0 으로 옮 기 는 것 을 대표 한다.
다음 코드 를 보십시오:

public static void main(String[] args){
        for (int i = 30; i <= 33; i++) {
            System.out.println("1 << "+ i +" = "+(1 << i));
        }
        System.out.println("1 << -1 = " + (1 << -1));
}

출력 결 과 는:
1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648
결과 분석:

int 유형 은 32 비트 정형 으로 4 개의 바이트 를 차지한다.

자바 의 원본 형식 에는 기호 가 없 는 형식 이 없습니다.->그래서 첫 번 째 는 기호 비트 의 정수 가 0 이 고 마이너스 가 1

이다.

자바 에 저 장 된 것 은 패 치 입 니 다.1 왼쪽 에서 31 비트 를 이동 하 는 것 은 16 진법 의 0x 80000000 은-2147483648 C>를 대표 하기 때문에 최대 30

밖 에 안 됩 니 다.
탐구 과정 2 C 왜 1<30>
탐구 끝 1.왜 30 인지 조금 알 고 있 을 거 라 고 믿 습 니 다.그런데 왜 1<<30,0x7fffff 즉 Integer.MAX 가 아니 라VALUE
우 리 는 먼저 코드 의 주석 을 본다.

 /**
     * 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;

구조 함수 가 들 어 오 는 값 이 이 수 보다 크 면 이 수로 바 꾸 는 것 이다.
ok,구조 함수 의 호출 을 봅 시다.

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);
    }

그 중의 이 한 마디 는

if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

이것 을 보고 의문 이 생 겼 습 니 다.만약 제 가 저축 하고 자 하 는 수량 이 MAXIMUM 보다 많다 면CAPACITY,너 는 아직도 나의 용량 을 MAXIMUM 로 줄 였 다.CAPACITY？？？
서 두 르 지 말고 계속 보 세 요:resize()방법 중 에 한 마디 가 있 습 니 다.

if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
}

여기 서 보면 사실 hashmap 의'최대 용량'은 Integer.MAX 입 니 다.VALUE;
총결산
MAXIMUM_CAPACITY 는 2 의 멱 방 중 최대 치 로 서 이 값 의 역할 은 비교적 광범 위 하 게 관련된다.그 중 하 나 는 hashmap 에서 용량 이 2 의 k 제곱 을 확보 하 는 것 이다.들 어 오 는 초기 용량 이 2 의 k 제곱 이 아니 더 라 도 table SizeFor()방법 은 당신 의 용량 을 2 의 k 제곱 으로 설정 할 것 이다.이때 MAXVALUE 는 최대 용량 치 를 나타 낸다.
또 하 나 는 threshold 입 니 다.hashmap 에 대해 조금 이라도 아 는 사람 은 threshold=초기 용량*로드 인 자 를 알 수 있 습 니 다.확 장 된 문턱 이다.실제 사용 용량 에 해당 한다.확장 은 두 배로 늘 었 다.그러면 용량 이 MAXIMUM 에 도착 하면CAPACITY,이때 다시 확장 하면 1<31 정형 넘 침.
그래서 Integer.MAXVALUE 는 최종 용량 이지 만 threshold 의 신분 입 니 다.이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.