함께 소스 코드 에서 자바 시리즈 배우 기 (1) (util)

어떻게 IDEA 로 소스 코드 를 확인 합 니까?
저 는 util 패키지 에서 배 웠 습 니 다 (구조 모듈 에 따라) [본 고 는 jdk 8 을 바탕 으로 합 니 다]
분석 Collection 인터페이스

public interface Collection<E> extends Iterable<E>

Iterable 부모 인 터 페 이 스 를 계승 하면 이 인터페이스의 실현 은 모두 교체 기 를 얻 을 수 있 습 니 다.
서브 인터페이스
Set
아래 의 영문 단락 은 모두 jdk 문서 의 정의 입 니 다.
A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.
다 중 요소 가 없 는 집합 입 니 다. 더욱 정확 한 것 은 집합 에 한 쌍 의 요소 e1, e2 가 존재 하지 않 고 e1. equals (e2) 를 만 들 며 최대 한 개의 빈 요소 만 있 습 니 다.말 그대로 이 인 터 페 이 스 는 수학 에서 집합 한 추상 적 인 모델 (추상 적 인 모델) 이다.
//TODO
AbstractCollection
//TODO
Queue
//TODO
List

AbstractList

AbstractSequentialList

This class provides a skeletal implementation of the List interface to minimize the effort required to implement this interface backed by a “sequential access” data store (such as a linked list). For random access data (such as an array), AbstractList should be used in preference to this class.
이 종 류 는 '연속 방문' 을 실현 하 는 List 인터페이스 (예 를 들 어 링크) 의 뼈 대 를 가장 간소화 했다.무 작위 접근 데이터 (예 를 들 어 배열) 에 대해 서 는 abstractList 를 우선 사용 해 야 합 니 다.
지도 인터페이스
상용 데이터 구조
선형 표
체인 테이블
LinkedList
Doubly-linked list implementation of the List and Deque interfaces. >Implements all optional list operations, and permits all elements >(including null). …
list 인터페이스 구현 클래스 는 여러 개의 null / / TODO 를 추가 할 수 있 습 니 다.
문서 주석 에서 두 가지 중요 한 것 을 언급 했다.

1. 이 실현 은 동기 화 되 지 않 습 니 다. 동시 수정 작업 이 있 으 면 외부 에서 동기 화 되 어야 합 니 다 (예 를 들 어 List list = Collections. synchronized List (new LinkedList (...)

.

2. 교체 기 가 되 돌아 오 는 iterator and listIterator 는 fail - fast 입 니 다. 교체 기 를 만 든 후 교체 기 자체 가 실현 하 는 reove 나 add 방법 을 제외 한 모든 대상 에 게 하면 교체 기 는 Concurrent ModificationException 을 던 집 니 다. fail - fast 의 샘플 코드 와 분석 을 간단하게 보 여 줍 니 다.
따라서 병발 수정 에 직면 할 때 교체 기 는 앞으로 어떤 불확실 한 시간 에 임 의적 이 고 불확실 한 행위 의 위험 을 무릅 쓰 는 것 이 아니 라 빠 르 고 깨끗하게 실패 할 것 이다.
교체 기의 fail - fast 체 제 를 보장 할 수 없습니다. 일반적인 상황 에서 동기 화 되 지 않 은 병행 수정 이 존재 하 는 상황 에서 어떠한 하 드 보증 도 할 수 없 기 때 문 입 니 다.Fail - fast 교체 기 는 최선 을 다 한 토대 에서 Concurrent ModificationException 을 던 졌 다.따라서 이 이상 한 정확성 에 의존 하 는 프로그램 을 만 드 는 것 은 잘못 되 었 습 니 다. 교체 기의 빠 른 실패 행 위 는 오 류 를 검사 하 는 데 만 사용 되 어야 합 니 다.
상세 하 게 위의 견본 을 보십시오.

public class LinkedList<E> extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

그 가 계승 하고 실현 한 인 터 페 이 스 를 보면 이것 은 양 방향 대기 열 기능 을 포함 한 연속 링크 (계열 화, 복사) 이다.

get (int index) [위조 랜 덤 방문]

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

get (index) 방법 을 발견 할 수 있 습 니 다. 먼저 경 계 를 넘 었 는 지 판단 한 다음 node 로 돌아 갑 니 다.

node(int index)

  Node<E> node(int index) {
          // assert isElementIndex(index);
  
          if (index < (size >> 1)) {
              Node<E> x = first;
              for (int i = 0; i < index; i++)
                  x = x.next;
              return x;
          } else {
              Node<E> x = last;
              for (int i = size - 1; i > index; i--)
                  x = x.prev;
              return x;
          }
      }

무 작위 로 접근 하 는 방법 이 있 지만 실제로는 끊임없이 요 소 를 얻는다
순서 표
ArrayList
여기 서 오랫동안 생각 했다 ArrayList 왜 계승 AbstractList 또 실현 List 인터페이스 - > 점프 링크

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

이것 은 가 변 크기 의 List 구현 클래스 로 List 인터페이스 에서 의 조작 을 제외 하고 size 를 바 꾸 는 작업 도 제공 합 니 다.

//    10
private static final int DEFAULT_CAPACITY = 10;

//          
//1.new ArrayList(0);
//2.new ArrayList(collection);   collection.toArray().length=0
private static final Object[] EMPTY_ELEMENTDATA = {};

//     new ArrayList();
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//        
transient Object[] elementData; // non-private to simplify nested class access
//Arraylist  
private int size;

용량 확장 메커니즘
add 방법

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

빈 구조 기 생 성 여 부 를 판단 합 니 다. 그렇다면 minCapacity 를 업데이트 합 니 다.

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//         
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }//          10，  10   
    ensureExplicitCapacity(minCapacity);
}

