해시맵의 확장 메커니즘은 무엇입니까?

해시맵의 확장 메커니즘은 용량을 다시 계산하고 원래 배열을 새 배열로 교체하는 것입니다. 원본 배열의 모든 데이터를 다시 계산하여 새 배열을 삽입한 후 새 배열을 가리키며, 용량 확장 전 배열이 최대값에 도달한 경우 직접 임계값을 최대 정수로 설정하고 반환합니다.

이 튜토리얼의 운영 환경: windows7 시스템, java8, Dell G3 컴퓨터.

크기 조정이란 무엇인가요?

확장(크기 조정): 용량을 다시 계산하여 HashMap 개체에 요소를 지속적으로 추가하는 것입니다. HashMap 개체 내부의 배열이 더 많은 요소를 로드할 수 없는 경우 개체가 배열의 길이를 확장해야 합니다. 더 많은 요소를 로드할 수 있습니다. 물론, Java의 배열은 자동으로 확장할 수 없습니다. 새로운 배열을 사용하여 기존 배열을 작은 용량으로 교체하는 것과 마찬가지로, 물을 더 많이 담으려면 작은 양동이를 사용해야 합니다. 더 큰 버킷으로 변경합니다.

정원은 언제 확장되나요?

컨테이너에 요소를 추가할 때 임계값(threshold)보다 크거나 같은 경우, 즉 현재 컨테이너의 요소 수가 다음과 같을 때 판단됩니다. 현재 배열의 길이에 로딩 인자 값을 곱한 것보다 크면 자동으로 확장됩니다.

hashmap 확장 원리

hashMap 확장은 용량을 다시 계산하고 hashMap에 요소를 지속적으로 추가하는 것입니다. hashMap이 새 요소를 로드할 수 없으면 객체는 더 많은 요소를 로드하기 위해 배열 용량을 확장해야 합니다.

HashMap 용량 확장 특성, 로딩 인자가 클수록 공간 활용도가 높아지고 확장 전에 채워야 할 요소가 많아질수록 넣기 작업이 빨라지지만 연결 목록이 너무 길어지기 쉽습니다. 해시 충돌 가능성이 높고 가져오기 작업이 느립니다. 로딩 인자가 작을수록 가져오기 작업이 빨라지고, 연결된 목록이 짧아지며, 해시 충돌 가능성이 낮아집니다. 하지만 공간 활용도는 낮다. Put 요소가 너무 많으면 확장이 자주 발생하고 성능에 영향을 미칩니다.

HashMap의 용량 확장 원리: Hashmap의 방법은 원래 배열을 새 배열로 교체하고, 원래 배열의 모든 데이터를 다시 계산하고, 새 배열을 삽입한 다음, 다음과 같은 경우 새 배열을 가리키는 것입니다. 배열이 확장 전에 최대값에 도달한 경우 임계값을 반환된 최대 정수로 직접 설정합니다.

확장 과정

다음은 소스 코드 + 그림 + 텍스트 설명을 사용하여 HashMap의 확장 과정을 소개합니다.

