자바 소스 코드 ConcurrentHashMap

10661 단어 JavaConcurrentHashMap
기록 형식
프로 세 스 를 원본 코드 에 직접 쓰 려 면 순서대로 주석 을 달 고 찾 아 볼 때 번호 에 따라 주석 부분 만 볼 수 있 습 니 다.
2.ConcurrentHashMap
이러한 사용 과정 을 직접 모 의 한 다음 에 한 걸음 한 걸음 어떻게 작 동 하 는 지 보 는 것 이 좋 습 니 다.물론 문 제 를 가지 고 한 번 생각 하고 정리 하 는 것 이 좋 습 니 다.저 는 소스 코드 를 읽 을 때 다음 과 같은 몇 가지 문 제 를 가지 고 있 습 니 다.
  • 병발 은 어디 에 나타 납 니까?스 레 드 안전 을 어떻게 보장 합 니까?
  • 어떻게 확 대 했 습 니까?용량 을 늘 리 는 것 은 어떻게 라인 의 안전 을 보장 합 니까?
  • 어떻게 넣 었 어 요?put 는 어떻게 라인 의 안전 을 보장 합 니까?
  • 은 어떤 자 물 쇠 를 사 용 했 습 니까?이 자물쇠 들 의 작용 은 무엇 입 니까?
  • 은 어떤 관건 을 유의 해 야 합 니까?
  • 우리 가 가장 간단하게 사용 하 는 방법 은 어 떻 습 니까?
  • new 하나의 Concurrent HashMap 대상
  • puut 방법 을 k-v 대
  • 에 넣 습 니 다.
  • 호출 get 방법 획득 k-v 대
  • 그러면 분명히 수정 과 업 데 이 트 를 할 때 병행 을 고려 해 야 하기 때문에 제 가 주목 하 는 중점 은 put 방법 과 확대 에 있 습 니 다.
    우선 new 대상 이 있 을 때,우 리 는 하나의 size 를 전송 하여 하나의 매개 변수 만 있 는 구조 기 를 호출 합 니 다.
    
    public ConcurrentHashMap(int initialCapacity) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException();
            // 1、                 ,        
            // 2、    ,   tableSizeFor
            // 3、tableSizeFor   size 2   ,     2    ?   hash     
            //       ,  size 2        
            int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                       MAXIMUM_CAPACITY :
                       tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
            this.sizeCtl = cap;
        }
    
    
    // 1、                 ,        
    // 2、    ,   tableSizeFor
    // 3、tableSizeFor size 2   ,     2    ?   hash     
    //       ,  size 2        
    이 때 맵 데이터 구 조 를 만 들 지 않 았 기 때문에 Concurrent HashMap 은 게 으 름 으로 만 들 어 졌 습 니 다.
    이어서 우 리 는 put 방법 을 호출 하여 데 이 터 를 넣 고 put 방법 을 조정 한 puutVal
    
    final V putVal(K key, V value, boolean onlyIfAbsent) {
       		// 1、k-v     ,     
            if (key == null || value == null) throw new NullPointerException();
            // 2、  key hashcode hash 
            int hash = spread(key.hashCode());
            // 3、  binCount            ,               
            int binCount = 0;
            // 4、  tab    ,    table,       ,  null
            //      ,table    Node  ,  Node    Map.Entry<K,V>
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                // 5、  tab         ,            
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                // 6、         ,        。
                //    tabAt(tab,i)  tab  i         
                //    ,(n-1)& hash    hash%n,  n 2        
                //          
                // 7、f       i         
                //    null       ,        
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                	// 8、            ,casTab   cas      
                	//       Node  ,            
                	//              cas     ,             
                	//      tab    ,tab    table  , table   volatile 
                	//       
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
                // 9、  f   ,  f.hash==MOVED(-1),             
                //         ,              ,    helpTransfer     
                //    ,                  ,       f.hash  MOVED
                //                                ,         
                else if ((fh = f.hash) == MOVED)
                    tab = helpTransfer(tab, f);
                // 10、  f.hash       , f  null              
                //       ,          
                else {
                    V oldVal = null;
                    // 11、        ,     ,    ,    synchronized
                    //             (           )
                    //          ,           
                    //                  ,      
                    synchronized (f) {
                    	//   f   
                        if (tabAt(tab, i) == f) {
                        	// 12、  f.hash   0,  0           
                        	//            
                            if (fh >= 0) {
                                binCount = 1;
                                // 13、           ,           
                                //          ,            
                                //          
                                // 14、  ,           binCount
                                //            ,          
                                for (Node<K,V> e = f;; ++binCount) {
                                    K ek;
                                    if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                         (ek != null && key.equals(ek)))) {
                                        oldVal = e.val;
                                        if (!onlyIfAbsent)
                                            e.val = value;
                                        break;
                                    }
                                    Node<K,V> pred = e;
                                    if ((e = e.next) == null) {
                                        pred.next = new Node<K,V>(hash, key,
                                                                  value, null);
                                        break;
                                    }
                                }
                            }
                            // 13、  f       ,          
                            else if (f instanceof TreeBin) {
                                Node<K,V> p;
                                binCount = 2;
                                if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                               value)) != null) {
                                    oldVal = p.val;
                                    if (!onlyIfAbsent)
                                        p.val = value;
                                }
                            }
                        }
                    }
                    // 14、     ,binCount        ,           
                    //      ,       TREEIFY_THRESHOLD=8
                    if (binCount != 0) {
                        if (binCount >= TREEIFY_THRESHOLD)
                            treeifyBin(tab, i);
                        if (oldVal != null)
                            return oldVal;
                        break;
                    }
                }
            }
            // 15、addCount  size+1 
            //      ,        ,   get  +,               cas 
            //    size         size  ,  size      ,            
            //      LongAdder         ,   CountCell  ,           
            //    Cell,      
            addCount(1L, binCount);
            return null;
        }
    
    put 의 과정 을 정리 하 겠 습 니 다.
    1.맵 생 성 여 부 를 판단 하고 생 성 되 지 않 으 면 먼저 생 성 합 니 다.구 조 는 Node[]extend Map.Entry 입 니 다.
    2.키 를 어느 위치 에 두 어야 할 지 찾 아 i
    3.이 위치 가 비어 있 는 지 여 부 를 판단 하고 비어 있 으 면 CAS 를 사용 하여 새 노드 를 삽입 합 니 다.
    4.비어 있 지 않 으 면 현재 위치 상태 가 MOVED 인지 여 부 를 판단 합 니 다.이 는 현재 위치 가 다른 스 레 드 에 의 해 변경 되 고 있 음 을 의미 합 니 다.현재 스 레 드 는 이동 을 완료 하 는 데 도움 이 필요 합 니 다.
    5.비어 있 지 않 고 MOVED 가 아 닌 경우 링크 인지 트 리 인지 판단 하여 해당 하 는 업데이트 방법 을 각각 실행 합 니 다.
    6.링크 라면
  • 먼저 링크 를 잠 그 고 syn
  • 을 사용 합 니 다.
  • 이 존재 하 는 지 찾 습 니 다.
  • 마지막 에 존재 하지 않 으 면 바로 꼬리 에
  • 을 꽂 습 니 다.
  • 동시 통계 체인 테이블 의 원소
  • 7.링크 요소 가 나무 로 변 하 는 한도 값 8 을 초과 하 는 지 판단 하고 초과 하면 나무 로 변 하 며 나무 로 변 하 는 것 도 syn 이다.
    8.addCount 를 사용 하여 size 를 업데이트 합 니 다.업데이트 방식 은 LongAdder 와 유사 합 니 다.
    관건
  • 게 으 름 로드 맵
  • 현재 위치 조작 전에 현재 위치 에 저 장 된 내용 이 다른 스 레 드 에 의 해 이동 되 었 는 지 판단 해 야 합 니 다.이동 되면 먼저 이동 완료
  • 을 도와 야 합 니 다.
    확장 이동 을 실행 하 는 스 레 드 는 각 위 치 를 이동 하 는 링크 입 니 다.이동 하기 전에 현재 위치 상 태 를 CAS 로 MOVED 로 변경 합 니 다.
    주의 하 세 요.이게 병발 도 를 높이 는 관건 이에 요.
    삽입 과 이동(확장)의 입 도 는 각 위치 로 세분 화 된 링크 이기 때문이다.
    확장 과 삽입 이 동시에 가능 하 다 는 뜻 이다.
    삽입 시 자 물 쇠 를 잠 근 후 확장 스 레 드 가 이 위치 로 실행 되 려 면 차단 이 필요 하 다 는 뜻 입 니 다.
    맵 전 체 를 잠 그 는 게 아니 라.
  • 현재 위치 에 내용 이 없 을 때 CAS 를 통 해 새 노드 를 삽입 하고 링크 를 조작 할 때 syn
  • 을 사용 합 니 다.
    면접 에서 Concurrent HashMap 에 어떤 자 물 쇠 를 썼 는 지 물 어보 면 알 수 있어 요.
  • 사이즈 업 데 이 트 를 할 때 LongAdder 와 비슷 한 방법 을 썼어 요.
  • .
    CountCell 배열 이 있 습 니 다.스 레 드 마다 업데이트 되면 배열 의 한 Cell+1 에 대해
    경쟁 이 없 으 면 baseCell 하나,그+1
    사이즈 집계 시 집계 하면 됩 니 다.
    앞의 절 차 를 좀 더 세분 화 하 겠 습 니 다.
    맵 을 초기 화 할 때 어떻게 라인 의 안전 을 보장 합 니까?여러 스 레 드 가 동시에 초기 화 되 는 것 을 방지 합 니까?
    정 답 은 initTable 방법 중 에 있 습 니 다.
  • 에서 볼 수 있 듯 이 sizeCtl 이 음수 라면 확장 하거나 초기 화 하고 있 음 을 설명 합 니 다
  • 따라서 초기 화가 필요 할 때 CAS 에 가서 sizeCtl 을 바 꾸 고 마이너스
  • 으로 바 꿉 니 다.
  • 어느 스 레 드 CAS 가 성공 하면 초기 화 를 실행 할 수 있 습 니 다.이것 은 스 레 드 안전
  • 을 보장 합 니 다.
  • 다시 볼 수 있 습 니 다.sizeCtl 은 volatile 이 수식 한 하
  • 입 니 다.
  • 그리고 SIZECTL 은 sizeCtl 의 offset 입 니 다.이것들 은 모두 원자 류 와 유사 한 것 입 니 다.
  • 
    private final Node<K,V>[] initTable() {
            Node<K,V>[] tab; int sc;
            while ((tab = table) == null || tab.length == 0) {
                if ((sc = sizeCtl) < 0)
                    Thread.yield(); // lost initialization race; just spin
                else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if ((tab = table) == null || tab.length == 0) {
                            int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                            @SuppressWarnings("unchecked")
                            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                            table = tab = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        sizeCtl = sc;
                    }
                    break;
                }
            }
            return tab;
        }
    
    get 방법 은 말 하지 않 겠 습 니 다.동시 다발 과 관련 되 지 않 기 때문에 찾 을 뿐 입 니 다.
    느낌 이 별로 좋 지 않 습 니 다.put 방법 을 알 아 보 았 습 니 다.Concurrent HashMap 은 스 레 드 안전 을 어떻게 해결 하 는 지 잘 알 고 있 습 니 다.그리고 병발 의 관건 은 어디 에 있 는 지 잘 알 고 있 습 니 다.
    자바 소스 코드 인 Concurrent HashMap 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 자바 Concurrent HashMap 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 부탁드립니다!

    좋은 웹페이지 즐겨찾기