[java] 초기 용량으로 ArrayList를 시작하는 이유는 무엇입니까?

나는 실제로 2 개월 전에 주제에 대한 블로그 게시물 을 썼습니다 . 이 기사는 C #에 대한 List<T>것이지만 Java의 ArrayList구현은 매우 유사합니다. ArrayList동적 배열을 사용하여 구현 되므로 필요에 따라 크기가 커집니다. 용량 생성자의 이유는 최적화를위한 것입니다.

이러한 크기 조정 작업 중 하나가 발생하면 ArrayList는 배열의 내용을 기존 배열의 용량의 두 배인 새 배열로 복사합니다. 이 작업은 O (n) 시간에 실행됩니다 .

예

다음은 ArrayList크기가 어떻게 증가 하는지에 대한 예입니다 .

10
16
25
38
58
... 17 resizes ...
198578
297868
446803
670205
1005308

따라서 목록의 용량은 1011 번째 항목이 추가 될 때로 증가 50% + 1합니다 16. 17 번째 항목에서 ArrayList가 다시 증가합니다 25. 이제 원하는 용량이 이미 알려진 목록을 작성하는 예를 고려하십시오 1000000. ArrayList크기 생성자를 사용하지 않고 생성하면 크기 조정시 O (1) 또는 O (n)ArrayList.add 1000000 이 걸리는 시간 이 호출됩니다 .

1000000 + 16 + 25 + … + 670205 + 1005308 = 4015851 연산

생성자를 사용하여 이것을 비교 한 다음 O (1)ArrayList.add 에서 실행되도록 보장하는 호출하십시오 .

1000000 + 1000000 = 2000000 연산

자바 대 C #

Java는 위와 같으며에서 시작하여 10각 크기를 조정 50% + 1합니다. C #은 시작될 4때마다 훨씬 더 적극적으로 증가하여 크기를 조정할 때마다 두 배가됩니다. 1000000C # 사용 3097084작업에 대한 위 의 추가 예제 .

참고 문헌

• C #의 List <T>에 대한 내 블로그 게시물
• 자바의 ArrayList 소스 코드

답변

ArrayList example = new ArrayList<Integer>(3);
example.add(1); // size() == 1
example.add(2); // size() == 2, 
example.add(2); // size() == 3, example has been 'filled'
example.add(3); // size() == 4, example has been 'expanded' so that the fourth element can be added. 

int newCapacity = (oldCapacity * 3)/2 + 1;

int newCapacity = (oldCapacity * 3)/2 + 1;