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)>실제 용량 을 확보 하 는 것 이다.