자바 의 HashMap 비 스 레 드 안전 시 행동

자바 의 HashMap 비 스 레 드 안전 시 행동
우 리 는 HashMap 이 다 중 스 레 드 환경 에서 안전 하지 않다 는 것 을 알 고 있 습 니 다.여기 서 말 하 는 안전 하지 않 은 것 은 상대 적 인 것 입 니 다(적어도 2 개의 스 레 드 가 있 습 니 다).스 레 드 를 읽 거나 스 레 드 를 하나 만 쓴다 면 HashMap 은 정상적으로 사용 할 수 있 습 니 다.다음은 본론 으로 들 어 갑 니 다.
나타 날 수 있 는 현상
구체 적 분석
총화
부록
tips:아래 에 언급 된 hashIndex 는 하나의 요소 가 hashmap 에 넣 었 을 때 키.hashcode&(table.size()-1)에 따라 table 의 위 치 를 결정 하 는 것 을 말한다.
table 은 Node 형식 으로 배열 되 어 있 습 니 다.Node 는 hashmap 의 내부 클래스 로 hashmap 의 요소 의 일부 속성 을 묘사 합 니 다.
1.나타 날 수 있 는 현상
1.데이터 오류(중복 데이터 발생)2.데이터 손실(데이터 삽입 에 성 공 했 지만 분실)3.rehash 로 인 한 데이터 손실 4.rehash 로 인 한 순환
2.구체 적 분석
1.데이터 오류

 table
 ------ |  33  | 
 ------  ------ ------ |  1   |  ->|  9   |  
 ------ ------  ------ |      | 
 ------  ------ |      | 
 ------ 

