Java 다중 스레드 환경에서 HashMap을 적용할 때 주로 다음과 같은 옵션이 있습니다. 스레드로부터 안전한 java.util.Hashtable을 대안으로 사용합니다. 기존 HashMap 객체를 스레드로 래핑하려면 java.util.Collections.synchronizedMap 메서드를 사용합니다. -안전한. 성능이 매우 좋은 java.util.concurrent.ConcurrentHashMap 클래스를 대안으로 사용하십시오.
위의 방법은 모두 구현의 특정 세부 사항에서 어느 정도 뮤텍스 잠금을 사용합니다. 뮤텍스 잠금은 스레드 차단을 유발하고, 운영 효율성을 저하시키며, 교착 상태 및 우선순위 뒤집기와 같은 일련의 문제를 일으킬 수 있습니다.
CAS(Compare And Swap)는 기본 하드웨어에서 제공하는 기능으로, 값 판단 및 변경 작업을 원자화할 수 있습니다.
Java의 원자적 연산
java.util.concurrent.atomic 패키지에서 Java는 전적으로 CAS 작업을 기반으로 하는 다양한 편리한 원자 유형을 제공합니다.
예를 들어 전역 공개 카운터를 구현하려는 경우 다음을 수행할 수 있습니다.
다음과 같이 코드 코드를 복사합니다.
privateAtomicInteger 카운터 =newAtomicInteger(3);
publicvoidaddCounter() {
을 위한(;;) {
intoldValue = counter.get();
intnewValue = oldValue +1;
if(counter.compareAndSet(oldValue, newValue))
반품;
}
}
그 중 CompareAndSet 메소드는 counter의 기존 값이 oldValue인지 확인하고, 그렇다면 새로운 값 newValue로 설정되며, 그렇지 않으면 작업이 실패하고 false가 반환됩니다.
counter의 새 값을 계산할 때 다른 스레드가 counter의 값을 변경하면 CompareAndSwap이 실패합니다. 이 시점에서는 외부에 루프 레이어를 추가하고 이 프로세스를 계속 시도하면 결국 성공적으로 카운터 값이 1만큼 증가합니다. (사실 AtomicInteger는 일반적으로 사용되는 +1/-1 연산에 대해 incrementAndGet 및 decrementAndGet 메서드를 이미 정의했습니다. 앞으로는 간단히 호출하기만 하면 됩니다.)
AtomicInteger 외에도 java.util.concurrent.atomic 패키지는 각각 원자 참조 및 원자 참조 배열(참조 배열)을 나타내는 AtomicReference 및 AtomicReferenceArray 유형도 제공합니다.
Lock-Free 연결리스트 구현
잠금 없는 HashMap을 구현하기 전에 먼저 비교적 간단한 잠금 없는 연결 목록 구현 방법을 살펴보겠습니다.
삽입 작업을 예로 들어 보겠습니다.
먼저 삽입할 위치 앞에 있는 노드 A와 그 뒤에 있는 노드 B를 찾아야 합니다.
그런 다음 새 노드 C를 만들고 다음 포인터가 노드 B를 가리키도록 만듭니다. (그림 1 참조)
마지막으로 노드 A의 다음 포인터가 노드 C를 가리키도록 만듭니다. (그림 2 참조)
그러나 작업 도중 다른 스레드가 A와 B(D로 추정)의 일부 노드를 직접 삽입했을 가능성이 있습니다. 우리가 아무런 판단을 하지 않으면 다른 스레드가 삽입한 노드가 손실될 수 있습니다. (그림 3 참조) CAS 연산을 사용하여 값을 할당할 때 노드 A의 다음 포인터가 여전히 B를 가리키는지 여부를 확인할 수 있습니다. 만약 노드 A의 다음 포인터가 변경되면 전체 삽입 연산을 다시 시도합니다. 대략적인 코드는 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다.
privatevoidlistInsert(노드 헤드, 노드 c) {
을 위한(;;) {
노드 a = findInsertionPlace(head), b = a.next.get();
c.next.set(b);
if(a.next.compareAndSwap(b,c))
반품;
}
}
(Node 클래스의 다음 필드는 Node 유형을 가리키는 원자 참조인 AtomicReference<Node> 유형입니다.)
잠금 없는 연결 목록의 검색 작업은 일반 연결 목록의 검색 작업과 다르지 않습니다. 삭제 연산은 삭제할 노드 앞의 노드 A와 그 뒤에 있는 노드 B를 찾고, CAS 연산을 통해 노드 A의 다음 포인터가 노드 B를 가리키도록 검증하고 업데이트해야 합니다.
잠금 없는 HashMap의 어려움과 혁신
HashMap에는 주로 삽입, 삭제, 검색 및 ReHash의 네 가지 기본 작업이 있습니다. 일반적인 HashMap 구현은 배열을 사용하며 배열의 각 요소는 노드의 연결된 목록입니다. 이 연결 리스트의 경우 위에서 언급한 작업 방법을 사용하여 삽입, 삭제 및 검색 작업을 수행할 수 있지만 ReHash 작업이 더 어렵습니다.
그림 4에서 볼 수 있듯이 ReHash 프로세스 중 일반적인 작업은 이전 테이블의 각 노드를 순회하고 새 테이블에서 위치를 계산한 다음 새 테이블로 이동하는 것입니다. 이 기간 동안 포인터를 세 번 조작해야 합니다.
D를 향한 A의 다음 포인터
C를 향한 B점의 다음 포인터
E를 향한 C점의 다음 포인터
이동 작업의 원자성을 보장하려면 이러한 세 가지 포인터 작업을 동시에 완료해야 합니다. 그러나 CAS 연산은 한 변수의 값이 한 번에 원자적으로 검증되고 업데이트되도록 보장할 수 있을 뿐이며 동시에 세 개의 포인터를 검증하고 업데이트해야 하는 필요성을 충족할 수 없다는 것을 아는 것은 어렵지 않습니다.
그러면 생각을 바꿔서 노드를 이동하는 작업이 너무 어렵기 때문에 모든 노드를 항상 정렬된 상태로 유지하여 이동 작업을 피할 수 있습니다. 일반적인 HashMap 구현에서 배열의 길이는 항상 2i로 유지되며 해시 값을 배열 첨자로 매핑하는 프로세스는 단순히 배열 길이에 대해 모듈로 연산을 수행합니다(즉, 해시 바이너리의 마지막 i 비트만 유지됨). ReHash를 수행하면 배열 길이가 2i+1로 두 배가 되고 이전 배열의 j번째 목걸이 목록에 있는 각 노드는 새 배열의 j번째 항목으로 이동되거나 j+2i번째 항목으로 이동됩니다. 유일한 차이점은 해시 값의 i+1번째 비트에 있습니다(i+1번째 비트가 0이면 여전히 j번째 항목이고, 그렇지 않으면 j+2번째 항목입니다).
그림 5와 같이 Hash 값의 역순(예: 1101->1011)에 따라 모든 노드를 오름차순으로 정렬합니다. 배열 크기가 8이면 2와 18이 한 그룹에 있고, 3, 11과 27이 다른 그룹에 있습니다. 각 그룹의 시작 부분에는 후속 작업을 용이하게 하기 위해 감시 노드가 삽입됩니다. 그룹 앞부분에 센티넬 노드를 올바르게 배치하기 위해 일반 노드 Hash(플리핑 후 가장 낮은 비트가 됨)의 가장 높은 비트를 1로 설정하고, 센티넬 노드는 이 비트를 설정하지 않습니다.
배열을 16개로 확장하면(그림 6 참조), 두 번째 그룹은 3개만 포함하는 그룹과 11개와 27개를 포함하는 그룹으로 분할되지만 노드 간의 상대적 순서는 변경되지 않습니다. 이런 방식으로 ReHash 중에 노드를 이동할 필요가 없습니다.
구현 세부정보
배열 복사는 확장시 시간이 많이 걸리기 때문에 여기서는 전체 배열을 블록으로 나누어 천천히 생성하는 방법을 채택합니다. 이렇게 특정 첨자가 접근되면 해당 첨자가 위치한 블록이 성립되었는지(그렇지 않다면 생성) 여부만을 판단하면 된다.
또한 size는 현재 사용되는 첨자 범위로 정의되며, 초기값은 2이다. 배열을 확장할 때 크기를 두 배로 늘리기만 하면 현재 HashMap에 포함된 전체 노드 수를 나타내도록 정의된다( 센티넬 노드는 계산하지 않음).
처음에는 0번째 항목을 제외한 배열의 모든 항목이 null입니다. 항목 0은 전체 체인의 시작점을 나타내는 하나의 감시 노드만 있는 연결 목록을 가리킵니다. 초기 전체 그림은 그림 7에 표시되어 있으며 연한 녹색은 현재 사용되지 않는 아래 첨자 범위를 나타내고 점선 화살표는 논리적으로 존재하지만 실제로 설정되지 않은 블록을 나타냅니다.
첨자 작업 초기화
배열의 Null 항목은 초기화되지 않은 상태로 간주됩니다. 특정 첨자를 초기화하는 것은 해당 Sentinel 노드를 설정하는 것을 의미합니다. 초기화는 재귀적으로 수행됩니다. 즉, 부모 첨자가 초기화되지 않은 경우 부모 첨자가 먼저 초기화됩니다. (첨자의 상위 첨자는 최상위 이진 비트를 제거하여 얻은 첨자입니다.) 대략적인 코드는 다음과 같습니다.
다음과 같이 코드 코드를 복사합니다.
privatevoidinitializeBucket(intbucketIdx) {
intparentIdx = bucketIdx ^ Integer.highestOneBit(bucketIdx);
if(getBucket(parentIdx) ==null)
초기화버킷(parentIdx);
노드 더미 =newNode();
dummy.hash = Integer.reverse(bucketIdx);
dummy.next =newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), dummy));
}
그 중 getBucket은 배열의 특정 첨자의 내용을 가져오기 위한 캡슐화된 메소드이며, setBucket도 동일합니다. listInsert는 지정된 위치에서 시작하여 적절한 위치에 지정된 노드를 삽입합니다. 동일한 해시를 가진 노드가 연결된 목록에 이미 있으면 기존 노드를 반환하고, 그렇지 않으면 새로 삽입된 노드를 반환합니다.
삽입 작업
먼저 HashMap의 크기를 사용하여 키의 hashCode를 모듈로화하여 삽입해야 하는 배열 첨자를 얻습니다.
그런 다음 첨자가 null인지 확인하고, null이면 첨자를 초기화합니다.
새 노드를 구성하고 이를 적절한 위치에 삽입합니다. 노드의 해시 값은 비트 반전 후 가장 낮은 위치를 1로 설정한 후의 원래 hashCode 값이어야 합니다.
노드 수 카운터에 1을 추가합니다. 1을 추가한 후 노드가 너무 많으면 크기를 size*2로 변경하기만 하면 됩니다. 이는 배열 확장(ReHash)을 의미합니다.
찾기 작업
배열에서 찾을 노드의 인덱스를 찾습니다.
아래 첨자가 null인지 확인합니다. null인 경우 검색 실패가 반환됩니다.
해당 위치부터 연결리스트를 입력하여 찾고자 하는 노드가 발견되거나 이 노드 그룹의 범위를 초과할 때까지 순차적으로 검색합니다.
삭제 작업
삭제해야 하는 배열의 노드 인덱스를 찾습니다.
첨자가 null인지 확인하고, null이면 첨자를 초기화합니다.
삭제할 노드를 찾아 연결리스트에서 삭제합니다. (센티넬 노드의 존재로 인해 모든 일반 요소는 이전 노드에서만 참조됩니다. 이전 노드와 배열의 포인터에서 동시에 참조되는 상황은 없습니다. 동시에 여러 포인터를 수정할 필요가 없습니다.)
노드 번호 카운터를 1씩 감소시킵니다.