Quelle est la raison pour laquelle la capacité initiale d'ArrayList en Java est de 10 ?

Pourquoi la capacité initiale de HashMap 16 ?

Quand on parle de la capacité d'initialisation d'ArrayList, il faut d'abord revoir la capacité d'initialisation de HashMap. En prenant le code source Java 8 comme exemple, il y a deux facteurs pertinents dans HashMap : la capacité d'initialisation et le facteur de chargement :

/**
 * 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;

Dans HashMap, la capacité d'initialisation par défaut du tableau est de 16. Lorsque les données sont remplies à 0,75 de la valeur par défaut capacité, il effectuera une expansion 2x. Bien entendu, les utilisateurs peuvent également transmettre la taille spécifiée lors de l'initialisation. Cependant, il convient de noter qu'il est préférable d'utiliser une valeur de 2 à la puissance n. Si elle n'est pas définie sur 2 à la puissance n, HashMap la convertira également, mais cela nécessitera une étape supplémentaire.

Concernant le principe de mise en œuvre de HashMap, je n’entrerai pas dans les détails ici. Il y a déjà trop d’articles sur Internet à ce sujet. Une chose que nous devons savoir est l'algorithme de HashMap pour calculer les coordonnées de la valeur clé, c'est-à-dire en hachant la valeur clé, puis en la mappant aux coordonnées du tableau.

À ce stade, assurez-vous que la capacité de HashMap est de 2 à la nième puissance, puis l'opération sur bits peut être utilisée pour faire fonctionner directement la mémoire pendant l'opération de hachage sans conversion en décimal, et l'efficacité sera plus élevée.

De manière générale, on peut considérer que la raison pour laquelle HashMap utilise 2 à la puissance n et que la valeur par défaut est 16 est due aux considérations suivantes :

• Réduire les collisions de hachage

• Améliorer l'efficacité des requêtes de carte ;

• L'allocation est trop petite pour empêcher une expansion fréquente ;

• L'allocation est trop grande et gaspille des ressources

Tout d'abord, jetons un coup d'œil au code source de la capacité d'initialisation d'ArrayList dans Java 8 :

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

À partir du JDK1.7, lors de l'initialisation d'ArrayList, la valeur par défaut est initialisée sur un tableau vide :

    /**
     * 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;
    }

Réservez vos doutes, jetons d'abord un œil à la méthode add d'ArrayList :

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

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    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=10Dans la méthode ci-dessus, calculez d'abord la capacité par calculateCapacity :

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

Vous constaterez que minCapacity a été réaffecté à 10 (DEFAULT_CAPACITY=10 ), passez ensureExplicitCapacity(minCapacity);C'est minCapacity=10,

La méthode de croissance dans le code ci-dessus est utilisée pour gérer l'expansion, la capacité est étendue à 1,5 fois l'originale.

En comprenant le flux de traitement ci-dessus, nous constaterons qu'essentiellement la capacité initiale d'ArrayList est toujours de 10, mais il utilise simplement le chargement paresseux. Il s'agit d'une optimisation effectuée par Java 8 pour économiser de la mémoire. Par conséquent, du début à la fin, la capacité initiale d’ArrayList est de 10.

Voici une autre mention des avantages du chargement paresseux. Lorsqu'il y a des milliers de ArrayLists dans le programme, la taille par défaut de 10 objets signifie que 10 pointeurs (40 ou 80 octets) sont alloués et utilisés pour le tableau sous-jacent lors de sa création. Remplissez-les avec des valeurs nulles, un tableau vide (rempli de valeurs nulles) prend beaucoup de mémoire. Si vous pouvez initialiser paresseusement un tableau, vous pouvez économiser beaucoup d'espace mémoire. Les modifications apportées à Java 8 visent l’objectif ci-dessus.

Pourquoi la capacité initiale d'ArrayList 10 ?

Enfin, voyons pourquoi la capacité initiale d'ArrayList est de 10. En fait, on peut dire qu'il n'y a aucune raison, c'est juste que ça « fait » du bien, ni trop grand, ni trop petit, juste ce qu'il faut pour les yeux !

Tout d'abord, en discutant de HashMap, nous avons dit que la raison pour laquelle HashMap choisit 2 à la nième puissance est davantage pour tenir compte des performances et des collisions de l'algorithme de hachage. Ce problème n'existe pas pour ArrayList. ArrayList n'est qu'un simple tableau croissant, sans prendre en compte l'optimisation au niveau de l'algorithme. Tant qu’il dépasse une certaine valeur, il peut croître. Par conséquent, en théorie, la capacité d'ArrayList peut être n'importe quelle valeur positive.

La documentation d'ArrayList n'explique pas pourquoi 10 a été choisi, mais cela est probablement dû à la prise en compte de la meilleure correspondance entre perte de performances et perte d'espace. 10. Il n’est ni trop grand ni trop petit. Il ne gaspillera pas trop d’espace mémoire et ne compromettra pas trop les performances.

Si vous devez demander pourquoi vous avez choisi 10 en premier lieu, vous devrez peut-être demander à l'auteur de ce code "Josh Bloch".

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!