HashMap 의 put 원리 분석.

JDK 1.7 VS JDK 1.8 비교
JDK 1.8 은 주로 문 제 를 해결 하거나 최적화 시 켰 다.
사이즈 확장 최적화
4.567917.빨간색 과 검은색 나 무 를 도 입 했 는데 그 목적 은 단일 링크 가 너무 길 어서 조회 효율 에 영향 을 주지 않도록 하 는 것 이다
4.567917.다 중 스 레 드 순환 문 제 를 해결 하 였 으 나 비 스 레 드 가 안전 하고 다 중 스 레 드 일 때 데이터 손실 문 제 를 초래 할 수 있 습 니 다
먼저 소스 코드 를 보 겠 습 니 다.
1 층 은 puutVal 을 호출 하 는 방법 입 니 다.

   public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

puutVal 다시 보기:

    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 = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

1.키 값 이 배열 table[i]이 비어 있 거나 길이 가 0 인지 판단 하고,만약 에 resize()를 실행 하여 확장 합 니 다.
2.키 키 키 에 따라 hash 가 삽입 할 수 있 는 배열 색인 i 를 계산 합 니 다.table[i]=null 이 있 으 면 새 노드 를 직접 추가 하고 삽입 에 성공 하면 실제 존재 하 는 키 쌍 을 판단 합 니 다.      수량 size 가 최대 용량 threshold 를 초과 하 였 는 지,초과 하면 확장 합 니 다.table[i]가 비어 있 지 않 으 면.그렇지 않 으 면
3.table[i]의 첫 번 째 요소 가 key 와 같 는 지 판단 합 니 다.같은 값 으로 value 를 직접 덮어 쓰 지 않 으 면 table[i]가 빨 간 검 은 나무 인지,즉 table[i]가 빨 간 검 은 나무 인지 판단 합 니 다.빨 간 검 은 나무 라면 트 리 에 키 값 을 직접 삽입 합 니 다.그렇지 않 으 면 table[i]를 옮 겨 다 니 며 링크 길이 가 8 이상 인지 판단 합 니 다.8 이상 이면 treeifybin 방법()안쪽 을 호출 하여 배열 이 64 이상 인지 아 닌 지 를 판단 한 다음 에 링크 를 빨 간 검 은 나무 로 바 꾸 고 빨 간 검 은 나무 에서 삽입 작업 을 수행 합 니 다.그렇지 않 으 면 링크 의 삽입 작업 을 합 니 다.옮 겨 다 니 는 과정 에서 key 가 존재 하 는 것 을 발견 하면 value 를 직접 덮어 쓰 면 됩 니 다.
4.삽입 에 성공 한 후 실제 존재 하 는 키 값 이 수량 size 에 최대 용량 threshold 를 초과 하 였 는 지 판단 하고 초과 하면 확장 합 니 다.
해시 맵 은 어떤 방법 을 사용 하여 해시 충돌 을 효과적으로 해결 하 는 지 간단하게 요약 합 니 다.
1.체인 주소 법(산 목록 사용)을 사용 하여 같은 hash 값 을 가 진 데 이 터 를 연결 합 니 다.2.2 차 교란 함수(hash 함수)를 사용 하여 해시 충돌 확률 을 낮 추고 데이터 분 포 를 더욱 고 르 게 한다.3.붉 은 검 은 나 무 를 도입 하여 옮 겨 다 니 는 시간의 복잡 도 를 더욱 낮 추어 옮 겨 다 니 는 것 이 빠르다.
그의 확장 체 제 를 살 펴 보고 먼저 소스 코드 resize()방법 을 봅 니 다.

  final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

1.jdk 1.8 에서 resize 방법 은 hashmap 의 키 값 이 밸브 값(현재 용량*0.75)보다 크 거나 초기 화 될 때 resize 방법 으로 확장 하 는 것 입 니 다.
2.매번 확장 할 때마다 2 배 확장;
3.확장 후 Node 대상 의 위 치 는 원래 위치 에 있 거나 원래 의 오프셋 두 배 위치 로 이동 합 니 다.
puutVal()에서 우 리 는 이 함수 에서 2 차 resize()방법 을 사용 한 것 을 보 았 다.resize()방법 은 첫 번 째 초기 화 를 할 때 이 를 확대 하거나 이 배열 의 실제 크기 가 임계값(첫 번 째 는 12)보다 크 면 확대 하 는 동시에 수반 되 는 통 위의 요 소 를 다시 나 누 어 주 는 것 을 나타 낸다.이것 도 JDK 1.8 버 전의 최 적 화 된 부분 이다.1.7 에서 용량 을 확대 한 후에 Hash 값 을 다시 계산 하고 Hash 값 에 따라 나 누 어 주어 야 한다.그러나 1.8 버 전에 서 는 같은 통 의 위치 에서(e.hash&oldCap)가 0 인지 아 닌 지 를 판단 하고 hash 값 에 따라 분배 한 후에 이 요소 의 위 치 는 원래 위치 에 머 무 르 거나원본 위치+추 가 된 배열 크기 로 이동 하거나