데이터 구조 (순서 표) 의 응용 - ArrayList, Vector 분석
Array List 는 모두 가 이미 잘 알 고 있 을 것 이다. 그러나 우 리 는 밖에서 인 터 페 이 스 를 호출 할 뿐 어떤 사람들 은 그 내부 의 실현 원 리 를 모른다.나 도 예전 에 집합 을 만 났 을 때 모두 Array List 를 사 용 했 지만 그렇게 여러 번 사 용 했 지만 그것 에 대해 깊이 이해 하지 못 했다. 지금 우 리 는 함께 분석 하 자.
Array List 는 배열 을 바탕 으로 이 루어 진 것 이기 때문에 그 안에 많은 조작 이 배열 을 통 해 이 루어 집 니 다. 이것 은 동적 배열 로 그 용량 이 자동 으로 증가 할 수 있 습 니 다. C 언어 에서 의 동적 신청 메모리 와 비슷 하고 동적 성장 메모리 와 같 습 니 다.ArrayList 는 스 레 드 가 안전 한 것 이 아니 라 단일 스 레 드 환경 에서 만 사용 할 수 있 습 니 다. 다 중 스 레 드 환경 에서 Collections. synchronizedList (List l) 함수 로 스 레 드 가 안전 한 ArrayList 류 를 되 돌려 주 는 것 도 고려 할 수 있 습 니 다. concurrent 를 사용 하여 보 낸 CopyOnWrite ArrayList 류 도 사용 할 수 있 습 니 다.
(1) ArrayList 의 계승 관계 와 실현 인터페이스
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable
--------------------------------------------------------------------------------------------------
public abstract class AbstractList extends AbstractCollection implements List
--------------------------------------------------------------------------------------------------
public abstract class AbstractCollection implements Collection
Array List 를 통 해 알 수 있 듯 이 이것 은 범 형 을 지원 하 는 것 이다. Array List 는 AbstractList 를 계승 하고 AbstractList 는 AbstractCollection 을 계승 했다. AbstractCollection 은 Collection 인터페이스의 실현 류 로 그 안에 집합 하 는 유 니 버 설 인터페이스 가 봉인 되 어 있다.한편, AbstractList 는 List 인 터 페 이 스 를 실현 하 는 꼭대기 층 실현 류 라 고 할 수 있 고 그 중에서 도 List 인터페이스 가 Collection 에 대한 인 터 페 이 스 를 바탕 으로 하 는 확장 인 터 페 이 스 를 정의 했다.우리 가 일반적으로 사용 하 는 Array List 는 AbstractList 중의 하나 이다.
ArrayList 는 List 인 터 페 이 스 를 실현 하기 때문에 ArrayList 는 List 인터페이스 에 포 장 된 방법 을 실현 해 야 합 니 다.
Array List 는 RandomAccess 인 터 페 이 스 를 실현 하여 빠 른 랜 덤 접근 을 지원 합 니 다.
ArrayList 는 Cloneable 인 터 페 이 스 를 실현 하여 ArrayList 를 복제 할 수 있 도록 합 니 다.
자바. io. Serializable 인 터 페 이 스 를 통 해 직렬 화 기능 을 사용 합 니 다.이 인 터 페 이 스 를 실현 하지 않 은 클래스 는 그 어떠한 상태 도 직렬 화하 거나 반 직렬 화 할 수 없습니다.직렬 화 인 터 페 이 스 는 방법 이나 필드 가 없고 표지 의 직렬 화 된 의미 에 만 사용 된다.
(2) ArrayList 의 속성 필드
private static final int DEFAULT_CAPACITY = 10; //ArrayList
private static final Object[] EMPTY_ELEMENTDATA = {}; //
Array List 는 두 개의 속성 을 정 의 했 습 니 다. 어떻게 보면 이것 은 우리 의 순서 표 의 구조 가 아 닙 니까?그 중에서 transient 키워드 가 표시 하 는 필드 의 생명 주 기 는 호출 자의 메모리 에 만 존재 하 며 디스크 에 기록 되 지 않 습 니 다.
transient Object[] elementData; // ArrayList
private int size;
(3) ArrayList 의 구조 함수
(1) 초기 용량 을 가 진 구조 함수
public ArrayList(int initialCapacity) {
super(); // AbstractList
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity]; //
}
(2) 무 참 구조 함수
public ArrayList(){ // Api ， 10
super();
this.elementData = EMPTY_ELEMENTDATA;
}
(3) 무 참 구조 함수
// c
public ArrayList(Collection extends E> c){
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// ， c toArray ， bug
if(elementData.getClass() != Object[].class){
// copy ， Arrays
elementData = Arrays.copyOf(elementData,size,Object[].class);
}
}
(4) Array List 의 첨삭 검사
(1) 동작 추가
// e
public boolean add(E e) {
ensureCapacityInternal(size + 1); //
elementData[size++] = e;
return true;
}
// index e
public void add(int index,E e){
rangeCheckForAdd(index); // index
ensureCapacity(size+1);
// index （ ）
System.arraycopy(elementData,index,elementData,index+1,size-index); //
elementData[index] = e;
size++;
}
// c ArrayList
public boolean addAll(int index,Collection extends E> c){
rangeCheckForAdd(index);
Object[] o = c.toArray();
int numNew = o.length;
int numMoved = size - index; //
if(numMoved>0){
// index （ ） numNew
System.arraycopy(elementData,index,elementData,index+numNew,numMoved);
}
System.arraycopy(o,0,elementData,index,numNew);
size += numNew;
return numMoved != 0;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) { //
//
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity); //
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // List ， ArrayList ，
// overflow-conscious code
if (minCapacity - elementData.length > 0) // ，
grow(minCapacity); //
}
//ArrayList
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; //
int newCapacity = oldCapacity + (oldCapacity >> 1); // 3/2
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); // ， elementData ,
}
//MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError()；
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
private void rangeCheckForAdd(int index){
if(index<0 || index>size){
throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
}
(2) 삭제 작업
//
public E remove(int index){
rangeCheck(index); // Index
E oldValue = (E)elementData[index];
// ， index
int numMoved = size - index -1;
if(numMoved>0){
// index 1
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
// arraycopy ， ， ， null.
elementData[--size] = null;
return oldValue;
}
//
public boolean remove(Object o){
if(o == null){ // Null
for(int index=0;index 0){
System.arraycopy(elementData,index+1,elementData,index,numMoved);
}
elementData[--size] = null;
}
private void rangeCheck(int index){
if(index<0 || index>=size){
throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
}
}
(3) 조작 수정
public E set(int index,E e){
rangeCheck(index); //
E oldValue = (E)elementData[index];
elementData[index] = e; //
return oldValue;
}
(4) 조회 조작
public E get(int index){
rangeCheck(index);
E oldValue = (E)elementData[index];
return oldValue;
}
(5) ArrayList 가 정의 하 는 집합 방법 과 배열 의 다음 표 조회 방법
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
//
public void clear() {
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
}
}
//
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// ( )
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;
}
//
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;
}
이것들 이 바로 Array List 의 대략적인 것 입 니 다. 그리고 옮 겨 다 니 고 교체 기 를 분석 하지 않 았 습 니 다. 그러나 저 는 그것 이 가장 중요 한 것 이 아니 라 Array List 의 데이터 구조 와 삭제, 검사 작업 과 확장 체 제 를 이해 하 는 것 이 중요 하 다 고 생각 합 니 다.이것 도 면접 에서 직면 할 수 있 는 문제 이다. 그 실현 원 리 를 알 아야 우 리 는 면접 관 앞에서 유창 하 게 대답 하고 자신 을 향상 시 킬 수 있다.어떤 방법 은 한 버 전에 서 다 를 수 있 습 니 다. 저 는 안 드 로 이 드 SDK 의 소스 코드 로 분석 하고 있 습 니 다. 버 전이 데이터 구 조 를 바 꾸 지 않 는 한 실현 원 리 는 똑 같 습 니 다.Vector 에 대해 우 리 는 너무 깊이 연구 할 필요 가 없다. 왜냐하면 지금 은 거의 사용 할 수 없 기 때문이다.
(6) ArrayList 와 Vector 그리고 Vector 는 분석 하지 않 았 지만 Vector 의 실현 원 리 는 ArrayList 와 대체적으로 똑 같 습 니 다. 다만 Vector 는 첨삭 검사 등 작업 을 할 때 synchronized 키 워드 를 추가 하여 다 중 스 레 드 상황 에서 안전 합 니 다.
List 인터페이스 에서 모두 세 가지 유형 을 실현 했다. Array List, Vector, LinkedList.링크 드 리스트 는 더 이상 말 하지 않 겠 습 니 다. 데이터 의 삽입 순 서 를 유지 할 때 주로 사 용 됩 니 다.Array List 와 Vector 는 모두 배열 로 이 루어 진 것 으로 주로 세 가지 차이 가 있 습 니 다.
1. Vector 는 다 중 스 레 드 가 안전 하지만 Array List 는 그렇지 않 습 니 다. 이 는 소스 코드 에서 볼 수 있 듯 이 Vector 류 의 방법 은 synchronized 로 수식 되 기 때문에 Vector 는 효율 적 으로 Array List 와 비교 할 수 없습니다.
2. 두 가지 모두 선형 연속 공간 저장 요 소 를 사용 하지만 공간 이 부족 할 때 두 가지 유형의 증가 방식 이 다르다. 많은 네티즌 들 은 Vector 가 원래 공간의 배 를 증가 하고 Array List 가 원래 의 1.5 배 를 증가 했다 고 말한다.
//ArrayList
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);
}
// Vector ， ： 0， public Vector(int initialCapacity,int capacityIncrement) ， (oldCapacity+capacityIncrement)， ；
// ， (oldCapacity+oldCapacity)， 。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. Vector 는 성장 인 자 를 설정 할 수 있 지만 Array List 는 안 됩 니 다. 처음에 이것 을 볼 때 저 는 증 량 인자 가 무엇 인지 이해 하지 못 했 습 니 다. 그러나 두 개의 소스 코드 를 비교 해서 이 를 이 해 했 습 니 다. 먼저 두 가지 구조 방법 을 보 겠 습 니 다. Array List 는 세 가지 구조 방법 이 있 습 니 다.
public ArrayList(int initialCapacity)// 。
public ArrayList()// 10 。
public ArrayList(Collection extends E> c)// collection
Vector 는 네 가지 구조 방법 이 있 습 니 다.
public Vector()// 。
public Vector(int initialCapacity)// ， ， 。
public Vector(Collection extends E> c)// collection
public Vector(int initialCapacity,int capacityIncrement)//
(7) ArrayList 요약
(1) Array List 는 선형 표 의 순서 저장 구조의 순서 표 이다. 내부 유 지 는 하나의 배열 이 고 배열 은 연속 적 으로 주 소 를 저장 하 는 저장 블록 이기 때문이다.
(2) Array List 는 내부 유지 보수 가 하나의 배열 이기 때문에 조회 와 수정 효율 이 높 고 꼬리 부분 삽입 효율 도 높 지만 삽입 추가 와 삭제 의 효율 이 비교적 낮 고 성능 이 느 려 지 는 것 은 배열 의 copy 에 구체 적 으로 나타 나 며 특히 데이터 양 이 많은 경우 에 현저 해 야 한다.
(3) Array List 는 요 소 를 추가 할 때 null 요 소 를 추가 할 수 있 습 니 다.그러나 우 리 는 데 이 터 를 추가 할 때 데이터 에 대해 비 공 판단 을 하 는 것 이 좋 습 니 다. 그렇지 않 으 면 추출 한 데 이 터 는 사용 할 때 빈 지침 으로 분 별로 사람 이 되 는 것 을 가 르 칩 니 다.
(4) ArrayList 는 스 레 드 가 안전 하지 않 으 므 로 다 중 스 레 드 환경 에서 ArrayList 를 사용 하지 않도록 합 니 다.
나이 든 기사 에 게 부족 한 점 을 지적 해 주 십시오. 감사합니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
