>Java >java지도 시간 >Java에서 ArrayList의 초기 용량이 10인 이유는 무엇입니까?

Java에서 ArrayList의 초기 용량이 10인 이유는 무엇입니까?

WBOY
WBOY앞으로
2023-05-10 14:19:131525검색

HashMap 16의 초기 용량은 왜 있나요?

ArrayList의 초기화 용량을 이야기할 때 먼저 HashMap의 초기화 용량을 검토해야 합니다. Java 8 소스 코드를 예로 들면 HashMap에는 초기화 용량과 로딩 인자라는 두 가지 관련 요소가 있습니다.

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap에서 배열의 기본 초기화 용량은 16입니다. 데이터가 기본값의 0.75로 채워지면 2배 확장을 수행합니다. 물론 사용자는 초기화 중에 지정된 크기를 전달할 수도 있습니다. 그러나 2의 n승 값을 사용하는 것이 가장 좋다는 점에 유의해야 합니다. 2의 n승으로 설정되지 않은 경우 HashMap도 이를 변환하지만 한 단계가 더 필요합니다.

HashMap의 구현 원리에 대해서는 여기서 자세히 설명하지 않겠습니다. 이미 인터넷에 이에 대한 기사가 너무 많습니다. 우리가 알아야 할 한 가지는 키 값 좌표를 계산하는 HashMap의 알고리즘입니다. 즉, 키 값을 해싱한 다음 이를 배열의 좌표에 매핑하는 것입니다.

이때, HashMap의 용량이 2의 n승인지 확인해야 하며, 그러면 비트 연산을 사용하여 해시 연산 중에 10진수 변환 없이 직접 메모리를 연산할 수 있어 효율성이 더 높아집니다.

일반적으로 HashMap이 2의 n승을 사용하고 기본값이 16인 이유는 다음 고려 사항 때문이라고 생각할 수 있습니다.

  • 해시 충돌 감소

  • 맵 쿼리 효율성 향상;

  • 할당이 너무 작으면 잦은 확장이 불가능합니다.

  • 할당이 너무 크면 리소스가 낭비됩니다.

간단히 HashMap이 16을 기본값으로 사용하는 이유는 해시 충돌을 줄이고 효율성을 높이기 위한 것입니다.

ArrayList의 초기 용량은 10인가요?

다음으로 먼저 ArrayList의 초기 용량이 10인지 확인한 후, 왜 이 값인지 논의해 보겠습니다.

먼저 Java 8의 ArrayList 초기화 용량 소스 코드를 살펴보겠습니다.

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

분명히 기본 컨테이너 초기화 값은 10입니다. JDK1.2부터 JDK1.6까지 이 값은 항상 10입니다.

JDK1.7부터 ArrayList를 초기화할 때 기본값은 빈 배열로 초기화됩니다.

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

여기 친구들 중 일부는 Java 8에서 ArrayList의 기본 초기화 크기가 10이 아니라 0이라고 말했을 것입니다. 또한 생성자 메서드에 대한 주석에서 이상한 점을 발견할 수 있습니다. 초기 용량이 10인 빈 목록을 생성합니다. 대체 뭐야? 분명히 비어 있습니다!

의심스러운 점을 염두에 두고 먼저 ArrayList의 add 메소드를 살펴보겠습니다.

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

acheCapacityInternal 메소드는 add 메소드에서 호출되므로 처음에는 빈 컨테이너이므로 size=0minCapacity=1에 전달됩니다.

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
size=0传入的minCapacity=1

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

上述方法中先通过calculateCapacity来计算容量:

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    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);
    }

会发现minCapacity被重新赋值为10 (DEFAULT_CAPACITY=10),传入ensureExplicitCapacity(minCapacity);minCapacity=10위 방법에서 먼저 계산 용량을 사용하여 용량을 계산합니다.

ArrayList-10
Vector-10
HashSet-16
HashMap-16
HashTable-11

minCapacity를 찾을 수 있습니다. code>가 10(<code>DEFAULT_CAPACITY=10 )으로 재할당되었습니다. ensureExplicitCapacity(minCapacity);를 전달하세요. 이는 minCapacity=10입니다.

메소드 본문은 다음과 같습니다.

rrreee

위 코드의 성장 메소드는 확장을 처리하는 데 사용되며, 용량이 원래의 1.5배로 확장됩니다.

위의 처리 흐름을 이해하면 기본적으로 ArrayList의 초기 용량은 여전히 ​​10이지만 지연 로딩만 사용한다는 것을 알 수 있습니다. 이는 메모리 절약을 위해 Java 8에서 수행하는 최적화입니다. 따라서 처음부터 끝까지 ArrayList의 초기 용량은 10입니다.

여기에는 지연 로딩의 이점에 대한 또 다른 언급이 있습니다. 프로그램에 수천 개의 ArrayList가 있는 경우 기본 크기인 10개의 개체는 생성 시 기본 배열에 10개의 포인터(40 또는 80바이트)가 할당되고 사용된다는 의미입니다. null 값으로 채우면 빈 배열(null 값으로 채워짐)은 많은 메모리를 차지합니다. 배열을 느리게 초기화할 수 있으면 많은 메모리 공간을 절약할 수 있습니다. Java 8의 변경 사항은 위의 목적을 위한 것입니다.

ArrayList의 초기 용량은 왜 10인가요?

마지막으로 ArrayList의 초기 용량이 10인 이유에 대해 논의해 보겠습니다. 사실 이유가 없다고 할 수 있습니다. 그냥 "느낌"이 좋고, 너무 크지도 작지도 않고, 눈에 딱 맞습니다!

우선 HashMap을 논의할 때 HashMap이 2의 n승을 선택하는 이유는 해시 알고리즘의 성능과 충돌을 더 고려하기 때문이라고 말했습니다. ArrayList에는 이 문제가 존재하지 않습니다. ArrayList는 알고리즘 수준 최적화를 고려하지 않은 단순한 성장 배열입니다. 특정 값을 초과하는 한 성장할 수 있습니다. 따라서 이론적으로 말하면 ArrayList의 용량은 양수 값일 수 있습니다.

ArrayList의 문서에는 10을 선택한 이유가 설명되어 있지 않지만, 성능 손실과 공간 손실 간의 최적 일치를 고려했기 때문일 가능성이 높습니다. 10. 너무 크거나 작지 않으며 메모리 공간을 너무 많이 낭비하지 않으며 성능도 크게 저하되지 않습니다.

애초에 10을 선택한 이유가 궁금하다면 이 코드의 작성자인 "Josh Bloch"에게 물어봐야 할 수도 있습니다.

주의 깊게 관찰하면 다른 흥미로운 초기화 용량 수치도 찾을 수 있습니다.

rrreee🎜ArrayList는 Vector와 동일한 초기화 용량(10)을 가지며 HashSet과 HashMap은 동일한 초기화 용량(16)을 갖습니다. HashTable은 11만을 사용합니다. 또 다른 매우 흥미로운 질문입니다. 🎜

위 내용은 Java에서 ArrayList의 초기 용량이 10인 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
이 기사는 yisu.com에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제