/** 
 * HashMap 添加节点 
 * 
 * @param hash        当前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶，也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //数组扩容条件：1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后，数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢？  
        bucketIndex = indexFor(hash, table.length);//扩容之后，数组长度变了，在数组的下标跟数组长度有关，得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 这地方就是链表出现的地方，有2种情况 
 * 1，原来的桶bucketIndex处是没值的，那么就不会有链表出来啦 
 * 2，原来这地方有值，那么根据Entry的构造函数，把新传进来的key-value mapping放在数组上，原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  
}

위의 addEntry 메소드에서 크기(현재 컨테이너의 요소 수)가 임계값(배열 길이에 로드 인자를 곱한 값)보다 크거나 같고 기본 배열의 bucketIndex 좌표가 null이 아닌 경우, 그러면 확장(크기 조정)이 수행됩니다 ). 그렇지 않으면 확장이 발생하지 않습니다. 다음은 다음과 같은 과정에 중점을 둘 것이다 : wenni328 Blogger :

transfer (newtable);

== & gt;

전송 (newtable, inithashseedaseded (newcapacity)); (int) (newCapacity * loadFactor);

==> Threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); 확장하기 전에 먼저 배열의 참조 주소를 얻습니다. 그리고 이를 oldTable 변수에 저장한 후 확장 전 배열 길이가 int형에 저장된 최대값에 도달했는지 확인한다. 그렇다면 배열 용량이 최대값에 도달해 확장할 수 없으므로 확장을 포기한다.
아래 그림은 프로그램이 Entry[] newTable = new Entry[newCapacity]; 코드를 실행한 후의 상태를 보여줍니다.

기존 어레이를 더 작은 용량으로 교체하기 위해 더 큰 용량의 어레이를 사용하는 방법입니다. , transfer( ) 메소드는 원래 Entry 배열의 요소를 새 Entry 배열에 복사합니다.

        void resize(int newCapacity) {   //传入新的容量
            Entry[] oldTable = table;    //引用扩容前的Entry数组
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
                threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                return;
            }
     
            Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
            transfer(newTable);	此行有遗漏，勘误见下面引用	//！！将数据转移到新的Entry数组里
            table = newTable;                           //HashMap的table属性引用新的Entry数组
            threshold = (int) (newCapacity * loadFactor);此行有遗漏，勘误见下面引用//修改阈值
        }

newTable[i]의 참조는 e.next에 할당됩니다. 즉,

단일 연결 리스트의 헤드 삽입 방법을 사용합니다

. 동일한 위치의 새 요소는 항상 링크된 리스트의 헤드에 배치됩니다. 이러한 방식으로 먼저 배치됩니다(해시 충돌이 발생하는 경우). 인덱스의 요소는 결국 항목 체인의 끝에 배치됩니다. 이전 배열의 동일한 항목 체인에 있는 요소는 인덱스 위치를 다시 계산한 후 새 배열의 다른 위치에 배치될 수 있습니다.

전송 과정은 아래 그림 형태로 설명됩니다. (아래 그림의 빨간색 글꼴은 위 그림과의 차이점을 나타냅니다. 다음 그림도 이와 같으며 빨간색 글꼴 설명은 반복되지 않습니다.)

아래 그림은 프로그램 실행 완료를 보여줍니다. src[j] = null; 코드 이후의 상태(첫 번째 루프 중 상태):

먼저 table[] 배열의 참조 주소를 src[] 배열에 할당합니다.

그러면 Entry e = src[j]; src[j] 위치의 연결 리스트를 e 변수에 저장합니다. src[j]의 연결 리스트는 e에 저장용으로 주어졌으므로 과감하게 src[j]=null; 로 설정한 후 가비지 컬렉션을 기다리면 됩니다.

아래 그림은 프로그램이 Entry next = e.next; 코드를 실행한 후의 상태를 보여줍니다(첫 번째 루프 동안의 상태).

여기서 먼저 e의 값을 변경합니다. .next 다음 변수로 백업합니다. 후속 코드는 e.next의 포인터를 변경하므로 e.next의 값이 여기에 백업됩니다.

아래 그림은 프로그램이 e.next = newTable[i]; 코드를 실행한 후의 상태를 보여줍니다(첫 번째 루프 중 상태).

newTable[3]의 값이 null이므로 이므로 위 그림에 표시된 것처럼 e.next는 null입니다.

아래 그림은 프로그램이 newTable[i] = e; 코드를 실행한 후의 상태를 보여줍니다(첫 번째 루프 동안의 상태).

아래 그림은 프로그램이 e를 실행한 후의 상태를 보여줍니다. = next; code Status(첫 번째 루프 동안의 상태):

위에 표시된 것처럼 루프가 끝나면 e!=null이 판단되므로 Entry1 노드가 성공적으로 삽입됩니다. 모든 노드가 newTable로 이동할 때까지 위의 프로세스가 반복됩니다.

요약

• 확장은 특히 성능 집약적인 작업이므로 프로그래머가 HashMap을 사용할 때 맵의 잦은 확장을 피하기 위해 초기화 중에 맵의 크기를 추정하고 대략적인 값을 제공해야 합니다.
• 부하율은 수정이 가능하며 1보다 클 수도 있지만, 아주 특별한 상황이 아닌 이상 쉽게 수정하지 않는 것이 좋습니다.
• HashMap은 스레드에 안전하지 않습니다. 동시 환경에서 HashMap을 동시에 작동하지 않는 것이 좋습니다.
• JDK1.8은 HashMap의 성능을 크게 최적화하기 위해 레드-블랙 트리를 도입합니다.

더 많은 프로그래밍 관련 지식을 보려면 프로그래밍 교육을 방문하세요! !

위 내용은 해시맵의 확장 메커니즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!