용량 의 크기 가 충분 하도록 확보 해 야 지, 그렇지 않 으 면 용량 을 늘 려 야 한다.

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

먼저 용량 을 1.5 배 용량 크기 로 확대 한 다음 에 요구 에 도 달 했 는 지 판단 하고 요구 에 미 달 하면 다시 갱신 하 며 최대 용량 을 초과 하면 최대 용량 으로 설치한다.
그리고 원 배열 의 내용 을 모두 새로운 배열 로 복사 하고 element Data 를 업데이트 합 니 다.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList 와 같은 특징 은 스 레 드 가 안전 하지 않 고 iterator fast - fail 메커니즘 입 니 다.
(This class is roughly equivalent to Vector , except that it is unsynchronized.) Vector 와 달리 vector 의 확장 용량 은 2 배 입 니 다.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

창고.
stack - 후진 선 출
실제로 stack 은 Vector 를 계승 하여 스 택 작업 을 구현 할 수 있 는 5 가지 방법 을 실현 하 였 으 며, Vector 와 본질 적 으로 다 르 지 않 습 니 다.
그럼 Vector 와 Array List 가 어떻게 다른 지 직접 보 겠 습 니 다.
1. 스 레 드 안전
2. 확장 용량 이 다르다

elements 방법 은 ArrayList 에 없 는 것 이 고 elements 방법 은 fail - fast

가 아 닙 니 다.

public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;

            public boolean hasMoreElements() {
                return count < elementCount;
            }

            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }

