Java lock-free 해시맵의 원리와 구현에 대한 자세한 설명

Java 멀티 스레드 환경에서 HashMap을 적용할 때 주로 다음과 같은 옵션이 있습니다. 대안으로 스레드로부터 안전한 java.util.Hashtable을 사용하여 기존 HashMap을 래핑합니다. 스레드로부터 안전한 개체입니다. 대안으로 java.util.concurrent.ConcurrentHashMap 클래스를 사용하면 성능이 매우 좋습니다.
위의 방법은 모두 구체적인 구현 세부 사항에서 뮤텍스 잠금을 어느 정도 사용합니다. 뮤텍스 잠금은 스레드 차단을 유발하고, 작업 효율성을 저하시키며, 교착 상태 및 우선순위 뒤집기와 같은 일련의 문제를 일으킬 수 있습니다.

CAS(Compare And Swap)는 기본 하드웨어에서 제공하는 기능으로, 값을 판단하고 변경하는 작업을 원자화할 수 있습니다.

Java의 원자 연산

java.util.concurrent.atomic 패키지에서 Java는 CAS 연산을 완전히 기반으로 하는 다양한 편리한 원자 유형을 제공합니다.

예를 들어 전역 공개 카운터를 구현하려는 경우 다음과 같이 할 수 있습니다.

privateAtomicInteger counter =newAtomicInteger(3); 

publicvoidaddCounter() { 

    for(;;) { 

        intoldValue = counter.get(); 

        intnewValue = oldValue +1; 

        if(counter.compareAndSet(oldValue, newValue)) 

            return; 

    } 

}

그 중 CompareAndSet 메소드는 counter의 기존 값이 oldValue인지 확인하고, 그렇다면 new로 설정합니다. 값이 newValue이면 작업이 성공하고 true가 반환됩니다. 그렇지 않으면 작업이 실패하고 false가 반환됩니다.

새 카운터 값을 계산할 때 다른 스레드가 카운터 값을 변경하면 CompareAndSwap이 실패합니다. 이 시점에서는 외부에 루프 레이어를 추가하고 이 프로세스를 계속 시도하면 결국 성공적으로 카운터 값이 1만큼 증가합니다. (사실 AtomicInteger는 일반적으로 사용되는 +1/-1 연산에 대해 incrementAndGet 및 decrementAndGet 메소드를 이미 정의했습니다. 앞으로는 간단히 호출하기만 하면 됩니다.)

AtomicInteger 외에도 java.util.concurrent .atomic 패키지는 또한 각각 원자 참조 및 원자 참조 배열(참조 배열)을 나타내는 AtomicReference 및 AtomicReferenceArray 유형을 제공합니다.

lock-free 연결 리스트 구현
lock-free HashMap을 구현하기 전에 먼저 비교적 간단한 lock-free 연결 리스트 구현 방법을 살펴보겠습니다.

삽입 연산을 예로 들어보겠습니다.

먼저 삽입할 위치 앞에 있는 노드 A와 그 뒤에 있는 노드 B를 찾아야 합니다.
그런 다음 새 노드 C를 만들고 다음 포인터가 노드 B를 가리키도록 만듭니다. (그림 1 참조)
마지막으로 노드 A의 다음 포인터가 노드 C를 가리키도록 만듭니다. (그림 2 참조)

그러나 작업 도중에 다른 스레드가 A와 B(D로 추정)에 일부 노드를 직접 삽입했을 가능성이 있습니다. 우리는 아무것도 판단하지 않습니다. 다른 스레드에 의해 삽입된 노드가 손실될 수 있습니다. (그림 3 참조) CAS 연산을 사용하여 값을 할당할 때 노드 A의 다음 포인터가 여전히 B를 가리키는지 여부를 확인할 수 있습니다. 만약 노드 A의 다음 포인터가 변경되면 전체 삽입 연산을 다시 시도합니다. 대략적인 코드는 다음과 같습니다.

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; 
    } 
}

(Node 클래스의 다음 필드는 Node 유형을 가리키는 원자 참조인 AtomicReference 유형입니다.)

검색 작업 잠금 없는 연결 목록은 일반 연결 목록과 다르지 않습니다. 삭제 연산은 삭제할 노드 앞의 노드 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，数组扩容时仅需将size加倍即可；定义count代表目前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)); 

 
}

其中getBucket即封装过的获取数组某下标内容的方法，setBucket同理。listInsert将从指定位置开始查找适合插入的位置插入给定的节点，若链表中已存在hash相同的节点则返回那个已存在的节点；否则返回新插入的节点。

插入操作

首先用HashMap的size对键的hashCode取模，得到应插入的数组下标。
然后判断该下标处是否为null，如果为null则初始化此下标。
构造一个新的节点，并插入到适当位置，注意节点中的hash值应为原hashCode经过位翻转并将最低位置1之后的值。
将节点个数计数器加1，若加1后节点过多，则仅需将size改为size*2，代表对数组扩容（ReHash）。

查找操作

找出待查找节点在数组中的下标。
判断该下标处是否为null，如果为null则返回查找失败。
从相应位置进入链表，顺次寻找，直至找出待查找节点或超出本组节点范围。

删除操作

找出应删除节点在数组中的下标。
判断该下标处是否为null，如果为null则初始化此下标。
找到待删除节点，并从链表中删除。（注意由于哨兵节点的存在，任何正常元素只被其唯一的前驱节点所引用，不存在被前驱节点与数组中指针同时引用的情况，从而不会出现需要同时修改多个指针的情况）
将节点个数计数器减1。

更多Java lock-free 해시맵의 원리와 구현에 대한 자세한 설명相关文章请关注PHP中文网！