rehash 생각 안 해.두 스 레 드 가 각각 같은 요소 A 를 삽입 할 때 A 의 hashIndex(A.hashcode()&(table.size()-1)를 먼저 검사 합 니 다.이 hashIndex 에 대응 하 는 링크 에 key 가 존재 하 는 지 비교 합 니 다.이 때 두 스 레 드 가 기록 작업 을 할 때 키 가 존재 하지 않 는 것 을 발견 하면 삽입 작업 을 준비 합 니 다.삽입 작업 은 이 링크 의 머리 에 요 소 를 삽입 하 는 것 입 니 다.기록 할 때 짧 은 우선 순위 가 있다 고 가정 하면 결 과 는 다음 과 같 을 수 있 습 니 다.

  table
 ------ |  33  | 
 ------  ------ ------ |  1   |  ->|  9   |  
 ------ ------  ------ ------ |  A   |  ->|  A   |  
 ------ ------  ------ |      | 
 ------ 

우 리 는 hashmap 가 두 개의 같은 키 가 나타 나 는 것 을 허락 하지 않 는 다 는 것 을 알 고 있 지만,이러한 상황 에 서 는 나타 날 수 있다.
2.데이터 분실
아니면 두 스 레 드 입 니까?이번에 쓴 것 은 서로 다른 데이터 A 입 니 다.B.hashIndex 의 값 을 계산 하 는 것 은 같 습 니 다.즉,A,B 는 같은 링크 에 꽂 힐 것 입 니 다.그들 이 거의 동시에 같은 링크 를 쓴다 고 가정 합 니 다.우 리 는 요소 A 를 삽입 하 는 과정 을 알 아야 합 니 다.여기 서 약술 해 야 합 니 다.(1)A 의 hashIndex(2)대응 하 는 링크 에서 key 가 존재 하 는 지 찾 아야 합 니 다.A 를 새 체인 헤더 노드 로 삽입 합 니 다.
두 스 레 드 가 거의 동시에 실행 되 었 다 고 가정 하면(3)실행(4)후에 하나의 요소 체인 이 버 려 질 수 있 습 니 다.그 러 니까 데이터 가 하나 없어 진 다 는 거 야.

 table
 ------     
|  33  | 
 ------     
 ------      ------         
|  1   |  ->|  9   |  
 ------      ------        
 ------          ------          ------
|      |  ----->|  B   |  ----> |   A  |
 ------   \      ------          ------
           \（  ）  
            \    ------          ------
 ------      -->|   C  |  ----> |   A  |
|  33  |         ------          ------
 ------ 

그림 이 비교적 추 하 니 양해 해 주 십시오.
위의 그림 에서 보 듯 이 B,C 는 모두 링크 의 새로운 머리 노드 가 되 기 를 원 하고 모두 원래 의 머리 노드 A 와 링크 를 완성 했다.그러나 실제 B,C 는 하나만 머리 결점 이 될 수 있 기 때문에 그 중 하 나 는 있 는 데이터 체인 을 잃 어 버 릴 수 있다.이것 이 바로 데이터 가 바로 그 원인 이다.
3.rehash 로 인 한 데이터 손실
rehash 를 여러 번 언급 한 이상 rehash 의 과정 도 설명 하 겠 습 니 다.다음은 일부 코드 입 니 다.

Node<K,V> loHead = null, loTail = null;     
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
    next = e.next;
    if ((e.hash & oldCap) == 0) {
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    else {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

e 는 table 배열 의 요소,즉 각 링크 의 끝 점 임 을 설명 합 니 다.oldcap 은 오래된 table 의 길 이 를 말 합 니 다.new Tab 은 새로운 table 을 말 합 니 다.rehash 의 hashIndex 계산 방식 은 put 와 약간 다르다.put: A.hashcode & (table.size() -1) rehash: e.hash & oldCap
이미지 의 예:table 길이 가 4 라 고 가정 합 니 다.
인덱스 인덱스
0
1
2
3
머리 결산 점 hash
1
다음 결점
5
다음 결점
9
ok,요소 개수/해시 슬롯 개수=3/4 가 기본 rehash 임계 점 에 도 착 했 기 때문에 다음 에 rehash 를 시작 합 니 다.index 색인 이 0 인 링크 를 먼저 취하 고 비어 있 는 것 을 발견 하여 조작 하지 않 습 니 다.index 색인 이 1 인 링크 를 가 져 오 면 머리 노드 가 비어 있 지 않 습 니 다.e=1,next=5.e.hash&oldCap=1&4=0 에 따 르 면.loHead = e; loTail = e; loHead = loTail = e。 next != null 。 e.hash&oldCap=5&4!=0。hiHead = e; hiTail = e; hiHead = hiTail = e。 next != null 。 e.hash&oldCap=9&4=0 에 따 르 면.loHead = e; loTail = e; loHead = 1 -> 9 = loTail。
이로써 index 색인 이 1 인 링크 rehash 가 완료 되 었 습 니 다.새로운 배열 에 넣 습 니 다.여기 서 loHead,loTail 과 hiHead,hiTail 의 의 미 를 설명 한다.이전 e.hash&oldCap 의 결과 에 따 르 면 e.hash&oldCap 이 된다 면!=0,oldCapnewCap,e.hash&oldCap=0.이것 역시 검증 할 수 있다.이 결론 을 알 았 다 면 loHead,loTail 의 역할 은 rehash 를 저장 한 후에 도 hashIndex 는 원래 의 요소 이다.한편,hiHead,hiTail 은 hashIndex 변화 요 소 를 저장 합 니 다.일반적으로 여 기 는 하나의 요소 만 있 습 니 다.그러면 다음 작업 은 비교적 밝 아 지고 각각 두 개의 체인 시 계 를 새로운 table 에 연결 합 니 다.hihead 에 대해 서 는 hiTail 이 어느 tableIndex 에 삽입 되 었 는 지,new Tab[j+oldCap]=hiHead 이 동작 은 이미 설명 되 었 습 니 다.j 는 이 요소 가 원래 table 에 있 는 tableIndex 를 말 합 니 다.
여기까지 말 하면 rehash 의 과정 은 대체적으로 끝 났 습 니 다.그런데 왜 다 중 스 레 드 쓰기 도 rehash 작업 할 때 이상 이 생 길 수 있 습 니까?rehash 는 데 이 터 를 삽입 한 후에 발생 합 니 다(주의:이때 이미 삽입 완료).부하 인자 가 한도 값 에 도달 한 것 을 발견 합 니 다.그럼 rehash 작업 이 실 행 됩 니 다.기 존 스 레 드 A,B 는 hashmap 를 동시에 기록 합 니 다.A 를 기록 한 후에 요소 가 너무 많은 것 을 발견 하고 rehash 를 진행 합 니 다.원래 table 길이 가 4 라 고 가정 합 니 다.A 가 tableIndex=1 에 옮 겨 다 닐 때(tableIndex=0 의 링크 가 rehash 완료 되 었 음 을 설명 합 니 다).스 레 드 B 는 tableIndex=0 에 요 소 를 삽입 하지만 스 레 드 A 는 tableIndex=0 에 대해 처리 되 었 습 니 다.더 이상 신경 쓰 지 않 습 니 다.그래서 A 는 B 가 새로운 데 이 터 를 삽 입 했 거나 B 가 삽 입 된 데 이 터 를 버 렸 다 는 것 을 몰 랐 다.계속 옮 겨 다 녀.
다음 두 가지 상황 이 있 습 니 다.1.B 스 레 드 삽입 작업 이 끝 났 을 때 A 스 레 드 의 rehash 작업 이 완료 되 었 습 니 다.새로운 table 은 오래된 table 을 바 꾸 었 습 니 다.B 스 레 드 삽입 이 끝 난 후에 rehash 를 해 야 하 는 지 확인 할 때 새로운 table 을 받 았 기 때문에 rehash 를 하지 않 아 도 됩 니 다.그러나 B 스 레 드 는 자신 이 삽입 한 데 이 터 를 잃 어 버 렸 을 지도 모른다.2.B 스 레 드 삽입 작업 이 완료 되 었 을 때 A 스 레 드 는 rehash 작업 이 완료 되 지 않 았 습 니 다.그 결과 B 가 데 이 터 를 삽입 한 후에 도 rehash 가 필요 하 다 는 것 을 알 게 되 었 습 니 다.그러면 B 는 오래된 table 에 대해 다시 rehash 를 진행 합 니 다.그리고 A 가 rehash 를 완성 한 다음 에 hashmap 에 대한 삽입 작업 을 계속 할 수 있 습 니 다.그러나 B 는 A 가 rehash 를 한 번 했 는 지 모 르 기 때문에 B 가 rehash 를 완성 한 후에 A 스 레 드 rehash 가 발생 하 는 새로운 table 을 직접 덮어 버 리 면 심각 한 데 이 터 를 잃 어 버 릴 수 있 습 니 다.
4.rehash 시 발생 하 는 순환
이런 상황 이 발생 할 확률 이 크 지 않 고 설명 하기 도 복잡 하 니 간단하게 말씀 드 리 겠 습 니 다.
먼저,이전 rehash 로 인 한 데이터 손실 에 대해 설명 하 였 습 니 다.한 노드 에 rehash 를 진행 할 때 현재 노드 e 와 e.next 를 저장 합 니 다.둘째,map 에 하나의 요 소 를 삽입 하면 우 리 는 링크 의 머리 에 삽입 되 는 것 을 알 고 있다.즉,원래 링크 의 요소 1->9 가 rehash 후에 도 같은 링크 에 있 으 면 선후 순서 가 뒤 바 뀌 어 9->1 이 된다.
똑 같이 두 개의 스 레 드 A,B 입 니 다.rehash 작업 도 마찬가지 입 니 다.

table
 ------ |  33  | 
 ------  ------ ------ |  1   |  ->|  9   |  
 ------ ------  ------ |      | 
 ------  ------ |      | 
 ------ 

그 위의 그림 중의 1,9 는 예 이다.1 을 가 져 오 면 e=1.next=e.next=9 A,B 스 레 드 는 노드 1 을 읽 고 next 9 를 저장 합 니 다.이때 B 라인 의 질서정연 한 CPU 스케줄 링 문제 가 한동안 끊 겼 고,이 기간 에 A 라인 은 1,9 rehash 의 과정 을 마 쳤 다.A 가 만 든 새 table 에 서 는 9->1 과 같은 링크 구조 가 형성 되 었 습 니 다.
이 때 B 가 다시 실 행 됩 니 다.1 과 next 노드 9 를 불 러 왔 기 때문에 위 에 제 시 된 rehash 의 소스 코드 를 관찰 하고 노드 1 을 lohead 나 hiHead 에 넣 은 후에 next 가 비어 있 는 지 판단 합 니 다(물론 이때 next 는 9 이 고 비어 있 지 않 습 니 다).동상 e=9;next = e.next = 1。 여기 서 주의해 야 할 것 은 A 스 레 드 가 결점 1 과 9 의 방향 을 바 꾸 었 기 때문에 B 스 레 드 는 9 의 next 를 가 져 올 때 얻 을 수 있 고 결점 1 이다.이 어 B 라인 도 9 를 loHead 나 hiHead 에 삽입 하고 1 을 다시 9 로 향한다.이로써 1->9 및 9->1 은 순환 조건 이 while(e=next)이기 때문에!=null); 사순환 이 생기다.
3.총화
1.HashMap 이 왜 스 레 드 가 안전 하지 않 은 지 알 고 있 습 니 다.2.소스 코드 측면 에서 rehash 의 부분 실현 을 이해 했다.
4.부록