[자바] JDK 1.8 이전에 HashMap 병발 상황 이 왜 순환 이 되 는 지

원본 주소:https://www.jianshu.com/p/4930801e23c8
 
 
put 작업 을 한도 값 까지 진행 할 때 확장 을 진행 할 때 순환 을 초래 할 수 있 습 니 다.

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    // OldTable         ，    NewTable 
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;
                //       Map    
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

 
hash 알고리즘 이 key mod Entry 배열 의 길이 transfer () 과정 이 라 고 가정 합 니 다.
 
 
hash 알고리즘 이 key mod Entry 배열 의 길 이 를 간단하게 사용한다 고 가정 합 니 다.여기 서 e 와 next 의 지향 에 주의해 야 합 니 다. resize () 를 병행 할 때 이 두 지침 은 잠 금 해제 에 중요 한 역할 을 합 니 다.방법 집행 상황 에 따라 원래 맵 의 링크 요 소 는 새로운 맵 에서 순 서 를 뒤 바 꿉 니 다. 위의 그림 에서 보 듯 이 resize () 를 한 번 거 친 후에 key 가 7 인 노드 는 key 가 3 인 노드 앞 에 있 습 니 다.

do {
  Entry next = e.next;
  //       Map    
  int i = indexFor(e.hash, newCapacity);
  e.next = newTable[i];
  newTable[i] = e;
   e = next;
} while (e != null);

이 코드 를 다시 붙 이 는 것 은 이 do while 순환 이 자물쇠 가 생기 는 주범 임 을 강조 하 는 것 이다.다음은 자물쇠 가 생기 는 과정 을 모 의 한다.주의 하 세 요. 모든 상황 에서 자물쇠 가 생기 는 것 은 아 닙 니 다. 이것 도 스 레 드 간 의 호흡 이 필요 합 니 다. 어떻게 말 해 야 합 니까? 그림 에서 보 듯 이:
① 이때 스 레 드 1, e 는 key 가 3 인 노드 를 가리 키 고 next 는 key 가 7 인 노드 를 가리킨다.이 점 은 매우 중요 하 니 적어 라.실행 스 레 드 2.
 
② 스 레 드 2 가 정상적으로 실행 된다 고 가정 하면 종료 후의 상 태 는 다음 과 같다.
 
③ 이때 스 레 드 가 깨 어 나 면 스 레 드 1 의 작업 공간 에서 e 와 next 가 가리 키 는 요 소 는 key 가 3 과 7 의 노드 이다.스 레 드 가 시작 되 자마자 실 행 됩 니 다.
 
④ 아직 문제 가 발생 하지 않 았 으 므 로 스 레 드 작업 을 계속 합 니 다.키 (7) 를 떼 고 뉴 테이블 [i] 의 첫 번 째 에 놓 고 e 와 next 를 아래로 옮 깁 니 다.
 
e. next = new Table [i] 로 인해 key (3). next 는 key (7) 를 가 리 켰 다.메모: 이때 key (7). next 는 key (3) 를 가리 키 고 링 링크 가 이렇게 나 타 났 습 니 다.
 
 
* 전재 자 요약:
근본 적 인 원인 은 JDK 1.8 이전의 확장 이 결점 을 거꾸로 하기 때문이다.
사실은 병발 할 때 낡은 배열 의 데 이 터 를 새 배열 의 대응 위치 로 옮 길 때 이 위치 에 낡은 배열 의 데이터 가 있어 서 는 안 되 고 그렇지 않 으 면 링 이 형성 된다.
 
JDK 1.8 의 해결 (네 개의 지침)
두 개의 지침 을 통 해 loHead / loTail 은 다시 hash 후 위치 가 변 하지 않 는 체인 헤더 와 꼬리 를 가리킨다.
그리고 hiHead / hiTail 은 hash 후 위치 + oldCap 의 체인 헤더 와 끝 을 가리 키 고 있 습 니 다.
역순 의 문 제 를 피하 고 순환 의 문 제 를 해결한다.
하지만 HashMap 은 병발 문제 가 있 기 때문에 Concurrent HashMap 을 사용 해 야 합 니 다.