자바 에서 Array List 류 의 소스 코드 분석

앞에서 우리 가 언급 한 데이터 구조의선형 표.그러면 오늘 우 리 는 자바 소스 코드 가 어떻게 선형 표를 실현 하 는 지 상세 하 게 살 펴 보 겠 습 니 다.이 편 은 주로 순서 표 Array List 체인 표 다음 편 에서 언급 하고 있 습 니 다.
1:ArrayList 구성 도

2:Collection 과 List 의 차이 점
가장 좋 은 비 교 는 그들의 소스 코드 를 보 는 것 이다.우 리 는 Collection 의 모든 인 터 페 이 스 를 먼저 본다.

public interface Collection<E> extends Iterable<E> {
 int size();
 boolean contains(Object o);
 Iterator<E> iterator();
 Object[] toArray();
 <T> T[] toArray(T[] a);
 boolean add(E e);
 boolean remove(Object o);
 boolean containsAll(Collection<?> c);
 boolean addAll(Collection<? extends E> c);
 boolean retainAll(Collection<?> c);
 void clear(); 
 boolean equals(Object o);
 int hashCode();
}

List 인터페이스 보고 있어 요.

public interface List<E> extends Collection<E> { 
 int size();
 boolean isEmpty();
 Iterator<E> iterator();
 Object[] toArray();
 <T> T[] toArray(T[] a);
 boolean add(E e);
 boolean remove(Object o);
 boolean containsAll(Collection<?> c);
 boolean addAll(Collection<? extends E> c);
 boolean addAll(int index, Collection<? extends E> c);
 boolean removeAll(Collection<?> c);
 boolean retainAll(Collection<?> c);
 void clear();
 boolean equals(Object o);
 int hashCode();
 E get(int index);
 E set(int index, E element);
 void add(int index, E element);
 E remove(int index);
 int indexOf(Object o); 
 int lastIndexOf(Object o);
 ListIterator<E> listIterator();
 ListIterator<E> listIterator(int index);
 List<E> subList(int fromIndex, int toIndex);
}

List 는 Collection 을 계승 하 는 것 이기 때문에 모든 Collection 의 모든 기능 을 가지 고 있 습 니 다.Collection 인터페이스 에서 볼 수 있 듯 이 Collection 은 색인 이 없고 요소 의 값 을 가 져 올 수 없습니다.List 는 색인 을 가 집 니 다.그러면 요 소 를 가 져 오 는 데 있어 Collection 보다 훨씬 좋 습 니 다.
3:Iterable 인터페이스
Array List 에서 알 수 있 듯 이 맨 위 에 있 는 인 터 페 이 스 는 Iterable 이라는 인터페이스 입 니 다.이것 은 교체 기 입 니 다.인 터 페 이 스 는 다음 과 같 습 니 다.

public interface Iterable<T> {
 Iterator<T> iterator();
}

이 인 터 페 이 스 는 주로 대상 을 되 돌려 줍 니 다.이 대상 은 Iterator 입 니 다.그러면 Iterator 인터페이스 안의 방법 을 살 펴 보 겠 습 니 다.

public interface Iterator<E> {
 boolean hasNext();
 E next();
 void remove();
}

그러면 우 리 는 주로 Array List 가 어떻게 교체 기 Iterator 를 실현 하 는 지 를 본다.Iterator 의 실현 은 AbstractList 라 는 추상 적 인 클래스 의 개인 클래스 Itr 에 있 습 니 다.구체 적 으로 실현 되 는 것 을 봅 시다.

