데이터 구조 - map jdk 1.8

8319 단어 데이터 구조
데이터 구조 - map jdk 1.8
  • 데이터 구조 - map jdk 1.8
  • Hashmap
  • 데이터 구조
  • 값 은 어디 에 놓 습 니까?
  • Hash 충돌
  • 배열 확장
  • 교체 기


  • Hashmap
          16,  0.75,    8,    6
    

    데이터 구조
    데이터 구조의 최종 목표: 빠 른 속도 로 고 친 것 도 빠 른 조회 속도: 배열 의 삭제 속도: 링크
    JDK 1.8 이전 에는 배열 + 링크 의 구 조 를 이용 하여 이들 의 장점 을 종합 했다.
    링크 조회 가 느 리 기 때문에 O (n), JDK 1.8 이후 링크 를 최적화 시 켰 고 특정한 조건 을 만족 시 킬 때 전체 링크 는 빨간색 과 검은색 나무 로 바 뀌 었 다.
    어디 에 놓 을 만 한 가치 가 있 는가
    확인
        //   :                       
        int index = hashCode % tab.cap ;//            hashcode         
    
        //   :    CPU      ,             2        tab.cao-1 = 011111111
        //          hashCode 
        int index = hashCode & (tab.cap -1);
    
        //101110001110101110 1001 &0 1111 = 1001 = 9
        //       tab.cap-1     01111111                  hashcode,
        //     2 n  ,                ,    

    이것 도 데이터 의 초기 용량 요구 가 2 의 n 제곱 인 이유 이다 (예 를 들 어 16).
    사용 방식 2 의 연산 은 아래 표 시 를 계산 할 때 원래 hashcode 의 낮은 비트 만 사용 합 니 다. 충돌 이 더욱 적 음 을 확보 하기 위해 서 또는 연산 을 통 해 높 은 16 비트 와 낮은 비트 를 결합 하여 데이터 충돌 확률 이 더욱 낮 습 니 다.
    물론 아래 표 시 된 값 이 있 으 면 hash 충돌 이 발생 합 니 다.
    해 쉬 충돌
    hashmap 인 이상 hash 충돌 은 피 할 수 없습니다. hashmap 는 같은 위치 에 값 이 있 는 것 을 발 견 했 을 때 링크 아래로 내 려 갑 니 다. 만약 에 삽입 한 후에 링크 의 길이 가 8 에 이 르 면 빨간색 과 검은색 나 무 는 왜 빨간색 과 검은색 나 무 를 돌려 링크 의 길 이 를 8 로 요구 합 니까?개인 적 으로 최 적 화 된 목 표 는 조회 효율 을 높이 기 위 한 것 이 고 레 드 블랙 트 리 로 전환 하 는 과정 도 CPU 가 계산 해 야 하기 때문에 이 전환 의 조건 이 향상 되 어야 하 는 조회 효율 은 전환 의 소 모 를 상쇄 할 수 있 고 습관 적 으로 2 의 차방 으로 계산 할 수 있다. O (n) vs O (logn) 는 8 회 에 달 하면 링크 조회 0 ~ 8 회, 레 드 블랙 트 리 0 ~ 3 회 이다.이 조회 효율 의 증 가 는 이미 상쇄 할 수 있다 고 생각한다.
    부분 소스 코드
    public V put(K key, V value) {
            //     hash         K hashCode
            return putVal(hash(key), key, value, false, true);
     }
    
     static final int hash(Object key) {
            int h;
            // 32  hashcode     ,                               
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node[] tab; Node p; int n, i;
            if ((tab = table) == null || (n = tab.length) == 0)
            //    (n - 1) & hash
            if ((p = tab[i = (n - 1) & hash]) == null)
                //             
                tab[i] = newNode(hash, key, value, null);
            else {
                Node e; K k;
                //hash  
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //hash                  
                else if (p instanceof TreeNode)
                    e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //hash        
                     for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                            //     =8 ,       
                            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                //hash    equals           
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            //    +1                 /foreach                    ,   fail-fast    
            ++modCount;
            if (++size > threshold)//16*0.75=12
                resize();//                   
            afterNodeInsertion(evict);
            return null;
        }

    배열 확장
           hash
    a.   :          ,  put       hash   ,       
                    
    b.  :    /  /    ,               ,    
    

    교체 기
    hashmap      foreach         
    
    public void forEach(BiConsumer super K, ? super V> action) {
            //       ,  tab,       Node,   fail-fast
            Node[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node e = tab[i]; e != null; e = e.next)
                        action.accept(e.key, e.value);
                }
                //        modCount      , map     ,  fail-fast
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

    좋은 웹페이지 즐겨찾기