Array List, Array List 에 대해 알 고 싶 은 모든 것 에 정통 합 니 다.
Array List, Array List 에 대해 알 고 싶 은 모든 것 에 정통 합 니 다.
ArrayList
머리말
자바 개발 에서 Array List 는 가장 자주 사용 하 는 데이터 구조 중 하나 로 데이터 목록 을 저장 합 니 다.ArrayList 대상 을 초기 화 한 후에 우 리 는 그것 이 제공 하 는 여러 가지 방법 을 사용 할 수 있 습 니 다. 삽입, 지정 한 위치 삽입, 대량 삽입, 획득, 삭제, 비 공 판단, 저장량 획득 등 입 니 다.
비록 우 리 는 모두 능숙 하 게 사용 하지만, 이러한 의문 이 있 었 습 니까? Array List 는 내 가 add () 에 들 어간 데 이 터 를 어떻게 저장 합 니까?내 가 new Array List 대상 이 었 을 때, 그 는 얼마나 큰 용량 이 었 습 니까?용량 이 10 인 Array List 를 초기 화 했 는데 11 개의 요 소 를 삽입 할 수 있 습 니 다. 어떻게 확장 할 수 있 습 니까?다음은 Array List 소스 코드 에서 이 문제 들 을 볼 것 입 니 다.
ArrayList 내부 구조 및 상용 방법 구현
Array List 는 배열 기반 저장 소 입 니 다.ArrayList 소스 코드 를 열 면 다음 변수 가 있 습 니 다.
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData;
변수의 설명 은 이 배열 은 ArrayList 요 소 를 저장 하 는 데 사 용 됩 니 다. 배열 의 길 이 는 ArrayList 의 용량 입 니 다.빈 Array List 의 element Data 는 빈 배열 입 니 다. 데 이 터 를 처음 추가 할 때 용량 이 DEFAULT 로 확 대 됩 니 다.CAPACITY (즉 10).
실례 화 방법
Array List 는 두 가지 실례 화 방법 이 있 는데 구조 함수 라 고도 부른다.무 참 실례 화 방법 코드 는 다음 과 같다.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
이 실례 화 방법 은 매우 간단 하 다. 사실은 요 소 를 저장 하 는 배열 element Data 에 값 을 부여 하 는 것 이다. 빈 Object 배열 이다.
참조 가 있 는 실례 화 방법 은 다음 과 같다.
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
방법 수신 매개 변수 initialCapacity 는 element Data 의 길 이 를 초기 화 하 는 것 으로 이 수가 0 포 이상 보다 적 으 면 0 결과 와 무 참 구조 함수 와 같 습 니 다.
요소 추가 add () 방법
추가 방법 은 두 가지 가 있 습 니 다. 하 나 는 보통 삽입 이 고 하 나 는 지정 한 위치 삽입 입 니 다.일반 방법 코드 는 다음 과 같 습 니 다.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
방법 첫 줄 은 용량 과 관련 된 것 이 므 로 아래 에 상세 하 게 분석 하 겠 습 니 다.여기 서 두 번 째 줄 을 봅 니 다. 요 소 를 추가 하 는 것 은 목표 요소 e 를 배열 element Data 의 size 아래 에 넣 는 것 입 니 다.동시에 size 에 1 을 추가 합 니 다.아래 에서 지정 한 위치 삽입 보기:
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}
방법 은 두 개의 인 자 를 받 습 니 다: index - 위치 삽입, element - 목표 요소.첫 번 째 줄 은 삽입 위치 가 합 리 적 인지 확인 합 니 다 (0 < index
list 에 A, B, C, D, E5 자 모 를 저장 했다 고 가정 하고 현재 add (3, "F") 를 호출 하여 F 를 삽입 합 니 다. System. arraycopy 를 호출 하여 위 치 를 바 꾼 후 설명 도 는 다음 과 같 습 니 다.
A
B
C
D
E
A
B
C
D
E
그리고 elementData [3] = "F" 를 실행 합 니 다. 전체 과정 | 원본 | A | B | C | D | E | | | |: |: |: -- |:: |: --: |:: |:: |:: | |:: | | 위치 | A | B | C | E | | 삽입 | A | B | C | F | D | E |
get () 방법
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
get 방법 첫 줄 에서 index 가 합 법 적 인지 확인 합 니 다. 예 를 들 어 get (- 1) 을 할 수 없 을 것 입 니 다. 그리고 element Data 배열 의 index 아래 표 시 된 요 소 를 꺼 냅 니 다.
원소 제거
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove 방법 은 element Data 에서 index 에 있 는 요 소 를 제거 하고 이 요 소 를 되 돌려 줍 니 다. numMoved 는 변위 가 필요 한 요소 의 개수 입 니 다. 그리고 변위 를 호출 합 니 다. 그리고 마지막 요 소 를 제거 합 니 다.
어떻게 확 대 했 어 요?
위 에서 보 듯 이 add () 방법 중 에 ensureCapacity Internal () 방법 이 있 습 니 다. 이 방법 은 실제 적 으로 확장 작업 을 완 료 했 습 니 다. 확장 작업 은 두 부분 으로 나 뉘 어 있 습 니 다. 1. 최소 용량 의 값 을 확인 합 니 다. (현재 요 소 를 삽입 하기 위해 용량 이 도달 할 값)
이 최소 용량 값 은 minCapacity 변수 입 니 다. 현재 element Data 배열 이 비어 있 으 면 minCapacity = 10 입 니 다. 그렇지 않 으 면 minCapacity = size + 1;
minCapacity 가 10 보다 작 으 면 10 을 가 져 옵 니 다. minCapacity 가 element Data 의 길이 보다 크 면 grow () 방법 으로 확장 합 니 다.
2. grow () 방법 을 호출 하고 grow () 방법 은 다음 과 같다.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//1.5
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);
}
이 방법 은 element Data 배열 의 새로운 용량 을 확인 하고 Arrays. copy Of 를 호출 하여 확장 을 완료 합 니 다. 새 용량 이 이 세 가지 수 치 를 기반 으로 하 는 지 확인 합 니 다.
그래서 확장 이 필요 할 때마다 원래 의 1.5 배, 최대 Integer. MAX VALUE 를 초과 하지 않 는 다 고 대충 이해 할 수 있다.
서열 화 된 문제
앞에서 언급 했 듯 이 Array List 는 배열 을 바탕 으로 하 는 것 입 니 다. 데 이 터 를 저장 하 는 것 은 배열 형식 구성원 변수 에 두 는 것 입 니 다. 즉, 이것 입 니 다.
transient Object[] elementData;
이 변 수 는 transient 로 수 정 됩 니 다. transient 키워드 의 역할 은 다음 과 같 습 니 다.
transient 로 인 스 턴 스 변 수 를 설명 하면 대상 이 저장 할 때 값 을 유지 할 필요 가 없습니다. 다시 말 하면 transient 키워드 로 표 시 된 구성원 변 수 는 직렬 화 과정 에 참여 하지 않 습 니 다.
배열 요소 가 직렬 화 에 참여 하지 않 는 것 은 아 닐 까? 내 가 힘 들 게 add 에 추가 한 데 이 터 는 없 는 것 이 아 닐 까? 그러나 실제 상황 은 그렇지 않다.
Array List 는 writeObject () 와 readObject () 방법 을 실 현 했 습 니 다. 직렬 화 와 반 직렬 화 를 맞 춘 것 과 같 습 니 다. element Data 변 수 는 transient 로 수식 되 었 지만 실제 element Data 의 요 소 는 직렬 화 될 때 기록 되 었 습 니 다. 방법 은 다음 과 같 습 니 다.
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 size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i
왜 그 랬 을 까? 앞에서 말 했 듯 이 Array List 는 동적 확장 이기 때문에 하나의 array List 가 10 개의 용량 을 가지 고 있 을 때 실제 적 으로 하나의 요소 만 저장 되 어 있 을 수 있다. 즉, size = 1 이 고 element Data. length = 10 이다. 이 럴 때 element Data 를 서열 화하 여 무엇 을 할 까? 뒤쪽 은 모두 빈 값 이다.
스 레 드 보안 문제
ArrayList 는 스 레 드 가 안전 하지 않 습 니 다. 따라서 다 중 스 레 드 환경 에서 오류 가 발생 하기 쉽 습 니 다. 다음 예 에서 20 개의 스 레 드 를 시작 합 니 다. 각 스 레 드 는 공 유 된 ArrayList 에 20 개의 요 소 를 삽입 하여 ArrayList 의 길 이 를 출력 합 니 다. ArrayList 가 스 레 드 가 안전 하 다 면 최종 결 과 는 200 이 어야 합 니 다.
public class Test {
public static void main(String[] args)throws Exception {
ArrayList list = new ArrayList<>();
final CyclicBarrier cb=new CyclicBarrier(20);
final CountDownLatch latch=new CountDownLatch(20);
for(int i=0;i<20;i++){
Thread t1 = new Thread(()->{
try{
long cur = System.nanoTime();
Thread.sleep(100);
System.out.println(cur+" ");
cb.await();
for(int j=0;j<20;j++){
list.add(j);
}
System.out.println(cur+" ");
latch.countDown();
}catch (InterruptedException |BrokenBarrierException e){
e.printStackTrace();
}
});
t1.start();
}
latch.await();
System.out.println(" :"+list.size());
}
}
나 는 마음대로 한 번 집행 하여 다음 과 같은 결 과 를 얻 었 다.
339278509731 준 비 됐 습 니 다 339278550899613 준 비 됐 습 니 다 339278550816171 준 비 됐 습 니 다 3392785506322 준 비 됐 습 니 다 339278550595294 준 비 됐 습 니 다 3392785150751470 준 비 됐 습 니 다 3392785116680 준 비 됐 습 니 다 33927851239628 준 비 됐 습 니 다 33927851821046 준 비 됐 습 니 다 33927851959373 준 비 됐 습 니 다 33927851351182 준 비 됐 습 니 다 33927851887532 준 비 됐 습 니 다 33927855107067 준 비 됐 습 니 다.33927852538799 준 비 됐 습 니 다 33927851433286 준 비 됐 습 니 다 339277852370336 준 비 됐 습 니 다 339277852448424 준 비 됐 습 니 다 339277852126703 준 비 됐 습 니 다 3392752215500 준 비 됐 습 니 다 339277852281986 준 비 됐 습 니 다 33927522821986 집행 완료 339278550979931 집행 완료 33927850899613 집행 완료 339278550816171 집행 완료 3392785506322 집행 완료 339278550595294 집행 완료완료 339278507511470 집행 완료 339278551168680 집행 완료 33927851239628 집행 완료 339278551821046 집행 완료 33927852370336 집행 완료 33927851433286 집행 완료 3392785520338799 집행 완료 33927851959373 집행 완료 33927855107067 집행 완료 3392785178577532 집행 완료 33927855215500 집행 완료 33927855135182 집행 완료완료 33927852448424 완료 배열 크기: 397
뚜렷 한 결과 와 맞지 않 습 니 다. 몇 번 더 실행 하면 배열 이 경 계 를 넘 는 것 을 발견 할 수 있 습 니 다. 그래서 Array List 는 스 레 드 가 안전 하지 않 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.