private class Itr implements Iterator<E> {
 int cursor = 0;
 int lastRet = -1;
 int expectedModCount = modCount;
 public boolean hasNext() {
  return cursor != size();
 }

cursor:색인 을 호출 할 위 치 를 기록 합 니 다.
lastRet:마지막 요소 의 색인
int expectedModCount = modCount;목적 은 modCount 를 검증 하기 위해 서 입 니 다.
이 집합 에 마지막 요소 가 존재 하 는 지 판단 합 니 다.cursor 를 통 해!=size();size 는 배열 의 길 이 를 표시 합 니 다.배열 의 요소 색인 이 0 에서 시작 되 기 때문에 마지막 색인 이 배열 의 길이 와 같 을 때 배열 의 끝 에 이 르 렀 음 을 설명 합 니 다.

public E next() {
  checkForComodification();
 try {
 E next = get(cursor);
 lastRet = cursor++;
 return next;
 } catch (IndexOutOfBoundsException e) {
 checkForComodification();
 throw new NoSuchElementException();
 }
 }

final void checkForComodification() {
 if (modCount != expectedModCount)
 throw new ConcurrentModificationException();
 }

modCount:모든 배열 의 데이터 구조 변동 횟수 를 기록 합 니 다.추가,삭제,변경 등 을 포함 합 니 다.동시 다발 을 피하 기 위해 여러 스 레 드 가 동시에 작 동 할 때 특정한 스 레 드 는 배열 구 조 를 수 정 했 고 다른 스 레 드 는 이 배열 을 읽 었 습 니 다.그러면 오류 가 발생 할 수 있 습 니 다.그래서 이 코드 에 modCount 를 넣 었 습 니 다!=expected ModCount,예 를 들 어 A 스 레 드 가 데이터 구 조 를 한 번 수정 하면 modCount 는+1 이 고 expected ModCount 는 변화 가 없 기 때문에 이상 을 던 집 니 다.

public void remove() {
 if (lastRet == -1)
 throw new IllegalStateException();
  checkForComodification();
 try {
 AbstractList.this.remove(lastRet);
 if (lastRet < cursor)
  cursor--;
 lastRet = -1;
 expectedModCount = modCount;
 } catch (IndexOutOfBoundsException e) {
 throw new ConcurrentModificationException();
 }
 }

방금 lastRet 에 기 록 된 것 이 마지막 요소 라 고 말 했 기 때문에 삭제 할 때 색인 에 따라 삭제 하면 됩 니 다.modCount 가 1 을 줄 이기 때문에 expected ModCount 를 다시 할당 하여 옮 겨 다 닐 때 오류 가 발생 하지 않도록 합 니 다.그리고 lastRed 를 차 부 초기 값 으로 합 니 다.
4:분석 ArrayList
방금 목적 은 ArrayList 를 더욱 연결 하기 위해 서 였 습 니 다.ArrayList 는 우리 가 예전 에 데이터 구조 에서 언급 한 순서 표 와 마찬가지 로 Object[]배열 로 요 소 를 저장 하고 size 로 요소 의 개 수 를 기록 하 는 것 입 니 다.

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer.
 */
 private transient Object[] elementData;
 /**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
 private int size;

transient 에 대해 변수 가 transient 에 의 해 수식 되면 변 수 는 더 이상 대상 의 지속 적 인 일부분 이 아 닙 니 다.그러면 왜 transient 수식 을 사용 합 니까?element Data 자체 가 캐 시 배열 이기 때문에 보통 용량 을 미리 남 겨 두 고 용량 이 부족 할 때 확장 합 니 다.예 를 들 어 현재 element Data 용량 은 10 이지 만 5 개의 요소 만 있 습 니 다.배열 의 마지막 다섯 가지 요 소 는 실제 적 인 의미 가 없고 저장 할 필요 가 없 기 때문에 Array List 의 디자이너 는 element Data 를 transient 로 설계 한 다음 에 writeObject 방법 에서 수 동 으로 직렬 화 시 키 고 전체 배열 이 아 닌 실제 저 장 된 요소 만 직렬 화 시 켰 다.writeObject 방법 을 볼 게 요.

private void writeObject(java.io.ObjectOutputStream s)
 throws java.io.IOException{
 // Write out element count, and any hidden stuff
 int expectedModCount = modCount;
 s.defaultWriteObject();
 // Write out array length
 s.writeInt(elementData.length);
 // Write out all elements in the proper order.
 for (int i=0; i<size; i++)
  s.writeObject(elementData[i]);
 if (modCount != expectedModCount) {
  throw new ConcurrentModificationException();
 }
 }

Array List 초기 화Array List 의 디자이너 는 세 가지 방식 으로 초기 화 합 니 다.(기본 배열 용량 은 10)

public ArrayList(int initialCapacity) {
 super();
 if (initialCapacity < 0)
  throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
 this.elementData = new Object[initialCapacity];
 }
 public ArrayList() {
 this(10);
 }
 public ArrayList(Collection<? extends E> c) {
 elementData = c.toArray();
 size = elementData.length;
 // c.toArray might (incorrectly) not return Object[] (see 6260652)
 if (elementData.getClass() != Object[].class)
 elementData = Arrays.copyOf(elementData, size, Object[].class);
 }

trimToSize 방법,이 방법 은 많은 사람들 이 적 게 사용 할 수 있 습 니 다.사실은 의미 가 매우 큽 니 다.주로 쓸모없는 용량 을 제거 합 니 다.그러면 메모리 의 비용 을 줄 일 수 있 습 니 다.

 public void trimToSize() {
 modCount++;
 int oldCapacity = elementData.length;
 if (size < oldCapacity) {
  elementData = Arrays.copyOf(elementData, size);
 }

ensureCapacity 방법 은 배열 이 가득 차 면 용량 을 늘 리 는 것 을 알 고 있 습 니 다.이 방법 은 용량 을 늘 리 는 것 입 니 다.

public void ensureCapacity(int minCapacity) {
 modCount++;
 int oldCapacity = elementData.length;
 if (minCapacity > oldCapacity) {
 Object oldData[] = elementData;
 int newCapacity = (oldCapacity * 3)/2 + 1;
  if (newCapacity < minCapacity)
 newCapacity = minCapacity;
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
 }

modCount 는 인 자 를 늘 리 고 배열 구 조 를 조작 하 는 횟수 를 기록 하 는 것 이다.먼저 용량 과 비교 하고 부족 하면 확대 하 는 것 이다.자바 1.6 버 전이 다.1.7>>1 을 사용 하면 모든 요소 가 오른쪽 에서 한 자 리 를 이동 한 다음 에 원래 의 용량 을 더 하 는 것 이다.그 속
index Of 방법,이 방법 은 요소 색인 을 가 져 오 는 것 입 니 다.색인 을 통 해 요 소 를 조회 합 니 다.

public int indexOf(Object o) {
 if (o == null) {
 for (int i = 0; i < size; i++)
 if (elementData[i]==null)
  return i;
 } else {
 for (int i = 0; i < size; i++)
 if (o.equals(elementData[i]))
  return i;
 }
 return -1;
 }

이 를 통 해 알 수 있 듯 이 Array List 는 null 의 삽입 을 지원 합 니 다.똑 같이 반복 해서 찾 는 것 을 사용 하 는데 시간 이 복잡 한 것 은 n 이다.
contains 방법,배열 에 어떤 요 소 를 포함 하 는 지 검증 하고 index Of 를 통 해 값 을 되 돌려 줍 니 다.

public boolean contains(Object o) {
 return indexOf(o) >= 0;
 }

lastIndex Of 방법 은 index Of 와 상대 적 으로 index Of 는 이동 한 후 lastIndex Of 는 뒤에서 다음 과 같이 찾 습 니 다.

public int lastIndexOf(Object o) {
 if (o == null) {
 for (int i = size-1; i >= 0; i--)
 if (elementData[i]==null)
  return i;
 } else {
 for (int i = size-1; i >= 0; i--)
 if (o.equals(elementData[i]))
  return i;
 }
 return -1;
 }

toArray 방법 은 List 를 배열 형식 으로 바 꾸 는 것 이다.

public Object[] toArray() {
 return Arrays.copyOf(elementData, size);
 }

get 과 set 방법,이 건 간단 합 니 다.여러분 이 보시 면 됩 니 다.

public E get(int index) {
 RangeCheck(index);
 return (E) elementData[index];
 }
 public E set(int index, E element) {
 RangeCheck(index);
 E oldValue = (E) elementData[index];
 elementData[index] = element;
 return oldValue;
 }

Range Check 방법 은 검 증 된 것 입 니 다.검색 한 색인 은 배열 의 길 이 를 다음 과 같이 초과 해 서 는 안 됩 니 다.

 private void RangeCheck(int index) {
 if (index >= size)
 throw new IndexOutOfBoundsException(
 "Index: "+index+", Size: "+size);
 }

add(E e)에 요 소 를 추가 합 니 다.이 요 소 는 꼬리 삽입 을 사용 하여 용량 을 먼저 검증 합 니 다.size+1 은 1 개의 요 소 를 추가 한 후에 길이 입 니 다.원래 배열 의 용량 이 충분 한 지 확인 합 니 다.

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

add(int index,E element)는 색인 에 따라 삽입 합 니 다.첫 번 째 는 똑 같이 확장 한 다음 색인 index 뒤의 요 소 를 모두 뒤로 이동 합 니 다.System.arraycopy(elementData, index, elementData, index + 1,
             size - index);element Data 의 제 index 요 소 를 제 index+1 개 요소 로 옮 기 고 길 이 는 size-index 라 는 뜻 이다.

public void add(int index, E element) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(
 "Index: "+index+", Size: "+size);
 ensureCapacity(size+1); // Increments modCount!!
 System.arraycopy(elementData, index, elementData, index + 1,
  size - index);
 elementData[index] = element;
 size++;
 }

addAll(Collection c)

public boolean addAll(Collection<? extends E> c) {
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacity(size + numNew); // Increments modCount
 System.arraycopy(a, 0, elementData, size, numNew);
 size += numNew;
 return numNew != 0;
 }

먼저 집합 c 를 a 배열 로 변환 한 다음 에 추가 할 배열 의 길 이 를 계산 하고 다른 기본 은 추가 요소 와 일치 합 니 다.arraycopy(Object src, int srcPos,Object dest, int destPos,int length)
매개 변수 횟수 는 순서대로 소스 배열,소스 배열 의 시작 위치,목표 배열,목표 배열 의 시작 위치,배열 요소 의 수 를 복사 합 니 다.
addAll(int index, Collectionc)배열 을 지정 한 위치 에 삽입 합 니 다.

public boolean addAll(int index, Collection<? extends E> c) {
 if (index > size || index < 0)
 throw new IndexOutOfBoundsException(
 "Index: " + index + ", Size: " + size);
 Object[] a = c.toArray();
 int numNew = a.length;
 ensureCapacity(size + numNew); // Increments modCount
 int numMoved = size - index;
 if (numMoved > 0)
 System.arraycopy(elementData, index, elementData, index + numNew,
   numMoved);
 System.arraycopy(a, 0, elementData, index, numNew);
 size += numNew;
 return numNew != 0;
 }

먼저 경 계 를 넘 었 는 지 여 부 를 판단 한 다음 에 위의 기본 과 같이 확장 판단 을 한 다음 에 index 뒤의 값 을 옮 긴 다음 에 index 를 포함 한 공간 을 집합 a 에 삽입 하 는 것 이다.그래서 원 소 를 두 번 복사 합 니 다.
E remove(int index)는 add 와 상대 적 으로 이 요 소 를 삭제 한 다음 index 뒤의 요 소 를 앞으로 이동 합 니 다 size-index-1 그 중에서-1 은 index 라 는 요소 가 삭제 되 고 한 요소 가 빠 지기 때 문 입 니 다.

public E remove(int index) {
 RangeCheck(index);
 modCount++;
 E oldValue = (E) elementData[index];
 int numMoved = size - index - 1;
 if (numMoved > 0)
 System.arraycopy(elementData, index+1, elementData, index,
   numMoved);
 elementData[--size] = null; // Let gc do its work
 return oldValue;
 }

remove(Object o)이것 은 선진 적 인 검증 이 필요 합 니 다.그리고 이 요소 의 위 치 를 찾 아서 삭제 합 니 다.

public boolean remove(Object o) {
 if (o == null) {
  for (int index = 0; index < size; index++)
 if (elementData[index] == null) {
  fastRemove(index);
  return true;
 }
 } else {
 for (int index = 0; index < size; index++)
 if (o.equals(elementData[index])) {
  fastRemove(index);
  return true;
 }
 }
 return false;
 }

private void fastRemove(int index) {
 modCount++;
 int numMoved = size - index - 1;
 if (numMoved > 0)
  System.arraycopy(elementData, index+1, elementData, index,
    numMoved);
 elementData[--size] = null; // Let gc do its work
 }

clear 는 모든 원 소 를 비 우 는 거 예요.

public void clear() {
 modCount++;
 // Let gc do its work
 for (int i = 0; i < size; i++)
 elementData[i] = null;
 size = 0;
 }

subList 방법,우 리 는 Array List 에 이런 방법 이 있다 는 것 을 알 고 있 습 니 다.Array List 소스 코드 는 존재 하지 않 습 니 다.AbstractList 를 계승 해서 왔 기 때 문 입 니 다.

 public List<E> subList(int fromIndex, int toIndex) {
 return (this instanceof RandomAccess ?
  new RandomAccessSubList<E>(this, fromIndex, toIndex) :
  new SubList<E>(this, fromIndex, toIndex));
 }

class SubList<E> extends AbstractList<E> {
 private AbstractList<E> l;
 private int offset;
 private int size;
 private int expectedModCount;
 SubList(AbstractList<E> list, int fromIndex, int toIndex) {
 if (fromIndex < 0)
  throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 if (toIndex > list.size())
  throw new IndexOutOfBoundsException("toIndex = " + toIndex);
 if (fromIndex > toIndex)
  throw new IllegalArgumentException("fromIndex(" + fromIndex +
      ") > toIndex(" + toIndex + ")");
 l = list;
 offset = fromIndex;
 size = toIndex - fromIndex;
 expectedModCount = l.modCount;
 }

코드 에서 우 리 는 이 기본 적 인 내부 류 의 실현 을 알 수 있다.subList 는 List 중의 한 단락 의 데이터 일 뿐이다.하지만 subList 에 대해 서 는 몇 가지 사항 을 주의해 야 합 니 다.
첫째:만약 에 우리 가 List 의 수 치 를 바 꾸 면 당신 이 얻 은 subList 의 값 도 이에 따라 달라 집 니 다.이 유 는 다음 과 같 습 니 다.

 public E get(int index) {
 rangeCheck(index);
 checkForComodification();
 return l.get(index+offset);
 }

이전 List 의 데 이 터 를 가 져 왔 기 때 문 입 니 다.마찬가지 로 subList 가 가 져 온 수 치 를 수정 하면 List 도 변 합 니 다.
둘째:List 구 조 를 바 꾸 면 subList 를 사용 할 수 없습니다.이러한 수정 은 원래 의 list 를 바탕 으로 하기 때문에 그들 은 공동으로 list 배열 을 사용 합 니 다.

public void add(int index, E element) {
 if (index<0 || index>size)
  throw new IndexOutOfBoundsException();
 checkForComodification();
 l.add(index+offset, element);
 expectedModCount = l.modCount;
 size++;
 modCount++;
 }

5:list 삭제 오류 분석
list 는 순환 삭 제 를 사용 할 때 Concurrent ModificationException 이상 을 보고 합 니 다.그러면 구체 적 인 원인 을 살 펴 보고 코드 를 먼저 보 겠 습 니 다.

List<String> list = new ArrayList<String>();
 list.add("a");
 list.add("b");
 list.add("c");
 list.add("d");
 list.add("e");
 for (String str:list){
  list.remove(str);
 }

foreach 가 옮 겨 다 니 기 때문에 최종 적 으로 for(Iterator it=iterator;iterators.hasNext();)모드 는 요 소 를 가 져 올 때 반드시 교체 기 에 있 는 next 방법 을 사용 합 니 다.next 방법 은 앞에서 말 했 듯 이 if(modCount!=expected ModCount)throw new Concurrent ModificationException()검증.remove(T x)방법 을 호출 할 때 modCount 가+1 이 되 기 때문에 두 번 의 비교 가 일치 하지 않 습 니 다.
정확 한 표기 법 은 아래 와 같다.

 Iterator iterator=list.iterator();
 while (iterator.hasNext()){
  iterator.next();
  iterator.remove();
 }

왜 교체 기 에서 remove 하면 되 는 거 죠?reove 코드 에 expected ModCount=modCount 라 는 코드 가 있 기 때 문 입 니 다.
6:Array List 는 라인 이 안전 합 니까
스 레 드 가 안전 하지 않 은 것 은 여러 스 레 드 를 동시에 조작 하여 더러 운 읽 기,오독 상황 을 초래 하 는 것 을 말 합 니 다.분명 한 ArrayList 는 비 스 레 드 가 안전 합 니 다.예 를 들 어 ArrayList 는 현재 하나의 값 만 있 고 A,B2 개의 스 레 드 가 동시에 이 값 을 삭제 하면 A 스 레 드 는 size=1 을 판단 할 수 있 습 니 다.이때 시간 부분 에서 CPU 가 B 스 레 드 를 호출 하여 size 도 1 을 발견 하고 삭제 작업 을 시작 합 니 다.그리고 A 는 계속 진행 합 니 다.추가 등등.그러나 Vector 는 스 레 드 가 안전 합 니 다.그 안에 모든 방법 이 synchronized 를 추 가 했 기 때문에 모든 스 레 드 가 Array List 방법 을 실행 할 때 까지 기 다 려 야 동기 화 자 물 쇠 를 가 져 올 때 까지 계속 진행 할 수 있 습 니 다.그러면 성능 이 크게 떨 어 집 니 다.
이상 은 본 고의 모든 내용 입 니 다.본 고의 내용 이 여러분 의 학습 이나 업무 에 어느 정도 도움 이 되 기 를 바 랍 니 다.또한 저 희 를 많이 지지 해 주시 기 바 랍 니 다!