HashMap jdk 7 데 드 순환 장면

1. 머리말
자바 프로 그래 밍 에 사용 되 는 집합 용기 가 매우 많 습 니 다. hashmap 은 그 중의 하나 입 니 다.
2. 데이터 구조
hashmap 바 텀 데이터 구 조 는 jdk 8 이전에 배열 에 링크 를 추가 하고 jdk 8 에서 배열, 링크, 빨 간 검 은 나무 로 바 뀌 었 습 니 다.
3. 자물쇠
jdk 7 버 전의 hashmap 는 다 중 스 레 드 환경 에서 cpu 100% 의 상황 을 초래 할 수 있 습 니 다. 다음 에 이 장면 을 분석 하 겠 습 니 다.
분석
jdk 7 확장 코드 를 먼저 붙 여 주세요.

void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry e : table) {
		while(null != e) {
			Entry next = e.next;
			if (rehash) {
				e.hash = null == e.key ? 0 : hash(e.key);
			}
			int i = indexFor(e.hash, newCapacity);
			e.next = newTable[i];
			newTable[i] = e;
			e = next;
		}
	}
}

위의 코드 를 대충 설명 하 세 요.
우선 확장 코드 입 니 다. 트리거 코드 입 니 다.
두 번 째 줄 은 새로운 배열 의 길 이 를 가 져 오 는 것 입 니 다.
다음은 확장 전의 배열 을 옮 겨 다 니 기 시작 합 니 다.
배열 아래 표 시 된 모든 노드 가 링크 일 수 있 기 때문에 while 를 통 해 링크 를 옮 겨 다 닐 수 있 습 니 다.
다음 다섯 번 째 줄 이 들 어 오 면 e 가 비어 있 지 않 고 e 의 다음 노드 를 임시 노드 에 할당 합 니 다.
여섯 번 째 줄 과 일곱 번 째 줄 은 hash 값 을 다시 계산 하 는 것 입 니 다.
9 줄 은 hash 값 과 새 배열 의 길이 에 따라 배열 아래 표 시 를 계산 합 니 다.
다음 에 이 배열 아래 에 표 시 된 노드 의 값 을 e. next 에 부여 합 니 다.
그리고 e 를 현재 배열 에 표시 합 니 다.
그리고 next 가 비어 있 지 않 으 면 다음 노드 를 계속 옮 겨 다 닙 니 다.
이렇게 정리 하면 훨씬 분명 해 집 니 다. hashmap 링크 의 확장 은 실제 적 으로 원래 의 링크 와 새로운 링크 를 위 치 를 바 꾸 고 머리 노드 에 추가 하 는 것 입 니 다.
단일 스 레 드
다음은 이 코드 에 존재 하 는 문제점 을 한 걸음 한 걸음 분석 하고 먼저 단일 스 레 드 의 상황 을 살 펴 보 겠 습 니 다.
배열 의 길이 가 2 라 고 가정 하면 table [1] 안에 세 개의 노드 가 있 는데 각각 n1 - > n2 - > n3 이다.
다음 코드 한 번.
먼저 배열 을 옮 겨 다 니 고 링크 를 옮 겨 다 니 면 중점 은 다섯 번 째 줄 부터 시작 합 니 다. 현재 e = n1, e. next = n2 입 니 다. 그러면 이때 next = n2 에서 10 번 째 줄 new Table [i] = null 까지 입 니 다. 따라서 e. next = null 은 현재 의 e 즉 n1 을 new Table [i] 에 할당 합 니 다. 그러면 new Table [i] = n1.열 두 번 째 줄 e = next, 즉 e = n2 로 다음 순환 에 들 어 갑 니 다.최종 결 과 는 n3 - > n2 - > n1 입 니 다.
단일 스 레 드 환경 에 서 는 문제 가 없다.다음은 다 중 스 레 드 를 보 겠 습 니 다.
다 중 스 레 드
현재 t1, t2 두 개의 스 레 드 가 있 습 니 다. table 은 길이 가 2 인 배열 입 니 다. table [1] 또는 n1 - > n2 - > n3 입 니 다.
다음 에 t1 스 레 드 는 n1 을 새 배열 에 성공 적 으로 넣 었 습 니 다. 이때 변 수 는 new Table [i] = n1, e = n2, e. next = n3 입 니 다.
그러면 t1 스 레 드 가 다시 10 번 째 줄 로 갈 때 table [i] = n1, e = n2, next = n3, 그러면 t2 스 레 드 는 확장 을 하고 다섯 번 째 줄 로 갑 니 다. 이때 next 를 e. next 로 바 꿉 니 다. 이때 t1 스 레 드 는 n1 을 e. next 에 할당 하 였 기 때문에 t2 스 레 드 는 다섯 번 째 줄 에서 n1 을 next 에 부여 합 니 다. 그러면 다음 에 n1 노드 를 옮 겨 다 니 며 폐 환 을 형성 합 니 다.순환 은 이렇게 온다.
왜 이 문제 가 생 겼 을 까?jdk 7 에 서 는 같은 hash 의 노드 를 링크 의 머리 에 추가 하기 때 문 입 니 다.
4. jdk 8 의 개선
jdk 8 에서 이 점 을 개선 하여 같은 hash 의 노드 를 링크 의 끝 에 추가 하면 폐쇄 고리 가 형성 되 지 않 습 니 다.링크 의 끝 에 놓 을 때마다 링크 를 옮 겨 다 녀 야 하기 때문에 jdk 8 에서 링크 의 길이 가 8 보다 클 때 빨간색 과 검은색 나무 로 전환 합 니 다.이것 도 체인 시 계 를 최적화 시 킬 수 있다.
5. 총화
마지막 으로 다 중 스 레 드 장면 에 서 는 Concurrent HashMap, 단일 스 레 드 장면 에 서 는 HashMap 을 사용 합 니 다.