면접 & 필기시험 | ArrayList, 정복 (흔 한 면접 요약 첨부)
25323 단어 면접&필기시험
ArrayList 프로필 (이하 특별한 설명 없 이 jdk 1.8 기반 분석)
Array List 는 자바 집합 (용기) 의 일원 으로 그 자체 의 데이터 구 조 는 배열 이 며, 배열 을 바탕 으로 하 는 가장 특색 있 는 것 은 주소 지정 이 빠 르 고 랜 덤 접근 을 지원 하 며, 링크 구조의 용 기 를 삭제 하 는 것 이 느리다 는 것 이다 (일반적인 상황 에서).Array List 의 초기 용량 은 10 입 니 다.로드 인자 (요소 개수 가 자체 용량 의 절반 에 이 르 면 확장) 는 0.5 이다.용량 증가: 0.5 배;첫 번 째 확장 후 길 이 는 15 입 니 다.(후속 적 인 확장 은 5 의 경우 직접 수정 을 버 리 고 jdk 1.7 이상 의 버 전 은 직접 원 용량 * 1.5, jdk 1.6 버 전 은 1.5 배 + 1)
ArrayList 계승 및 실현
(아이디어 개발 도 구 를 사용 하면 shift 키 를 두 번 눌 러 ArrayList 를 검색 하여 원본 코드 를 볼 수 있 습 니 다)
Array List 소스 에서 볼 수 있 습 니 다:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Array List 는 먼저 E 유형의 범 형 을 밝 혔 고 AbstractList 추상 류 를 계승 하여 List 를 실현 했다.이것 은 추가, 삭제, 수정, 옮 겨 다 니 기 등 기능 을 제공 하 는 배열 대기 열 입 니 다.
ArrayList 는 RandomAccess 인 터 페 이 스 를 실현 했다. RandomAccess 는 빠 른 랜 덤 접근 을 지원 하 는 표지 인터페이스 이다.
ArrayList 는 함수 clone () 을 덮어 복제 할 수 있 는 Cloneable 인 터 페 이 스 를 실현 했다.
ArrayList 가 Serializable 인 터 페 이 스 를 실현 하 는 것 은 ArrayList 가 직렬 화 를 지원 하고 원 격 전송 이 가능 하 다 는 것 을 의미한다.
원본 코드 에서 정 의 된 구성원 변수:
/**
*
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* （ ）。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
// ， EMPTY_ELEMENTDATA ， 。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*
*/
transient Object[] elementData;
/**
* ArrayList
*/
private int size;
ArrayList 확장
/**
*
* @param e
* @return
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
/**
*
* @param minCapacity
*/
private void ensureCapacityInternal(int minCapacity) {
//
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 10 ， ，
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* ，
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// ，
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* ， 1.5
* @param minCapacity
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// ， oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//
elementData = Arrays.copyOf(elementData, newCapacity);
}
ArrayList 핵심 확장 은 최종 적 으로 Arrays. copy Of () 방법 임 을 알 수 있 습 니 다. Arrays. copy Of () 방법 은 최종 적 으로 System. array copy () 방법 을 호출 하 는 것 입 니 다. System. array copy () 는 native (이 키워드 에 의 해 수식 되 고 C 언어 로 작 성 된 방법 임 을 표시 합 니 다. 이 방법 은 자바 가 C 에 대한 api) 수식, System. array copy () 와 Arrays. copy Of () 방법의 차이 로 이해 할 수 있 습 니 다.
(1) copy Of () 내부 에 배열 을 새로 만 들 고 이 배열 로 돌아 갑 니 다.
(2) array copy () 는 대상 배열 이 필요 합 니 다. 원 배열 을 사용자 정의 배열 로 복사 하려 면 복사 의 시작 점 과 길 이 를 선택해 야 합 니 다.
ArrayList 요소 추가, 삭제, 수정 (원본 코드 삭제 분석 을 예 로 들 면)
ArrayList 의 용량 크기 는 매번 변동 (추가 삭제) 이 발생 할 때마다 새로운 배열 을 복사 하고 용량 크기 를 재 조정 해 야 합 니 다 (용량 크기 에 대해 서 는 ArrayList 를 만 들 때 크기 가 지정 되 지 않 으 면 빈 배열 로 먼저 할당 합 니 다. 첫 번 째 요 소 를 추가 할 때 만 기본 용량 크기 10 으로 확 대 됩 니 다). 이런 점 에서또한 본 고 에서 처음에 말 한 링크 가 느 린 이유 이기 도 한다. 링크 는 인용 만 바 꾸 면 되 고 배열 구조의 용 기 는 용량 크기 를 재 조정 해 야 한다. 아래 Array List 가 삭제 한 소스 코드 는 바로 이 점 을 검증 한 것 이다.
/**
*
* @param index
* @return
*/
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);
// null GC
elementData[--size] = null;
return oldValue;
}
ArrayList 직렬 화 (writeObject () 와 readObject () 를 예 로 들 면)
Array List 는 배열 을 바탕 으로 이 루어 집 니 다. 로 딩 인자 0.5 를 통 해 알 수 있 듯 이 그 는 항상 절반 의 공간 을 남 겨 두 고 확장 을 준비 합 니 다. 그러면 직렬 화 과정 에서 이 절반 의 공간 을 우 리 는 그 를 직렬 화 할 필요 가 없 을 것 입 니 다.
요 소 를 저장 하 는 배열 element Data 는 transient 수식 을 사용 합 니 다. 이 키 워드 는 배열 이 기본적으로 정렬 되 지 않 습 니 다.
transient Object[] elementData;
ArrayList 는 직렬 화 할 때 writeObject () 방법 을 사용 하여 size 와 element 길이 의 요 소 를 Object OutputStream 에 기록 합 니 다.역 직렬 화 시 readObject () 를 호출 하여 Object InputStream 에서 size 와 element 길이 의 크기 요 소 를 가 져 온 다음 element Data 로 복원 합 니 다. 원본 코드 에서 알 수 있 듯 이 직렬 화 된 길 이 는 element. length 가 아 닌 size 입 니 다.
/**
*
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
// size
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// .
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
ArrayList 의 fail - fast 메커니즘
ArrayList 는 매번 삭제, 수정, 추가 과정 에서 하나의 전역 변 수 를 증가 시 킵 니 다. 이 변 수 는 modCount 입 니 다. 요소 의 수정 횟수 를 대표 합 니 다. 이 전역 변 수 는 AbstractList 류 에 정의 되 어 있 습 니 다. 직렬 화 또는 교체 등 작업 을 할 때 전후 modCount 가 바 뀌 었 는 지 비교 해 야 합 니 다.바 뀌 면 Concurrent ModificationException 을 던 져 야 합 니 다.
protected transient int modCount = 0;
면접 에서 자주 묻는다.
1. List, Vector, Set 와 Map 의 초기 용량 과 로드 인자?
답: 1. List Array List 의 초기 용량 은 10 입 니 다.로 딩 인자 0.5;용량 증가: 0.5 배;한 번 에 용량 을 늘 린 후 길 이 는 15 이다.(후속 확장 은 5 의 경우 jdk 1.7 이상 의 버 전 을 직접 원 용량 * 1.5, jdk 1.6 버 전 은 0.5 배 + 1) Vector 의 초기 용량 은 10 이 고 로드 인 자 는 1 입 니 다.확장 용량: 원 용량 의 1 배, 예 를 들 어 Vector 의 용량 은 10 이 고 한 번 확장 하면 용량 은 20 이다.
2. Set
HashSet, 초기 용량 은 16 이 고 로드 인 자 는 0.75 입 니 다.용량 증가: 원 용량 의 1 배;예 를 들 어 HashSet 의 용량 은 16 이 고 한 번 의 확장 후 용량 은 32 이다.
3. Map HashMap, 초기 용량 16, 로드 인 자 는 0.75;용량 증가: 원 용량 의 1 배;예 를 들 어 HashMap 의 용량 은 16 이 고 한 번 에 용량 을 확대 한 후 용량 은 32 이다.
2、ArrayList list = new ArrayList(20); 목록 을 몇 번 확장 합 니까?답: 0 회, 초기 값 지정, 기본 값 은 확장 용량 으로 초기 용량 10 과 관계 가 없습니다.
3. Array List list 와 LinkedList 에 비해 차이 점 은?답: 하나의 배열, 하나의 링크, 배열 의 주소 지정 이 빠 르 고 링크 의 삭제 가 빠르다 (일반적인 상황 에서 배열 의 끝 에 삭제 하면 배열 의 시간 은 링크 와 크게 다 르 지 않 으 며 배열 의 머리 와 중부 에 이동 배열 이 필요 하 다).
4. ArrayList 스 레 드 가 안전 합 니까?답: 비 스 레 드 보안
5. System. array copy () 와 Arrays. copy Of () 방법의 차이 점 은?답: (1) copy Of () 내부 에 배열 을 새로 만 들 고 이 배열 (2) array copy () 로 돌아 가 려 면 대상 배열 이 필요 합 니 다. 원 배열 을 사용자 정의 배열 로 복사 하려 면 복사 의 시작 점 과 길 이 를 선택해 야 합 니 다.
6. ArrayList 는 직렬 화 를 지원 합 니까?서열 화 과정?답: 지원 합 니 다. 실제 요소 만 정렬 하고 Object OutputStream 의 writeObject () 를 사용 하여 대상 을 바이트 흐름 으로 변환 하고 출력 합 니 다.한편, writeObject () 방법 은 들 어 오 는 대상 에 writeObject () 가 존재 할 때 이 대상 의 writeObject () 를 반사 적 으로 호출 하여 직렬 화 를 실현 합 니 다.역 직렬 화 는 Object InputStream 의 readObject () 방법 을 사용 합 니 다.
7. Array List 는 이러한 종 류 를 계승 하여 어떤 인 터 페 이 스 를 실현 합 니까?답: AbstractList, RandomAccess, Cloneable, Serializable
8. Array List 는 어떤 것들 이 있 습 니까?답: 기본 for 순환, Iterator 교체 기 옮 겨 다 니 기
9. ArrayList 를 만 들 때 용기 크기 를 알 고 있다 면 초기 화 용량 을 지정 하 는 것 을 추천 하 는 이 유 는 무엇 입 니까?(알 리 바 바 규범) 답: 용량 을 늘 리 는 횟수 를 줄 이 고 성능 을 향상 시킨다.
10. List, Set, Map 3 자의 차 이 를 말 해 볼 까요?답: (1) List 인 터 페 이 스 는 한 그룹 이 유일 하지 않 습 니 다 (여러 요소 가 같은 대상 을 참조 할 수 있 습 니 다). 질서 있 는 대상 (2) set 은 중복 되 는 집합 을 허용 하지 않 습 니 다.무질서 (3) 맵 키 쌍, key 중복 허용 되 지 않 습 니 다. value 는 참조 형식 을 저장 할 수 있 습 니 다.
11. Arraylist 와 LinkedList 의 차이 점 은?답: (1) 바 텀 데이터 구조 가 다 르 고 Array List 는 Object 배열 을 사용 합 니 다.LinkedList 바 텀 은 양 방향 링크 데이터 구조 (JDK 1.6 이전 에는 순환 링크 였 으 나 JDK 1.7 은 순환 을 취소 하 였 습 니 다. 양 방향 링크 와 양 방향 순환 링크 의 차이 점 에 주의 하 십시오) (2) Arraylist 는 효율 적 인 무 작위 요소 접근 을 지원 하 며 LinkedList 는 지원 하지 않 습 니 다.빠 른 무 작위 접근 은 요소 의 번 호 를 통 해 요소 대상 을 신속하게 가 져 오 는 것 (get (int index) 방법 에 대응) (3) ArrayList 는 배열 로 저장 되 기 때문에 요 소 를 삽입 하고 삭제 하 는 시간 복잡 도 는 요소 위치의 영향 을 받는다.예 를 들 어 add (E) 방법 을 실행 할 때 Array List 는 지정 한 요 소 를 이 목록 의 끝 에 추가 하 는 것 을 기본 으로 합 니 다. 이 경우 시간 복잡 도 는 O (1) 입 니 다.그러나 지정 한 위치 i 에 요 소 를 삽입 하고 삭제 하려 면 (add (int index, E element) 시간 복잡 도 는 O (n - i) 입 니 다.상기 작업 을 할 때 집합 에서 i 와 i 번 요소 다음 (n - i) 요 소 는 모두 뒤로 / 앞으로 한 자 리 를 옮 기 는 작업 을 수행 해 야 하기 때문에 링크 드 List 는 링크 로 저장 되 기 때문에 삽입 합 니 다. 요소 삭제 시간 복잡 도 는 요소 위치의 영향 을 받 지 않 고 모두 O (1) 와 가 깝 고 배열 은 O (n) 와 비슷 합 니 다.
12. Array List 가 실현 하 는 RandomAccess 인터페이스 에 대해 RandomAccess 인 터 페 이 스 를 실현 한 것 이 바로 무 작위 방문 능력 이 있다 는 것 을 설명 합 니까?왜?답: Array List 소스 코드 를 읽 어 보면 RandomAccess 인터페이스 가 비어 있 고 모든 것 이 정의 되 어 있다 는 것 을 알 수 있다. 이 는 RandomAccess 인 터 페 이 스 는 간단 한 표지 역할 일 뿐 RandomAccess 인터페이스 가 무 작위 로 방문 하 는 능력 을 표시 하 는 것 이 아니 라 배열 자체 가 지원 한 다 는 것 을 의미한다.Collections. binary Search 방법 에 들 어 오 는 집합 은 RandomAccess 인 터 페 이 스 를 실현 하 는 지 여 부 를 판단 하여 다른 방법 을 호출 합 니 다.
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
// RandomAccess
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
13. Array List 와 Vector 의 차 이 는?답: ArrayList 스 레 드 가 안전 하지 않 고 Vector 스 레 드 가 안전 하 며 ArrayList 의 초기 용량 은 10 입 니 다.로 딩 인자 0.5;용량 증가: 0.5 배;한 번 에 용량 을 늘 린 후 길 이 는 15 이다.Vector 의 초기 용량 은 10 이 고 로드 인 자 는 1 입 니 다.확장 용량: 원 용량 의 1 배, 예 를 들 어 Vector 의 용량 은 10 이 고 한 번 확장 하면 용량 은 20 이다.
14. Array List 에 Fail - Fast 가 있 나 요?Fail - Fast 의 원 리 를 말 해 볼 까요?답: 우리 가 일반적으로 말 하 는 자바 의 fail - fast 메커니즘 은 기본적으로 자바 집합 의 오류 검출 메커니즘 을 가리킨다.여러 개의 스 레 드 나 원래 용기 에서 직접 수정 할 때 이 보호 체 제 를 촉발 합 니 다. 이 메커니즘 의 원 리 는 두 개의 변수 가 촉발 되 는 것 입 니 다. modCount 와 expected ModCount 변 수 는 초기 값 이 0 입 니 다. 수정 (삭제 추가) 작업 으로 modCount 는 스스로 증가 하여 수정 되 고 있 음 을 나타 냅 니 다. 이때 스 레 드 가 수정 되면 expected ModCount 와 일치 하 는 지 여 부 를 판단 합 니 다.같 지 않 으 면 ConcurrentModificationException 이상 을 던 집 니 다. CopyOnWriteArray List 를 사용 하여 피 할 수 있 습 니 다. 구체 적 으로 보 세 요.
조심 하지 않 으 면 자바 개발 자 에 게 구 덩이 를 밟 히 는 fail - fast 는 어떤 귀신 입 니까?
15 、 Array List 를 손 으로 써 볼 까요?하하
ps: 집합 면접 자료 에 대해 저 는 뇌 도 를 정리 하고 관심 이 있 으 면 댓 글 구역 (비밀번호) 에서 다운로드 하여 볼 수 있 습 니 다. 문제 가 있 으 면 지적 을 환영 합 니 다. 초 전 집합 복습 뇌 도 링크
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
면접 & 필기시험 | ArrayList, 정복 (흔 한 면접 요약 첨부)Array List 는 자바 집합 (용기) 의 일원 으로 그 자체 의 데이터 구 조 는 배열 이 며, 배열 을 바탕 으로 하 는 가장 특색 있 는 것 은 주소 지정 이 빠 르 고 랜 덤 접근 을 지원 하 며, 링크 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
