해시 테이블은 매우 효율적인 데이터 구조이며, 해시 기능의 탁월한 설계는 O (1) 레벨에 도달하는 추가, 삭제, 수정 및 검색 작업을 수행 할 수 있습니다. Java는 기성품 해시 구조, 즉 Hashmap 클래스를 제공합니다. 이전 기사에서 나는 HashMap 클래스를 소개했고 모든 방법이 동기화되지 않았다는 것을 알았으므로 다중 스레드 환경에서 안전하지 않습니다. 이를 위해 Java는 다른 해시 테이블 클래스를 제공합니다. 다른 해시 가능 클래스는 다중 스레드 동기화를 처리하는 데 매우 간단하고 조잡합니다. 이 방법은 간단하지만 문제가 발생합니다. 즉, 하나의 스레드 만 해시 테이블을 동시에 작동시킬 수 있습니다. 이러한 스레드가 읽기 작업 만 있더라도 경쟁이 치열한 다중 스레드 환경의 성능에 큰 영향을 미칩니다. 이 기사에서 소개 된 동의어는이 문제를 해결하는 것입니다. 세그먼트로 된 잠금 장치를 사용하여 잠금 장치를 미세 입자하여 여러 스레드가 해시 테이블을 동시에 작동시켜 성능을 크게 향상시킬 수 있습니다. 다음 그림은 내부 구조의 개략도입니다.
1. ConsurenThashmap은 어떤 멤버 변수입니까?
// 기본 초기화 용량 정적 최종 최종 int default_initial_capacity = 16; // 기본 부하 계수 정적 최종 플로트 DEFAULT_LOAD_FACTOR = 0.75F; // 기본 동시성 레벨 정적 최종 int default_concurrency_level = 16; // 최대 용량 정적 최종 int 최대_capacity = 1 << 30; // 최소 세그먼트 잠금 세그먼트 잠금 min_segment_table_capacity = 2; // 세그먼트 잠금의 최대 숫자 정적 최종 최종 int max_segments = 1 << 16; // 정적 최종 int retries_before_lock = 2; 마스크 값 최종 int 세그먼트 마스크; // 세그먼트 잠금 배열 최종 세그먼트 <k, v> [] 세그먼트;
이 기사를 읽기 전에 독자는 이러한 회원 변수의 구체적인 의미와 기능을 이해할 수 없지만 독자는 참을성있게 읽는 것이 좋습니다. 이 멤버 변수의 역할은 나중에 특정 시나리오에서 하나씩 소개됩니다. 여기서 독자는 이러한 멤버 변수를 익숙하게 살펴볼 필요가 있습니다. 그러나 여전히 우리가 알아야 할 변수가 여전히 있습니다. 예를 들어, 세그먼트 배열은 세그먼트 잠금 세트를 나타내고, 동시성 레벨은 세그먼트 잠금의 수를 나타냅니다 (또한 동시에 작동 할 수있는 스레드 수를 의미합니다), 초기화 용량은 전체 컨테이너의 용량을 나타내며로드 계수는 컨테이너 요소가 가득 찬 수준을 나타냅니다.
2. 세그먼트 잠금의 내부 구조는 무엇입니까?
// 세그먼트 잠금 정적 최종 클래스 세그먼트 <k, v> 확장 재 렌트 링크 핑크 시리얼이즈 가능 {// 최대 스핀 번호 정적 최종 최종 int max_scan_retries = runtime.getRuntime (). avideprocessors ()> 1? 64 : 1; // HAST 테이블 과도 휘발성 해시 트리 <k, v> [] 테이블; // 총 요소 수 과도 int 수; // 수정 수 과도 int modcount; // 요소 임계 값 과도 int 임계 값; // 하중 계수 최종 플로트로드 변수; // 다음 내용을 생략 ...}세그먼트는 정적 내부 클래스의 ConcurrEthashMap이므로 ReintrantLock에서 상속되는 것을 알 수 있으므로 본질적으로 잠금입니다. 내부적으로 Hashentry 배열 (해시 테이블)을 보유하고 있으며 배열을 추가, 삭제, 수정 및 검색하는 모든 방법이 스레드 안전임을 보장합니다. 특정 구현은 나중에 논의 될 것입니다. ConshErthAshMap의 추가, 삭제, 수정 및 점검에 대한 모든 작업은 세그먼트에 위탁 될 수 있으므로 ConsperHessHashMap은 다중 스레드 환경에서 안전을 확인할 수 있습니다. 또한, 다른 세그먼트가 다른 잠금 장치이기 때문에, 멀티 스레드는 동시에 다른 세그먼트를 작동 할 수 있으므로, 멀티 스레드는 동시에 동시에 동시에 작동 할 수 있으며, 이는 해시 가능의 결함을 피하고 성능을 크게 향상시킬 수 있음을 의미합니다.
3. ConsurenTashMap은 무엇을 초기화 했습니까?
// 코어 생성자 @SuppressWarnings ( "확인되지 않은") public conspressashmap (int initialcapacity, float loadfactor, int concurrencylevel) {if (! (loadfactor> 0) || 초기 커피 <0 || conkurrencyLevel <= 0) {Throw New ImergalArgumentection (); } // 동시성 레벨이 한계보다 크지 않도록하십시오. } int sshift = 0; int ssize = 1; // ssize가 2의 동력인지 확인하고 동시성 레벨보다 가장 큰 숫자인지 (ssize <concurrencylevel) {++ sshift; ssize << = 1; } // 세그먼트 잠금의 시프트 값을 계산하십시오. // 세그먼트 잠금의 마스크 값을 계산하십시오. // 총 최초 용량은 (초기 Capacity> maximum_capacity) 인 경우 한계 값보다 클 수 없습니다. } // 각 세그먼트의 초기 용량을 가져옵니다. int c = 초기 커피 /ssize; // 세그먼트 잠금 용량의 합은 초기 총 용량보다 작습니다. } int cap = min_segment_table_capacity; // CAP가 2의 전력인지 확인하고 C보다 가장 큰 숫자 또는 동일합니다. } // 새 세그먼트 개체 템플릿 세그먼트 생성 <k, v> s0 = 새 세그먼트 <k, v> (loadfactor, (int) (cap * loadfactor), (hashentry <k, v> []) 새 해시트 [CAP]); // 지정된 크기 세그먼트의 새 세그먼트 잠금 배열 생성 <k, v> [] ss = (세그먼트 <k, v> []) 새 세그먼트 [ssize]; // 안전하지 않은 사용하여 배열의 0 번째 요소를 안전하지 않게 할당합니다. this.segments = ss;}ConsurenThashMap에는 여러 생성자가 있지만 위에 게시 된 것은 핵심 생성자이며 다른 생성자는 호출하여 초기화를 완료합니다. 코어 생성자는 3 가지 매개 변수, 즉 초기 용량, 로딩 계수 및 동시성 레벨로 전달해야합니다. 멤버 변수를 일찍 도입 할 때 기본 초기 용량은 16이고 로딩 계수는 0.75F이고 동시성 레벨은 16이라는 것을 알 수 있습니다. 이제 코어 생성자의 코드가 표시됩니다. 먼저, 들어오는 동시성 레벨을 통해 ssize를 계산합니다. ssize는 세그먼트 배열의 길이입니다. 이런 방식으로 배열에 고정 된 세그먼트의 첨자는 HASH & SSIZE-1에 의해 계산 될 수 있습니다. 들어오는 동시성 속도는 2의 전력으로 보장 될 수 없으므로 세그먼트 배열의 길이로 직접 사용할 수 없습니다. 따라서 동시 레벨에 가장 가까운 2의 전력을 찾아 배열의 길이로 사용해야합니다. 동시 레벨 = 15가 지금 전달되면 위의 코드는 ssize = 16 및 sshift = 4를 계산할 수 있습니다. 다음으로 SegmentShift = 16 및 SegmentMask = 15를 즉시 계산할 수 있습니다. 세그먼트 시프트는 여기서 세그먼트 잠금의 시프트 값이며 세그먼트 마스크는 세그먼트 잠금의 마스크 값입니다. 이 두 값은 배열에서 세그먼트 잠금의 첨자를 계산하는 데 사용되며 아래에서 이야기 할 것입니다. 세그먼트 잠금의 수를 계산 한 후 Ssize의 수는 총 들어오는 용량과 그 값 c = 초기 용량/ssize에 따라 각 세그먼트 잠금의 용량을 계산할 수 있습니다. 세그먼트 잠금의 용량은 해시 트리 어레이의 길이이며, 또한 2의 전력으로 보장되어야합니다. 위에서 계산 된 C의 값은 이것을 보장 할 수 없으므로 c는 해시트 어레이의 길이로 직접 사용할 수 없습니다. C에 가장 가까운 2의 다른 전력을 찾아이 값을 CAP에 할당 한 다음 해시트 배열의 길이로 캡을 사용해야합니다. 이제 SSIZE 및 CAP를 갖기 때문에 새 세그먼트 잠금 어레이 세그먼트 []와 요소 배열 해시트리 []를 만들 수 있습니다. JDK1.6과 달리 JDK1.7에서 세그먼트 배열 만 생성되었으며 초기화되지 않았습니다. 세그먼트 초기화 작업은 삽입 작업에 맡겨졌습니다.
4. 자물쇠를 찾고 요소를 찾는 방법은 무엇입니까?
// 해시 코드 @suppresswarnings ( "선택 취소") 개인 세그먼트 <k, v> segmentforhash (int h) {long u = ((H >>> segmentshift) & segmentmask) << sshift) + sbase; return (segment <k, v>) unsafe.getObjectvolatile (segments, u);} // 해시 코드를 기반으로 요소 가져옵니다 @suppresswarnings ( "Checked") 정적 최종 <k, v> hashentry <k, v> enthrichash (세그먼트 <k, v> seg, int h) {hashentry <k, v> [] 탭; return (seg == null || (tab = seg.table) == null)? NULL : (Hashentry <k, v>) unsafe.getObjectvolatile (탭, ((long) ((tab.length -1) & h))) << tshift) + tbase);} JDK1.7에서 안전하지 않은 것은 어레이 요소를 얻는 데 사용되므로 JDK1.6보다 배열 요소 오프셋을 계산하는 더 많은 코드가 있습니다. 우리는 당시이 코드에주의를 기울이지 않을 것입니다. 이제 우리는 다음 두 가지 요점 만 알아야합니다.
에이. 해시 코드를 통해 배열에 잠겨있는 세그먼트의 스크립트를 계산하십시오.
비. 해시 코드에 의해 배열에서 요소의 첨자를 계산하십시오 : (Tab.length -1) & h.
이제 생성자로 전달 된 두 매개 변수가 InitialCapacity = 128, ConcurrencyLevel = 16이라고 가정 해 봅시다. 계산에 따르면, 우리는 ssize = 16, sshift = 4, segmentshift = 28, segmentmask = 15를 얻을 수 있습니다. 마찬가지로, 각 세그먼트 잠금의 해시트 어레이의 길이는 8으로 계산되므로 Tab.length-1 = 7입니다. 이 값을 기반으로, 아래 그림을 통해 동일한 해시 코드를 기반으로 세그먼트 잠금 및 요소를 찾는 방법을 설명합니다.
세그먼트 잠금 및 요소 포지셔닝은 요소의 해시 코드에 의해 결정된다는 것을 알 수 있습니다. 포지셔닝 세그먼트 잠금은 해시 코드의 높은 값 (32 비트부터 시작)이며 포지셔닝 요소는 해시 코드의 낮은 값입니다. 이제 질문이 있습니다. 그들은 32 비트의 왼쪽 끝과 32 비트의 오른쪽 끝에서 시작합니다. 어느 시점에서 갈등이 있습니까? 멤버 변수에서 maximum_capacity = 1 << 30, max_segments = 1 << 16을 찾을 수 있습니다. 즉, 포지셔닝 세그먼트 잠금 및 포지셔닝 요소에 사용되는 총 비트 수가 30을 초과하지 않으며 위치 구간 잠금에 사용되는 비트 수가 16을 초과하지 않으므로 최소 2 비트가 남아 있지 않으므로 충돌이 없습니다.
5. 구체적으로 요소를 찾는 방법은 무엇입니까?
// get valuepublic v get (개체 키) {세그먼트 <k, v> s; Hashentry <k, v> [] 탭; // 해시 함수 int h = hash (key)를 사용하여 해시 코드를 계산합니다. // 해시 코드 long u = (((h >>> segmentshift) & segmentmask) << sshift) + sbase; // 세그먼트 잠금과 해당 해시 테이블을 가져옵니다. (Hashentry <k, v>) safe.getObjectvolatile ((long) (((tab.length -1) & h)) << tshift) + tbase) {k k; // 키와 해시에 따라 해당 요소의 값을 따르고 ((k = e.key) == key || (e.hash == h && key.equals (k))) {return e.Value; }}} return null;}JDK1.6에서, Get 세그먼트 잠금 방법은 첨자를 통해 배열 요소에 액세스하는 반면, JDK1.7에서는 배열의 요소는 안전하지 않은의 GetObjectVolatile 메소드를 통해 읽습니다. 왜 이렇게합니까? 우리는 세그먼트 객체에 의해 보유 된 해시트 배열 참조가 유형 휘발성이지만 배열의 요소 참조는 유형 휘발성이 아니므로 배열 요소에 대한 멀티 스레딩 수정은 안전하지 않으며 배열에서 아직 구성되지 않은 개체를 읽을 수 있습니다. JDK1.6에서, 두 번째 잠금 판독은 안전하다고 보장되며, JDK1.7에서는 안전하지 않은의 GetObjectVolatile 방법을 통한 읽기도이를 보장하는 것입니다. getObjectVolatile 메소드를 사용한 배열 요소를 읽으려면 먼저 배열에서 요소의 오프셋을 얻어야합니다. 여기서 해시 코드에 따르면 배열의 세그먼트 잠금의 오프셋은 u이며 오프셋 U는 세그먼트 잠금을 읽는 데 사용됩니다. 구조 중에 세그먼트 잠금 어레이가 초기화되지 않으므로 널 값을 읽을 수 있으므로 먼저 판단이 필요합니다. 세그먼트 잠금 및 내부 해시 테이블이 비어 있지 않음을 확인한 후 해시트 배열의 요소는 해시 코드를 통해 읽습니다. 위의 구조 다이어그램에 따르면, 현재 링크 된 목록의 헤더 노드가 얻어 졌음을 알 수 있습니다. 그런 다음 링크 된 목록을 처음부터 끝까지 횡단하고 검색하십시오. 해당 값이 발견되면 반환됩니다. 그렇지 않으면 NULL로 반환됩니다. 위는 요소를 찾는 전체 과정입니다.
6. 삽입 요소를 구현하는 방법은 무엇입니까?
// 키-값 쌍을 세트에 추가하십시오 (있는 경우 교체) @SuppressWarnings ( "확인되지 않은") public v put (k key, v value) {세그먼트 <k, v> s; // 전달 된 값은 (value == null) 던지면 새로운 nullpointerexception (); // 해시 함수 int hash = hash (key)를 사용하여 해시 코드를 계산합니다. // 해시 코드 int j = (Hash >>> segmentshift)를 기반으로 세그먼트 잠금의 첨자를 계산합니다. & segmentmask; // if ((s = (s = (세그먼트 <k, v>) unsafe.getObject (segments, (j << sshift) + sshift) + sbase) + sbase) == null)에 따라 세그먼트 잠금을 얻으려고 노력하십시오. } // 세그먼트 잠금 리턴의 풋 메소드를 호출합니다. S.put (키, 해시, 값, utcone);} // 키-값 쌍을 세트에 추가 (존재하지 않는 경우 추가) @SuppressWarnings ( "Checked") public v putifabsent (k key, v value) {segment <k, v> s; // 전달 된 값은 (value == null) 던지면 새로운 nullpointerexception (); // 해시 함수 int hash = hash (key)를 사용하여 해시 코드를 계산합니다. // 해시 코드 int j = (Hash >>> segmentshift)를 기반으로 세그먼트 잠금의 첨자를 계산합니다. & segmentmask; // if ((s = (s = (s = (s =) k, v>) unsafe.getObject (segments, (j << sshift) + sshift) + sbase)) == null)를 기반으로 세그먼트 잠금을 얻으십시오. {// s = ensuresegment (j); } // 캘린더 캘린더 세그먼트 잠금의 풋 메소드 리턴 S.put (키, 해시, 값, true);}Key-Value 쌍을 추가하는 ConsurenThashMap에는 두 가지 방법이 있습니다. 존재하면 PUT 방법을 통해 추가하면 덮어 씁니다. ifabsent 메소드는 put ifabsent 방법을 통해 추가되며 덮어 쓰지 않습니다. 두 가지 방법 모두 풋 세그먼트 잠금 방법을 호출하여 작동을 완료하지만 마지막으로 전달 된 매개 변수는 다릅니다. 위의 코드에서는 먼저 키의 해시 코드를 기반으로 배열에서 세그먼트 잠금의 첨자를 계산 한 다음 안전하지 않은 클래스 getObject 메소드를 사용하여 첨자에 따라 세그먼트 잠금을 읽습니다. ConcurrEthashMap을 구성 할 때 세그먼트 배열의 요소가 초기화되지 않으므로 널 값을 읽을 수 있으며 Ensuresegment 메소드를 통해 새로운 세그먼트 잠금이 생성됩니다. 세그먼트 잠금을 얻은 후 풋 방법을 호출하여 추가 작업을 완료하십시오. 작동 방법을 살펴 보겠습니다.
// 키 값 쌍 쌍 최종 v put (k 키, int 해시, v 값, 부울 만화 값) {// 잠금 장치를 얻으려고 시도합니다. NULL : ScanAndLockForput (키, 해시, 값); v OldValue; {hashentry <k, v> [] tab = table; // 요소의 첨자 int index = (tab.length -1) & hash를 계산합니다. // 위시 해시트리 <k, v> first = enlyat (탭, index)을 기반으로 링크 된 목록의 헤더 노드를 가져옵니다. for (hashentry <k, v> e = first ;;) {// 링크 된 목록을 전송하여 요소를 찾아야합니다 (e! = null) {k k; if ((k = e.key) == key || (e.hash == hash && key.equals (k)))) {OldValue = e.Value; // 매개 변수를 기준으로 이전 값을 대체할지 여부를 결정하십시오. ++ modcount; } 부서지다; } e = e.next; // 찾을 수없는 경우 링크 된 목록에 노드를 추가하십시오} else {// 링크 된 목록의 헤더에 노드 노드를 삽입하십시오 (node! = null) {node.setnext (첫 번째); } else {node = new Hashentry <k, v> (해시, 키, 값, 먼저); } // 노드를 삽입 한 후 항상 1 int c = count + 1을 추가하십시오. // 요소가 임계 값을 초과하면 (c> threshold && length <maximum_capacity) {rehash (node); // 그렇지 않으면 해시 테이블을 Node Node로 지정된 첨자} else {setEntryat (탭, index, node)로 바꿉니다. } ++ modcount; count = c; OldValue = null; 부서지다; }}} 마침내 {unlock (); } return oldValue;}스레드 안전을 보장하려면 세그먼트 잠금 장치에 작업을 잠금해야하므로 스레드는 처음에 잠금을 획득하고 획득이 성공하면 계속 실행됩니다. 취득이 실패하면 ScanAndLockForput 메소드를 호출하여 회전하십시오. 스핀 프로세스 중에 해시 테이블을 스캔하여 지정된 키를 찾으십시오. 키가 존재하지 않으면 새 해시트가 만들어 지므로 잠금을 얻은 후에 다시 만들 필요가 없습니다. 자물쇠를 기다리는 동안 일을하기 위해서는 헛된 시간을 낭비하지 않습니다. 이것은 저자의 좋은 의도를 보여줍니다. 나중에 특정 스핀 방법을 자세히 설명하겠습니다. 이제 초점을 먼저 되 찾으십시오. 스레드가 잠금을 성공적으로 얻은 후 계산 된 첨자에 기초하여 지정된 첨자의 요소를 얻습니다. 현재 링크 된 목록의 헤더 노드가 얻어집니다. 헤더 노드가 비어 있지 않으면 링크 된 목록이 횡단되어 검색됩니다. 그것을 찾은 후, 유일한 파라미터의 값에 따라 교체할지 여부를 결정하십시오. 트래버스를 찾을 수없는 경우 새 해시트가 헤더 노드를 가리 킵니다. 이 시점에서 스핀 중에 해시 트리가 생성되면 현재 헤더 노드 옆에 직접 가리 킵니다. 스핀이 생성되지 않으면 새 해시트가 여기에 생성되어 헤더 노드를 가리 킵니다. 링크 된 목록에 요소를 추가 한 후 총 요소 수가 임계 값을 초과하는지 확인하십시오. 초과하는 경우 확장을 위해 다시 해쉬를 호출하십시오. 초과하지 않으면 배열의 해당 첨자 요소를 새로 추가 된 노드에 직접 참조하십시오. SetentRyat 메소드는 안전하지 않은의 PutorderEdoBject 메소드를 호출하여 배열 요소 참조를 변경하여 다른 스레드가 읽을 때 최신 값을 읽을 수 있도록합니다.
7. 요소 삭제를 구현하는 방법은 무엇입니까?
// 지정된 요소를 삭제합니다 (해당 요소를 찾은 후 바로 삭제) public v 제거 (개체 키) {// 해시 함수를 사용하여 해시 코드 int Hash = Hash (키); // 해시 코드 세그먼트 <k, v> s = segmentforHash (HASH)를 기반으로 세그먼트 잠금의 색인을 얻습니다. // 세그먼트 잠금 장치의 제거 메소드를 달성하십시오. return s == null? null : s.remove (key, hash, null);} // 지정된 요소 삭제 (주어진 값과 동일 값을 제거) 공개 부울 제거 (개체 키, 개체 값) {// 해시 함수를 사용하여 해시 코드 int hash = hash (키)를 계산합니다. 세그먼트 <k, v> s; // 메소드 제거 메소드 return 값을 호출하기 전에 세그먼트 잠금이 비어 있지 않도록 할 수 있습니다! = null && (s = segmentforHash (hash))! = null && s.remove (key, hash, value)! = null;}ConsurenThashMap은 두 가지 삭제 작업을 제공합니다. 하나는 찾은 후 직접 삭제하는 것이고, 다른 하나는 먼저 비교 한 다음 찾은 후 삭제하는 것입니다. 이 삭제 방법은 키의 해시 코드를 기반으로 해당 세그먼트 잠금을 찾은 다음 세그먼트 잠금의 제거 메소드를 호출하여 삭제 작업을 완료하는 것입니다. 세그먼트 잠금의 제거 방법을 살펴 보겠습니다.
// 지정된 요소 삭제 최종 V Final v 제거 (개체 키, int 해시, 개체 값) {// 잠금 장치를 얻으려고 시도합니다. } v OldValue = null; {hashentry <k, v> [] tab = table; // 요소의 첨자 int index = (tab.length -1) & hash를 계산합니다. // 첨자 (링크 목록 헤더 노드)에 따라 배열 요소를 가져옵니다 <k, v> e = enlicat (탭, index); Hashentry <k, v> pred = null; // 링크 된 목록을 전송하려면 (e! = null) {k k; // 다음은 현재 노드 해시트 리의 후속 노드를 가리 킵니다 <k, v> next = e.next; // 키와 해시 if ((k = e.key) == key || (e.hash == hash && key.equals (k)) {v v = e.value; // v와 동일하지 않은 경우 전달 된 값을 건너 뛰고 다른 경우 (value == null || value == v value.equals (v)) {// pred가 삭제 될 노드가 링커 노드라는 것을 의미합니다. } else {// 예측 노드의 승계를 다음 노드로 설정했습니다. pred.setnext (다음); } ++ modcount; --세다; // 요소의 값을 기록하십시오 삭제 OldValue = V; } 부서지다; } // e가 찾고있는 노드가 아닌 경우 Pred Reference Pred = E; // 다음 노드를 확인하십시오 e = 다음; }} 마침내 {unlock (); } return oldValue;}세그먼트 잠금에서 요소를 삭제할 때는 먼저 잠금 장치를 획득해야합니다. 획득이 실패하면 스피닝을 위해 ScanAndLock 메소드를 호출하십시오. 취득이 성공하면 다음 단계를 실행하십시오. 먼저 배열 첨자를 계산 한 다음 첨자를 통해 해시트 배열의 요소를 얻습니다. 여기서 링크 된 목록의 헤더 노드가 얻어집니다. 다음으로 횡단하고 링크 된 목록을 검색하십시오. 그 전에 다음 포인터를 사용하여 현재 노드의 후속 노드를 기록한 다음 키와 해시를 비교하여 원하는 노드인지 확인하십시오. 그렇다면 다음 if 판단을 수행하십시오. 값이 비어 있거나 값이 노드의 현재 값과 같으면 삭제에 대한 if 문을 입력하면 직접 건너 뜁니다. IF 문에서 삭제 작업을 수행 할 때 두 가지 상황이 있습니다. 현재 노드가 헤더 노드 인 경우 다음 노드를 헤더 노드로 직접 설정하십시오. 현재 노드가 헤더 노드가 아닌 경우 프레드 노드의 후속 장치를 다음 노드로 설정하십시오. 여기서 예측 노드는 현재 노드의 이전 모델을 나타냅니다. 다음 노드를 확인하기 전에 매번, 프레드는 현재 노드를 가리키며, 이는 프리 노드가 항상 현재 노드의 이전 모델임을 보장합니다. JDK1.6과 달리 JDK1.7의 해시트 객체의 다음 변수는 최종적이지 않으므로 다음에 참조 된 값을 직접 수정하여 요소를 삭제할 수 있습니다. 다음 변수는 휘발성 유형이므로 읽기 스레드는 즉시 최신 값을 읽을 수 있습니다.
8. 교체 요소는 구체적으로 어떻게 구현됩니까?
// 지정된 요소 (CAS 조작) public boolean replare (k key, v OldValue, v newValue) {// 해시 함수를 사용하여 해시 코드 int hash = hash (key); // (OldValue == null || newValue == NULL) if nullPointerException (); // 해시 코드 세그먼트 <k, v> s = segmentforHash (HASH)를 기반으로 세그먼트 잠금의 색인을 가져옵니다. // 세그먼트 잠금 장치의 교체 방법을 호출하면 s! = null && s.replace (키, 해시, OldValue, newValue);} // 요소 작동 (CAS 작동) 최종 부울 대체 (K 키, int 해시, v OldValue, v newValue) {// 잠금을 얻으려고 시도하는 경우 (!) } 부울 교체 = 거짓; {hashentry <k, v> e; // 헤더 노드를 해시를 통해 직접 검색 한 다음 (e = EntrysforHash (this, hash); e! = null; e = e.next) {k k; // 키와 해시 if ((k = e.key) == key || (e.hash == hash && key.equals (k))) {// 지정된 현재 값이 올바른 경우 (oldValue.equals (e.value)) {e.value = newValue; ++ modcount; 교체 = 참; } // 그렇지 않으면 작업이 수행되지 않으면 휴식을 반환하십시오. }}} 마침내 {unlock (); } return 교체;}ConsurenThashMap은 또한 두 가지 교체 작업을 제공합니다. 하나는 찾은 직후 교체하고, 다른 하나는 먼저 비교 한 다음 (CAS 조작)를 교체하는 것입니다. CAS 운영에는 교체하기 전에 비교 작업의 추가 계층이 있다는 점을 제외 하고이 두 작업의 구현은 거의 동일하므로 작업 중 하나만 이해하면됩니다. 여기서 우리는 여전히 오래된 루틴 인 분석을 위해 CAS 작업을 사용합니다. 먼저 키의 해시 코드를 기반으로 해당 세그먼트 잠금을 찾은 다음 교체 방법을 호출하십시오. 세그먼트 잠금에 교체 메소드를 입력 한 후에는 먼저 잠금 장치를 획득해야합니다. 취득이 실패하면 회전하십시오. 인수가 성공하면 다음 단계로 진행하십시오. 먼저 해시 코드에 따라 링크 된 목록의 헤더 노드를 얻은 다음 키와 해시에 따라 트래버스 및 검색을하십시오. 해당 요소를 찾은 후 주어진 OldValue가 현재 값인지 비교하십시오. 그렇지 않은 경우 수정을 포기하고 그렇다면 새 값으로 바꾸십시오. 해시트 객체의 값 필드는 휘발성 유형이므로 직접 교체 할 수 있습니다.
9. 회전 할 때 정확히 무엇을 했습니까?
// 잠금을 얻기 위해 대기 대기 (PUT 작동) 개인 해시트리 <k, v> scanandlockforput (k 키, int hash, v value) {// 해시 코드 해시트 <k, v> first = entherforhash (this, hash)에 따라 헤더 노드를 가져옵니다. Hashentry <k, v> e = 첫 번째; Hashentry <k, v> node = null; int retries = -1; // spin while (! trylock ()) {hashentry <k, v> f; if (retries <0) {// 헤더 노드가 비어있는 경우 if (e == null) {if (node == null) {node = new Hashentry <k, v> (hash, key, value, null); } retries = 0; // 그렇지 않으면, 링크 된 목록을 통과하여 노드를 찾아} else if (key.equals (e.key)) {retries = 0; } else {e = e.next; } // 리트리는 매번 여기에 1을 추가하고 최대 값을 초과하는지 여부를 결정합니다. 부서지다; // 리트리가 짝수 숫자 일 때 첫 번째 변경 여부를 결정하십시오} else if ((Retries & 1) == 0 && (f = entherforHash (this, hash))! = 첫 번째) {e = first = f; 재시도 = -1; }} return node;} // 잠금을 얻기 위해 대기 대기 (작업 제거 및 교체) 개인 void scanandlock (객체 키, int hash) {// 해시 코드 해시 트리 <k, v> first = entherforhash (this, hash)에 따라 링크 된 목록의 헤더 노드를 가져옵니다. Hashentry <k, v> e = 첫 번째; int retries = -1; // spin while (! trylock ()) {hashentry <k, v> f; if (retries <0) {// 링크 된 목록을 전송 if (e == null || key.equals (e.key)) {retries = 0; } else {e = e.next; } // 리트리는 매번 여기에 1을 추가하고 최대 값을 초과하는지 여부를 결정합니다. 부서지다; // 리트리가 짝수 숫자 일 때 첫 번째 변경 여부를 결정하십시오} else if ((Retries & 1) == 0 && (f = entherforHash (this, hash))! = 첫 번째) {e = first = f; 재시도 = -1; }}}앞에서 언급했듯이 세그먼트 잠금 장치의 작업을 넣고 제거하고 교체하려면 잠금 장치를 먼저 취득해야합니다. 잠금을 성공적으로 얻은 후에 만 다음 작업을 수행 할 수 있습니다. 획득이 실패하면 스핀이 수행됩니다. 스핀 작동은 JDK1.7에도 추가됩니다. 스레드의 빈번한 일시 중단 및 깨우기를 피하기 위해 동시 작업 중에 성능을 향상시킬 수 있습니다. ScanAndLockForput은 PUT 방법에서 호출되며 ScanAndlock은 제거 및 교체 방법에서 호출됩니다. 두 가지 스핀 방법은 거의 동일합니다. 여기서는 ScanAndLockforput 방법 만 분석합니다. 우선, 해시 코드를 기반으로 링크 된 목록의 헤더 노드를 얻어야합니다. 그런 다음 스레드가 while 루프를 입력하여 실행됩니다. 루프를 종료하는 유일한 방법은 잠금을 성공적으로 얻는 것입니다.이 기간 동안 스레드가 매달리지 않습니다. 루프가 방금 입력되면 재시도 값은 -1입니다. 현재 스레드는 즉시 잠금을 획득하려고 시도하지 않습니다. 대신, 먼저 키에 해당하는 노드를 찾은 다음 (찾을 수없는 경우, 새 제품이 생성됩니다), 다시 리트리를 0으로 설정합니다. 다음에 잠금을 반복해서 얻으려고합니다. 최대 시도 횟수가 최대 시도 수를 초과 할 때까지 해당 회수 값도 매번 1을 추가합니다. 잠금 장치가 얻지 못하면 차단 및 획득을 위해 잠금 방법이 요구됩니다. 잠금을 얻으려고 시도하는 동안 헤더 노드가 매번 변경되었는지 여부를 확인합니다 (검색이 짝수). 변경되면 재 검색을 -1로 다시 재설정 한 다음 지금 프로세스를 반복하십시오. 이것이 회전 할 때 실이하는 일입니다. 스핀 중에 헤드 노드가 변경되는 것으로 감지되면 스레드의 스핀 시간이 확장됩니다.
10. 해시 테이블을 확장 할 때 어떤 작업이 수행됩니까?
// 해시가 다시 @SuppressWarnings ( "확인되지 않은") Private void reshash (hashentry <k, v> node) {// 이전 해시 테이블 hashentry <k, v> [] oldtable = table; // 이전 해시 테이블의 용량을 가져옵니다 int OldCapacity = OldTable.length; // 새 해시 테이블의 용량을 계산합니다 (오래된 해시 테이블의 2 배) int newCapacity = OldCapacity << 1; // 새 요소 임계 값 임계 값 계산 = (int) (newCapacity * loadfactor); // 새 해시트 어레이 해시트리를 만듭니다 <k, v> [] newtable = (Hashentry <k, v> []) new Hashentry [newcapacity]; // 새 마스크 값 생성 int sizemask = newCapacity -1; // (int i = 0; i <oldcapacity; i ++)에 대한 기존 테이블의 모든 요소를 통한 평온함 {// 링크 된 목록의 헤더 노드를 가져옵니다. hashentry <k, v> e = OldTable [i]; if (e! = null) {hashentry <k, v> next = e.next; // 새 테이블에서 요소의 색인을 계산합니다 int idx = e.hash & sizesmask; // 다음은 링크 된 목록에 하나의 노드 만 있음을 나타 내기 위해 비어 있습니다 (next == null) {// 노드를 새 테이블 newtable [idx] = e에 직접 넣습니다. } else {hashentry <k, v> lastrun = e; int lastidx = idx; // lastrun 노드를 배치하고 lastrun 후의 노드를 직접 새 테이블에 넣습니다. if (k! = lastIdx) {lastIdx = k; lastrun = 마지막; }} newtable [lastIdx] = lastrun; // 링크 된 목록의 Lastrun 노드 앞에서 요소를 트랜스 립핑하고 (Hashentry <k, v> p = e; p! = lastrun; p = p.next) {v v = p.Value; int h = p.hash; int k = h & sizesmask; Hashentry <k, v> n = newtable [k]; newtable [k] = New Hashentry <k, v> (h, p.key, v, n); }}}}} // 새 테이블에서 들어오는 노드의 위시를 계산 int nodeindex = node.hash & sizesmask; // 링크 된 목록 노드의 헤더 노드에 들어오는 노드를 추가합니다. // 새 테이블 지정된 첨자 요소를 들어오는 노드 NewTable [NodeIndex] = 노드로 교체합니다. // 해시 테이블을 가리키는 새 테이블 테이블 = newtable;}푸트 방법에서 재사용 방법이 호출됩니다. 우리는 PUT 방법을 넣을 때 새 요소가 생성되어 해시 어레이에 추가 될 것임을 알고 있습니다. 해시 충돌 가능성이 높을수록 해시 테이블의 성능이 커질 것입니다. 따라서 PUT 작업이있을 때마다 총 요소 수가 임계 값을 초과하는지 확인합니다. 임계 값을 초과하면 재사용 방법이 확장을 요구합니다. 배열의 길이는 결정되면 더 이상 변경할 수 없으므로 원래 배열을 교체하기 위해 새로운 배열을 만들어야합니다. 코드에서 새로 생성 된 배열이 원래 배열의 길이의 두 배 (OldCapacity << 1)임을 알 수 있습니다. After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
위는이 기사의 모든 내용입니다. 모든 사람의 학습에 도움이되기를 바랍니다. 모든 사람이 wulin.com을 더 지원하기를 바랍니다.