이 방법 은 아마도 오래전 에 실 현 된 1.0, jdk 1.2 부터 iterator 가 있 었 고 Vector 는 초기 에 벡터 류 로 서 뒤에 실 현 된 List 인 터 페 이 스 였 다.
Vector 는 특별한 처리 와 병행 이 필요 하지 않 으 면 Array List 를 우선 사용 합 니 다.
대열
Queue – 먼저 나 가기
Queue 인터페이스 시 대기 열의 최상 위 인터페이스, 이 인터페이스의 실현 은 주로
1. Deque 양 방향 대기 열 2. BlockingQueue (JUC 패키지 중) 차단 대기 열
//TODO
해시 시계
HashMap
주석 을 직접 보다
인터페이스 구현 Map.null 값 과 null 키 를 허용 합 니 다.HashMap 와 Hashtable 는 일치 하지 않 는 것 을 제외 하고 null 을 허용 합 니 다.맵 의 순 서 를 장담 할 수 없고, 시간 에 따라 순서 가 변 하지 않 는 다 는 보장 도 없다.
용량 은 해시 표 의 통 수량 이 고 부하 인 자 는 해시 표 의 용량 이 자동 으로 증가 하기 전에 많이 담 을 수 있 는 도량 계수 이다.
해시 함수 가 원 소 를 표 에 정상적으로 분산 시 킬 수 있다 고 가정 하면 기본 적 인 작업 시간 은 상수 시간 이 걸 릴 것 이다.Map 의 교체 에 필요 한 시간 은 통 크기 와 키 값 이 수량 에 비례 하기 때문에 교체 기 를 사용 해 야 한다 면 부하 인 자 를 너무 높 거나 너무 낮 게 설정 하지 마 십시오.
확장 방면:
산 목록 에 있 는 항목 의 수량 이 부하 인자 와 용량 의 곱 을 초과 하면 해시 표 는 다시 산열 되 고 (내부 데이터 구조 가 재 구축 되 었 음) 해시 표 는 통 의 약 두 배 를 가지 게 된다.
기본 부하 인자 (0.75) 는 시간 과 공간 지출 에서 비교적 좋 은 평 가 를 얻 었 다.초기 용량 을 설정 할 때 예상 되 는 수량 과 부하 인 자 를 고려 하여 재 산열 횟수 를 최소 화해 야 한다.초기 용량 이 최대 항목 수 를 부하 인자 로 나 누 면 재 배열 작업 이 일어나 지 않 습 니 다.
만약 저장 한 수량 이 매우 많다 면, 충분 한 용량 을 만 드 는 것 은 그것 이 자동 으로 용량 을 늘 리 는 효율 보다 훨씬 클 것 이다.
여러 키 의 해시 값 hashCode 이 같 으 면 해시 표 의 기능 에 영향 을 줄 수 있 습 니 다.영향 을 낮 추기 위해 key 가 Comparable 일 때 이 종 류 는 key 간 의 비교 순 서 를 사용 하여 깨 뜨 릴 수 있다.
멤버 변수 다시 보기.

	//           。         。
     //     ，    2  
     //    0，                  
    transient Node<K,V>[] table;

    //     entrySet，AbstractMap      keySet  values   
    transient Set<Map.Entry<K,V>> entrySet;

    //       （        ）
    transient int size;

    //    ，   fail-fast
    transient int modCount;

     //             （  *    ）
     //         ，            ，          ；
    int threshold;//  

    //    
    final float loadFactor;

몇 가지 중요 한 지표

	//        16                      //   2  
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    //    。
	//                     ，       。
	//   2  <=1<<30。
    static final int MAXIMUM_CAPACITY = 1 << 30;

    //              ，          （0.75）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //                   。（        ）
    //              ，        。
    //                      ，              8。
    static final int TREEIFY_THRESHOLD = 8;

    //                  （        ）
	//                ，          ，     6
    static final int UNTREEIFY_THRESHOLD = 6;

    //              （                     ）
    //                 ，        4 * TREEIFY_THRESHOLD 
    static final int MIN_TREEIFY_CAPACITY = 64;

hash 알고리즘, key 의 hash 코드 가 다 르 거나 hash 코드 가 16 비트 낮 습 니 다. 왜 이렇게 소스 코드 주석 을 하 는 지 잘 알 고 있 습 니 다 - > hash 계산 주석
또한 hashCode 를 덮어 쓰 는 방법 중 하 나 를 설명 합 니 다. - > 왜 HashMap 은 equals 와 hashCode 를 덮어 써 야 합 니까?

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

저장 key

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)//            0
        n = (tab = resize()).length;					//     
    if ((p = tab[i = (n - 1) & hash]) == null)		//*1*
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> 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<K,V>)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. 여기 서 HashMap 저장 key 방식 을 설명 한다.
키 의 hash 코드 와 표 의 길이 - 1 과 결 과 를 키 가 표 에 있 는 위치 로 가 져 옵 니 다.(즉, hash 값 의 낮은 몇 자 리 를 key 로 하 는 위치)
그 다음 에 어떻게 삽입 하 는 과정 입 니까? - > HashMap 삽입 하 는 몇 가지 방법 입 니 다.
그리고 표 키 값 이 수량 에 한도 값 에 도달 하면 표를 다시 조정 합 니 다.
LinkedHashMap
//TODO