자바 무 잠 금 hashmap 원리 및 구현 상세 설명
7440 단어 hashmap 원리
CAS(Compare And Swap)는 바 텀 하드웨어 가 제공 하 는 기능 으로 값 을 판단 하고 변경 하 는 조작 을 원자 화 할 수 있다.
자바 의 원자 조작
자바.util.concurrent.atomic 패키지 에서 자바 는 우리 에 게 많은 편리 한 원자 유형 을 제공 합 니 다.그들의 바 텀 은 CAS 를 기반 으로 합 니 다.
예 를 들 어 우 리 는 전역 공용 계산 기 를 실현 하 기 를 원한 다 면 다음 과 같이 할 수 있다.
privateAtomicInteger counter =newAtomicInteger(3);
publicvoidaddCounter() {
for(;;) {
intoldValue = counter.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
return;
}
}
counter 의 새 값 을 계산 할 때 다른 스 레 드 가 counter 의 값 을 바 꾸 면 compare AndSwap 이 실패 합 니 다.이때 우 리 는 밖에서 순환 만 하고 이 과정 을 계속 시도 하면 결국 conter 값 을+1 하 는 데 성공 할 것 이다.(사실 AtomicInteger 는 자주 사용 하 는+1/-1 작업 에 increment AndGet 과 decrement AndGet 방법 을 정 의 했 습 니 다.이후 에 우 리 는 그것 을 간단하게 호출 하면 됩 니 다)
AtomicInteger 외 에 java.util.concurrent.atomic 패 키 지 는 AtomicReference 와 AtomicReference Array 형식 을 제공 합 니 다.각각 원자 적 인용 과 원자 적 인용 배열(인용 배열)을 대표 합 니 다.
잠 금 없 는 링크 의 실현 은 잠 금 없 는 HashMap 을 실현 하기 전에 비교적 간단 한 잠 금 없 는 링크 의 실현 방법 을 살 펴 보 자.
삽입 동작 을 예 로 들 면:
우선 우 리 는 삽입 할 위치 앞의 노드 A 와 뒤의 노드 B 를 찾 아야 한다.그리고 노드 C 를 새로 만 들 고 next 포인터 가 노드 B 를 가리 키 도록 합 니 다.(그림 1 참조)마지막 으로 노드 A 의 next 포인터 가 노드 C 를 가리 키 도록 합 니 다.(그림 2 참조)
그러나 작업 도중에 다른 스 레 드 가 A 와 B 에 일부 노드(D 로 가정)를 직접 삽입 할 수 있 습 니 다.만약 에 우리 가 어떠한 판단 도 하지 않 으 면 다른 스 레 드 가 노드 를 삽입 하 는 손실 을 초래 할 수 있 습 니 다.(그림 3)우 리 는 CAS 작업 을 이용 하여 노드 A 의 next 포인터 에 값 을 부여 할 때 B 를 가리 키 는 지 여 부 를 판단 할 수 있다.만약 에 노드 A 의 next 포인터 가 변화 하면 전체 삽입 작업 을 다시 시도 할 수 있다.대략적인 코드 는 다음 과 같다.
privatevoidlistInsert(Node head, Node c) {
for(;;) {
Node a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
return;
}
}
자물쇠 없 는 링크 찾기 동작 은 일반 링크 와 다 르 지 않 습 니 다.그 삭제 작업 은 삭 제 될 노드 앞 에 있 는 노드 A 와 뒤의 노드 B 를 찾 아 CAS 작업 검증 을 이용 하여 노드 A 의 next 지침 을 업데이트 하여 노드 B 를 가리 키 도록 해 야 한다.
자물쇠 없 는 HashMap 의 난점 과 돌파 HashMap 은 주로 삽입,삭제,찾기,ReHash 네 가지 기본 동작 이 있 습 니 다.전형 적 인 HashMap 실현 은 하나의 배열 을 사용 하고 배열 의 모든 요 소 는 하나의 노드 의 링크 입 니 다.이 링크 에 대해 우 리 는 앞에서 언급 한 조작 방법 을 이용 하여 삽입,삭제,찾기 작업 을 수행 할 수 있 으 나 ReHash 작업 에 있어 서 는 비교적 어렵다.
그림 4 에서 ReHash 과정 에서 전형 적 인 조작 은 오래된 표 의 모든 노드 를 옮 겨 다 니 며 새 표 에 있 는 위 치 를 계산 한 다음 에 새 표 로 이동 하 는 것 이다.그 동안 우 리 는 세 번 의 지침 을 조종 해 야 한다.
A 의 next 포인 터 를 D 로 가리 키 고 B 의 next 포인 터 를 C 로 가리 키 며 C 의 next 포인 터 를 E 로 가리 키 는데 이 세 번 의 포인 터 는 동시에 완성 해 야 이동 작업 의 원자 성 을 확보 할 수 있다.그러나 CAS 작업 은 매번 한 변수의 값 만 원자 적 으로 검증 되 고 업 데 이 트 될 수 있 을 뿐 세 개의 지침 을 동시에 검증 하고 업데이트 하 는 수 요 를 만족 시 킬 수 없다 는 것 을 알 수 있다.
따라서 우 리 는 방향 을 바 꾸 어도 무방 하 다.이동 노드 의 조작 이 이렇게 어 려 운 이상 우 리 는 모든 노드 를 시종일관 질서 있 는 상 태 를 유지 하여 이동 조작 을 피 할 수 있다.전형 적 인 HashMap 실현 에서 배열 의 길 이 는 항상 2i 로 유지 되 고 Hash 값 에서 배열 아래 표 시 된 과정 은 배열 의 길이 에 대해 모델 링 연산 을 간단하게 수행 할 뿐이다(즉,Hash 2 진법 의 후 i 비트 만 유지 하 는 것).ReHash 일 때 배열 의 길 이 는 배가 되 어 2i+1 로 바 뀌 었 다.낡은 배열 의 j 항 링크 의 모든 노드 는 새로운 배열 의 j 항 으로 이동 하거나 새로운 배열 의 j+2i 항 으로 이동 했다.그들의 유일한 차이 점 은 Hash 값 i+1 위의 차이 점(i+1 위 는 0 이면 j 항 이 고 그렇지 않 으 면 j+2i 항)이다.
그림 5 와 같이 우 리 는 모든 노드 를 Hash 값 의 뒤 집기 순서(예 를 들 어 1101->1011)에 따라 작은 것 에서 큰 것 으로 배열 합 니 다.배열 의 크기 가 8 일 때 2,18 은 한 그룹 안에 있 습 니 다.3,11,27 은 다른 조 안에 있다.각 조 의 시작 에 보초병 노드 를 삽입 하여 후속 작업 을 편리 하 게 한다.보초병 노드 를 조 의 최 전방 에 정확하게 배치 하기 위해 우 리 는 정상 노드 인 Hash 의 최고 위치(뒤 집 힌 후 최저 위치 로)를 1 로 설정 하고 보초병 노드 는 이 분 을 설정 하지 않 습 니 다.
배열 이 16 으로 확대 되 었 을 때(그림 6 참조)두 번 째 조 는 3 만 포함 하 는 그룹 과 11,27 을 포함 하 는 그룹 으로 나 뉘 었 으 나 노드 간 의 상대 적 인 순 서 는 변 하지 않 았 다.이렇게 ReHash 에 있 을 때 우 리 는 노드 를 이동 할 필요 가 없다
디 테 일 구현
확장 시 배열 의 복 제 는 많은 시간 을 차지 하기 때문에 우 리 는 전체 배열 을 블록 으로 나 누 어 게 으 르 게 만 드 는 방법 을 채택 했다.이렇게 하면 아래 표 시 를 방문 할 때 이 아래 표 시 된 블록 이 이미 만 들 어 졌 는 지 판단 해 야 합 니 다(없 으 면 만 듭 니 다).
또한 size 를 현재 사용 하고 있 는 아래 표 시 된 범위 로 정의 합 니 다.초기 값 은 2 이 며,배열 확장 시 size 를 배로 늘 리 면 됩 니 다.현재 HashMap 에 포 함 된 총 노드 개 수 를 정의 합 니 다(보초병 노드 는 아 닙 니 다).
초기 에는 배열 에서 0 항 을 제외 한 모든 항목 이 null 이 었 습 니 다.0 항 은 보초병 노드 만 있 는 체인 시 계 를 가리 키 며 전체 체인 의 출발점 을 대표 한다.처음에 전 모 는 그림 7 을 보 았 는데 그 중에서 옅 은 녹색 은 현재 사용 되 지 않 은 아래 표 시 된 범 위 를 나타 내 고 점선 화살 표 는 논리 적 으로 존재 하지만 실제 적 으로 구축 되 지 않 은 블록 을 나타 낸다.
다음 작업 초기 화
배열 에서 null 인 항목 은 모두 초기 화 되 지 않 은 상태 라 고 생각 합 니 다.아래 표 시 를 초기 화 하 는 것 은 해당 하 는 보초병 노드 를 만 드 는 것 을 의미 합 니 다.초기 화 는 재 귀적 으로 진 행 됩 니 다.즉,아버지 가 표 시 를 초기 화하 지 않 으 면 아버지 가 표 시 를 초기 화 합 니 다.(아래 표 시 된 부모 아래 표 시 는 최고 바 이 너 리 를 제거 한 후 얻 은 아래 표 시 됩 니 다)크게 코드 는 다음 과 같 습 니 다.
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==null)
initializeBucket(parentIdx);
Node dummy =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
삽입 조작
먼저 HashMap 의 size 키 에 대한 hashCode 로 모드 를 추출 하여 삽입 할 배열 아래 표 시 를 받 습 니 다.그리고 이 아래 표 시 된 곳 이 null 인지 여 부 를 판단 합 니 다.null 이면 이 아래 표 시 를 초기 화 합 니 다.새로운 노드 를 만 들 고 적당 한 위치 에 삽입 합 니 다.노드 의 hash 값 은 원래 hash Code 가 위 치 를 뒤 집 고 최저 위 치 를 1 후의 값 으로 해 야 합 니 다.노드 개수 계수 기 를 1 로 추가 하고 1 을 추가 한 후 노드 가 너무 많 으 면 size*2 로 바 꾸 면 배열 확장(ReHash)을 대표 합 니 다.
찾기 동작
찾 아야 할 노드 가 배열 에 있 는 아래 표 시 를 찾 아 라.이 아래 표 시 된 곳 이 null 인지 여 부 를 판단 하고 null 이면 찾기 에 실 패 했 습 니 다.해당 위치 에서 링크 에 들 어가 서 찾 아야 할 노드 를 찾 거나 본 그룹의 노드 범 위 를 초과 할 때 까지 순서대로 찾 습 니 다.
삭제 작업
삭제 해 야 할 노드 가 배열 에 있 는 아래 표 시 를 찾 아 라.이 아래 표 시 된 곳 이 null 인지 여 부 를 판단 하고 null 이면 이 아래 표 시 를 초기 화 합 니 다.삭제 할 노드 를 찾 아 링크 에서 삭제 합 니 다.(보초병 노드 의 존재 로 인해 모든 정상 적 인 요 소 는 유일한 전구 노드 에 의 해 인용 되 고 전구 노드 와 배열 의 지침 에 의 해 동시에 인용 되 는 상황 이 존재 하지 않 으 며 여러 개의 지침 을 동시에 수정 해 야 하 는 상황 이 발생 하지 않 습 니 다)노드 의 개수 계산 기 를 1 로 줄 입 니 다.
좋은 웹페이지 즐겨찾기
