Concurrent HashMap 의 sizeCtl 의미 교정
Concurrent HashMap 1.8
sizeCtl 정의 및 설명
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
private transient volatile int sizeCtl;
sizeCtl 은 Concurrent HashMap 에서 중요 한 변수 임 에 틀림없다. 각종 자료 에서 볼 수 있 는 기본 은
sizeCtl: 기본 값 은 0 입 니 다. table 의 초기 화 와 확장 작업 을 제어 하 는 데 사 용 됩 니 다. - 1 대표 table 이 초기 화 되 고 있 습 니 다. - N 은 N - 1 개의 스 레 드 가 확장 작업 을 하고 있 음 을 표시 합 니 다. 나머지 상황: 1. table 이 초기 화 되 지 않 으 면 table 이 초기 화 해 야 할 크기 를 표시 합 니 다.2. table 초기 화가 완료 되면 table 의 용량 을 표시 합 니 다. 기본 값 은 table 크기 의 0.75 배 입 니 다.
이 자료 들 은 사실 주석 에 따라 한 번 번역 한 것 이지 만, 사실 주석 은 잘못된 것 이다.N 은 N - 1 개의 스 레 드 가 확장 작업 을 하고 있다 는 것 을 나타 내 는데 이 말 은 잘못된 것 이다.
여기 서 - N 의 정 의 는 문제 가 있 습 니 다. - N 에 대응 하 는 바 이 너 리 의 낮은 16 비트 수 치 를 M 으로 해 야 합 니 다. 이때 M - 1 개의 스 레 드 가 확장 되 어야 합 니 다.(댓 글 창 친구 의 조언 에 감 사 드 립 니 다)
증명: sizeCtl 을 수정 할 수 있 는 방법 은 다섯 가지 가 있 습 니 다.
그 중에서 initTable 은 - 1 로 설정 하여 한 번 만 초기 화 할 수 있 도록 하고 초기 화 후 sizeCtl 을 길이 의 0.75 배로 설정 합 니 다. 이때 sizeCtl 은 플러스 입 니 다.
sizeCtrl 을 - N 으로 설정 할 수 있 는 방법 은 addCount 와 try Presize 방법 뿐 이 며, 두 가지 방법의 실현 논 리 는 매우 비슷 하 다. 여 기 는 try Presize 를 설명 으로 한다.
..
while ((sc = sizeCtl) >= 0) {
ConcurrentHashMap.Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
// ，
// initTable ， sc 0.75 ， ，
//
}
// ， ， ，
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
// while ， sc >=0， ， else
//
if (sc < 0) {
ConcurrentHashMap.Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// -N
// cas， cas -N
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
N 으로 설정 한 키 는 바로...
int rs = resizeStamp(n);
(rs << RESIZE_STAMP_SHIFT) + 2
：
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
private static int RESIZE_STAMP_BITS = 16;
//32-↑ ， 16
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
그 중의 Integer. numberOfLeadingZeros (n) 는 가장 높 은 1 의 왼쪽 0 의 수량 을 얻 는 역할 을 한다. n 은 int 유형 이기 때문에 여기 서 반환 값 은 [0, 32] 예 를 들 어 n = 16 - 0001 0000 = 24 이 고 왼쪽 의 0 의 수량 은 31 - 4 = 27 이다.
그리고 215, rs 를 얻 었 습 니 다.그래서 rs 의 수치 범 위 는 사실 [215, 215 + 32] 이다.
rs 부 호 를 왼쪽으로 16 자리 옮 깁 니 다. rs 의 215 자 리 는 반드시 1 이기 때문에 왼쪽으로 이동 한 후 231 자 리 는 반드시 1, 즉 rs 는 마이너스 입 니 다.
상기 rs 범위 에서 알 수 있 듯 이 왼쪽으로 이동 한 후 rs 는 매우 작다 (- N 은 매우 작다). 마지막 에 + 2 를 해도 양수 로 변 하지 않 는 다.이것 이 바로 sizeCtl 업데이트 후의 값 입 니 다.
테스트 코드: (n 은 배열 길이 이 고 모두 2 의 미터 입 니 다)
static final int resizeStamp(int n) {
int zeroCount = Integer.numberOfLeadingZeros(n);
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
private static int RESIZE_STAMP_BITS = 16;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
public static void main(String[] args) {
// <0 ，
for(int n=1;n>0;n*=2){
int rs = resizeStamp(n);
int ans = (rs << RESIZE_STAMP_SHIFT) + 2;
System.out.println("n:"+n+" rs:"+rs+" ans:"+ans);
}
}
결과:
n:1 rs:32799 ans:-2145452030
n:2 rs:32798 ans:-2145517566
n:4 rs:32797 ans:-2145583102
n:8 rs:32796 ans:-2145648638
n:16 rs:32795 ans:-2145714174
n:32 rs:32794 ans:-2145779710
n:64 rs:32793 ans:-2145845246
n:128 rs:32792 ans:-2145910782
n:256 rs:32791 ans:-2145976318
n:512 rs:32790 ans:-2146041854
n:1024 rs:32789 ans:-2146107390
n:2048 rs:32788 ans:-2146172926
n:4096 rs:32787 ans:-2146238462
n:8192 rs:32786 ans:-2146303998
n:16384 rs:32785 ans:-2146369534
n:32768 rs:32784 ans:-2146435070
n:65536 rs:32783 ans:-2146500606
n:131072 rs:32782 ans:-2146566142
n:262144 rs:32781 ans:-2146631678
n:524288 rs:32780 ans:-2146697214
n:1048576 rs:32779 ans:-2146762750
n:2097152 rs:32778 ans:-2146828286
n:4194304 rs:32777 ans:-2146893822
n:8388608 rs:32776 ans:-2146959358
n:16777216 rs:32775 ans:-2147024894
n:33554432 rs:32774 ans:-2147090430
n:67108864 rs:32773 ans:-2147155966
n:134217728 rs:32772 ans:-2147221502
n:268435456 rs:32771 ans:-2147287038
n:536870912 rs:32770 ans:-2147352574
n:1073741824 rs:32769 ans:-2147418110
이 를 통 해 알 수 있 듯 이 어느 길이 든 지 얻 은 sizeCtl 의 새 값 은 매우 작다.분명히 주석 에 따라 이해 하면 N - 1 개의 스 레 드 가 있 고 N 이 이렇게 크 며 이렇게 많은 스 레 드 는 불가능 합 니 다.
포 인 트 는 rs 가 왼쪽 에서 16 위 를 옮 긴 후에 16 위 가 낮 으 면 모두 0 이다.16 자리 만 낮 추 면 수치 가 M 이 고 초기 에는 0 입 니 다.(사실 바 이 너 리 로 봐 도 된다. 215 이렇게 많은 스 레 드 가 확장 되 는 것 은 불가능 하지만 엄밀 한 표현 을 위해 수치 만 본다) + 2 후 M = 2. 이때 확장 스 레 드 는 M - 1 = 1 이다. 그러면 주석 정의 에 대응 할 수 있다.
물론 높 은 16 비트 에 의 미 를 찾 으 려 면 현재 용량 n 을 대표 하 는 것 이지 만 수치 가 용량 크기 와 같다 고 말 하 는 것 은 아니다. 높 은 16 비트 는 n 에 대한 계산 이기 때문이다.
반증
사실 위의 증명 은 이미 충분 하지만, 우 리 는 다음 과 같은 몇 가지 측면 에서 잘못 을 설명 할 수 있다. (과학 은 엄밀 하 다!!)
helpTransfer
putVal 시 현재 노드 hash 값 이 - 1 인 것 을 감지 하면 현재 확장 상태 에 있 음 을 설명 하고 현재 put 스 레 드 를 확장 에 추가 합 니 다.
if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
helpTransfer 방법 에서 스 레 드 수 를 늘 리 는 코드 는:
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
while 조건 을 만족 시 키 고 현재 sizeCtl < 0 을 증명 합 니 다. 확장 스 레 드 수량 을 증가 하 는 작업 은 sc + 1 입 니 다. sc - 1 - N + 1 이 아니 라 N 값 이 작 아 지고 N - 1 스 레 드 의 표현 에 만족 하지 않 습 니 다. 그러나 16 비트 의 수치 M 만 낮 으 면 대응 하 는 수치 + 1, 즉 확장 스 레 드 + 1 입 니 다.
이 방법 을 제외 하고 try Presize, addCount 에 도 유사 한 코드 가 있 습 니 다. 여 기 는 try Presize 를 예 로 들 수 있 습 니 다.
//
if (sc < 0) {
ConcurrentHashMap.Node<K, V>[] nt;
//
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// ， ，
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
보 실 수 있 습 니 다. 똑 같이 sc + 1 입 니 다.
transfer()
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//
if (finishing) {
// ，
nextTable = null;
table = nextTab;
// sizeCtl 1.5 n（ ）， 0.75
// sizeCtl
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// ， ，
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// -N
// sc ，
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; //
}
}
그 중에서 스 레 드 수량 을 줄 이 는 코드 는 sc - 1 이 고 주석 이 맞지 않 는 다 는 표현 입 니 다.
총결산
이에 따라 결론 을 내 렸 다. - N 은 대응 하 는 바 이 너 리 의 낮은 16 비트 수 치 를 M 으로 해 야 한다. 이때 M - 1 개의 확장 스 레 드 가 있다 는 것 을 의미한다. N - 1 개의 스 레 드 가 있다 는 것 은 아니다.
본 고 는 유사 한 관점 을 발견 하지 못 했 고 관련 자 료 를 참고 하지 못 했 기 때문에 잘못 되면 지적 해 주 십시오.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JAVA- 소스 코드 분할(Package 사용)▪️test45.java 소스 코드 ▪️test47.java 소스 코드 ▪️실행 결과 더하면 12, 당기면 8 ▪️예① 클래스 이름에 대한 완전한 입력 생략 import 문 사용 ▪️예① test45.java 소스 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
