Analyse détaillée du code source du framework de collection Java ArrayList (image)

Introduction générale

ArrayList implémente l'interface List, qui est un conteneur séquentiel où les éléments sont stocké Les données sont dans le même ordre dans lequel elles sont insérées, permettant d'insérer les éléments null. La couche inférieure implémente via le tableau . Sauf que cette classe n'implémente pas la synchronisation, le reste est à peu près le même que Vector. Chaque ArrayList a une capacité, qui représente la taille réelle du tableau sous-jacent. Le nombre d'éléments stockés dans le conteneur ne peut pas dépasser la capacité actuelle. Lorsque des éléments sont ajoutés au conteneur, celui-ci augmente automatiquement la taille du tableau sous-jacent si la capacité est insuffisante. Comme mentionné précédemment, les génériques Java ne sont que du sucre syntaxique fourni par le compilateur, donc le tableau ici est un tableau Object pour pouvoir accueillir tout type de Object. Les méthodes

size(), isEmpty(), get() et set() peuvent toutes être exécutées en temps constant. Le coût en temps de la méthode add() est de . lié à la position d'insertion, le coût en temps de la méthode addAll() est proportionnel au nombre d'éléments ajoutés. La plupart des autres méthodes sont en temps linéaire.

Dans un souci d'efficacité, ArrayList n'est pas synchronisé. Si un accès simultané par plusieurs threads est requis, les utilisateurs peuvent synchroniser manuellement ou utiliser Vector à la place.

Méthode d'analyse

set()

Puisque la couche inférieure est un tableau, la méthode ArrayListde set() devient très simple, il suffit d'utiliser le tableau directement Attribuez simplement une valeur à l'emplacement spécifié. La méthode

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get() est également très simple. La seule chose à noter est que puisque le tableau sous-jacent est Object[], vous devez effectuer <🎜. >tapez la conversion< après avoir obtenu les éléments 🎜>.

add()

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

est différent du

vecteur

de C++ ArrayList n'a pas de méthode et la méthode correspondante. est , bush_back()ArrayListadd(E e) n'a pas non plus de méthode , la méthode correspondante est . Les deux méthodes ajoutent de nouveaux éléments au conteneur, ce qui peut entraîner une insert()capacitéadd(int index, E e) insuffisante. Par conséquent, avant d'ajouter des éléments, l'espace restant doit être vérifié et automatiquement agrandi si nécessaire. L'opération d'expansion est enfin complétée grâce à la méthode . grow()

Étant donné que Java GC gère automatiquement la mémoire, il n'est pas nécessaire de considérer ici la question de la version du tableau source.

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的3倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

Une fois le problème d'espace résolu, le processus d'insertion devient très simple.

Vous devez d'abord déplacer l'élément, puis terminer l'opération d'insertion, ce qui signifie que cette méthode a une complexité temporelle linéaire. La méthode

add(int index, E e)addAll()

peut ajouter plusieurs éléments à la fois. Il y a deux handles selon la position. L'un est ajouté à la fin. ;? extends

E> c), on est inséré à partir de la position spécifiée addAll()Méthode. Semblable à la méthode addAll(Collection <a href="http://www.php.cn/wiki/166.html" target="_blank">extends</a> E> c), une vérification de l'espace est également requise avant l'insertion, et la capacité sera automatiquement étendue si nécessaire si elle est insérée à partir d'une position spécifiée, les éléments peuvent également être déplacés ; La complexité temporelle de addAll(int index, Collection extends E> c)add() n'est pas seulement liée au nombre d'éléments insérés, mais aussi à la position d'insertion. La méthode
addAll()remove()

a également deux versions, l'une consiste à

supprimer l'élément à la position spécifiée, l'autre consiste à remove() supprimer le premier élément qui satisfait l'élément remove(int index). L'opération de suppression est le processus inverse de l'opération remove(Object o), qui nécessite de déplacer l'élément après le point de suppression vers l'avant d'une position. Il convient de noter que pour que GC fonctionne, la dernière position doit se voir explicitement attribuer une valeur o.equals(elementData[index]). add()null

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!