Distinzione tra la capacità di un elenco di array e la dimensione di un array

Ho letto il seguente frammento nel libro Core Java I.

Assegnare un elenco di array come nuova ArrayList (100) // capacity è 100

non è la stessa cosa che assegnare un nuovo array come nuova Employee [100] // la dimensione è 100

C’è un’importante distinzione tra la capacità di un elenco di array e la dimensione di un array. Se si assegna un array con 100 voci, l’array ha 100 slot pronti per l’uso. Un elenco di array con una capacità di 100 elementi ha il potenziale di contenere 100 elementi (e, di fatto, più di 100, a costo di ulteriori riallocazioni); ma all’inizio, anche dopo la sua costruzione iniziale, una lista di array non contiene alcun elemento.

Quando ho visto l’elenco di array del codice sorgente, il costruttore crea una matrice Object di una determinata capacità che è pronta a contenere elementi di una determinata capacità (di seguito è riportato lo snippet di codice).

public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } 

Non sono in grado di capire la reale differenza di ciò che l’autore ha menzionato nel testo sopra.

Se si assegna un nuovo array con arr = new Employee[100] , la dimensione di tale array ( arr.length ) sarà 100. Dispone di 100 elementi. Tutti gli elementi sono inizialmente nulli (dato che si tratta di una matrice di riferimenti a oggetti), ma comunque ci sono 100 elementi.

Se fai qualcosa come list = new ArrayList (100) , e prova a controllare list.size() , otterrai 0. Non ci sono elementi nella lista.

Internamente, è vero che ArrayList assegna abbastanza spazio per mettere 100 elementi prima che sia necessario estendere la sua capacità, ma questo è un dettaglio di implementazione interna e l’elenco presenta il suo contenuto come “nessun elemento memorizzato”. Solo se effettivamente fai list.add(something) , avrai degli elementi nella lista.

Quindi, sebbene la lista assegni in anticipo la memoria, l’API con cui comunica con il programma ti dice che non ci sono elementi in essa contenuti. Gli elementi nulli nel suo array interno non sono disponibili per te – non puoi recuperarli o modificarli.

Un ArrayList è solo un modo per rappresentare un elenco astratto e la capacità di un ArrayList è un dettaglio di implementazione di come il sistema implementa l’elenco logico.

Un ArrayList memorizza gli elementi di un elenco utilizzando un array effettivo “sotto le copertine”. La realizzazione effettiva dell’array nella memoria del computer ha una certa dimensione quando viene allocata; questa dimensione è la capacità dell’ArrayList. ArrayList emula un elenco di dimensioni variabili memorizzando la lunghezza logica dell’elenco oltre alla matrice a lunghezza fissa. Quindi se hai un ArrayList con una capacità 10 che contiene 4 elementi logici, ArrayList può essere rappresentato come una lunghezza e un array

(4) | e1 | e2 | e3 | e4 | __ | __ | __ | __ | __ | __ |

dove (4) è la lunghezza logica della lista e ‘__’ rappresenta i dati che vengono ignorati perché non fanno parte dell’elenco logico. Se si tenta di accedere al quinto elemento di questo ArrayList, genererà un’eccezione perché sa che il quinto elemento non è stato inizializzato. Se poi aggiungiamo un elemento extra e5 all’elenco, l’ArrayList diventa

(5) | e1 | e2 | e3 | e4 | e5 | __ | __ | __ | __ | __ |

Si noti che la capacità non è cambiata, mentre la lunghezza logica lo è, poiché l’array sottostante è ancora in grado di gestire tutti i dati nell’elenco logico.

Se riesci ad aggiungere più di dieci elementi a questo elenco, ArrayList non si interromperà. ArrayList è un’astrazione pensata per essere compatibile con tutte le operazioni dell’array. Piuttosto, l’ArrayList cambia la sua capacità quando la sua lunghezza logica supera la sua capacità originale. Se dovessimo aggiungere gli elementi (a1, a2, …, a7) all’elenco precedente, la ArrayList risultante potrebbe apparire come

(12) | e1 | e2 | e3 | e4 | e5 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | __ | __ | __ | __ | __ | __ | __ | __ |

con una capacità di 20.

Una volta creato un ArrayList, è ansible ignorare la capacità in tutte le programmazioni che seguono; la logica non è influenzata. Tuttavia, le prestazioni del sistema in determinati tipi di operazioni possono essere influenzate. Aumentare la capacità, ad esempio, potrebbe comportare l’allocazione di un array più grande, copiare il primo array nel secondo e quindi eseguire le operazioni. Questo può essere piuttosto lento rispetto, ad esempio, alla stessa operazione su una lista collegata. Pertanto è sensato scegliere la capacità di un ArrayList di essere maggiore o almeno paragonabile al numero effettivo di elementi previsti nell’ambiente di runtime reale.

Se crei un nuovo array myArray = new Object[100] , puoi leggere e scrivere da myArray[0] a myArray[99] (e lo troverai pieno di null ).

Se crei un ArrayList myList = new ArrayList(100) , provi e get o set qualsiasi elemento, otterrai una IndexOutOfBoundsException , perché l’ List è vuoto finché non add qualcosa.

In breve, la matrice della dimensione 100 inizialmente contiene 100 null s, ma la List sarà vuota.

Questo sembra poco formulato e potenzialmente errato se non lo capisco correttamente.

Credo che quello che sta cercando di dire è che c’è una differenza tra la capacità iniziale di ArrayList e la dimensione iniziale di ArrayList.

 List employees = new ArrayList<>(100); int size = employes.size(); 

la dimensione sarà 0 mentre la capacità iniziale è 100.

Hai ragione su come stai leggendo il codice sorgente.

La differenza è tra un contenitore di dimensioni fisse (struttura dati) e un contenitore di dimensioni variabili .

Un array è un contenitore di dimensioni fisse , il numero di elementi che contiene è stabilito quando la matrice viene creata e non cambia mai. (Quando viene creato l’array, tutti questi elementi avranno un valore predefinito, ad esempio null per i tipi di riferimento o 0 per interi, ma saranno tutti presenti nell’array: è ansible indicizzare tutti e ciascuno.)

Una lista è un contenitore di dimensioni variabili , il numero di elementi in esso contenuti può variare, variando da 0 a quanti ne vuoi (sobject a limiti di implementazione). Dopo la creazione, il numero di elementi può aumentare o diminuire. In ogni momento puoi recuperare qualsiasi elemento dal suo indice.

Ma il concetto di Java List è in realtà un’interfaccia e può essere implementato in molti modi diversi. Così, ArrayList , LinkedList , ecc. C’è una struttura dati “dietro” l’elenco per contenere effettivamente gli elementi. E quella stessa struttura dati potrebbe avere dimensioni fisse o dimensioni variabili, e in qualsiasi momento potrebbe avere la dimensione esatta del numero di elementi nell’elenco, oppure potrebbe avere uno spazio extra “buffer”.

La LinkedList , ad esempio, ha sempre nella sua struttura dati sottostante esattamente lo stesso numero di “posti per elementi” che sono nella lista che rappresenta. Ma ArrayList usa un array a lunghezza fissa come backing store.

Per ArrayList , in qualsiasi momento il numero di elementi nell’elenco può essere diverso dal numero di elementi che può contenere l’array sottostante. Questi posti “extra” per gli elementi contengono solo null o 0 o qualsiasi altra cosa, ma ArrayList non ti dà mai accesso a quei luoghi. Man mano che si aggiungono elementi a ArrayList , occupano più posizioni nell’array sottostante, fino a quando l’array sottostante è pieno. L’elemento successivo che aggiungi a ArrayList causa una matrice di dimensioni fisse completamente nuova – un po ‘più grande della matrice “corrente” – da allocare e tutti gli elementi della lista copiati (l’array originale viene scartato). Per evitare che questa costosa operazione (allocazione e copia) si verifichi troppo spesso il nuovo array è più grande della matrice corrente (di qualche fattore) e quindi ha elementi che non conserveranno elementi della lista in quel momento – sono vuoti (null o 0).

Quindi, poiché esiste (potenzialmente) una differenza tra il numero di elementi nella lista che viene rappresentata e il numero di elementi che la struttura di dati di implementazione può contenere ci sono due concetti in vigore.

La dimensione della lista è il numero di elementi in essa contenuti. La capacità dell’elenco è il numero di elementi che la struttura dei dati di supporto può contenere in questo momento . La dimensione cambierà quando gli elementi vengono aggiunti o rimossi dall’elenco. La capacità cambierà quando l’implementazione della lista in uso ne ha bisogno. (La dimensione, ovviamente, non sarà mai più grande della capacità.)

(Per quanto riguarda i contenitori di dimensioni fisse, la dimensione viene spesso chiamata lunghezza , quindi gli array hanno una lunghezza di proprietà e le stringhe hanno un metodo length () . Lingue diverse – a volte anche la stessa lingua – usano “size” e “length” in modo incoerente, ma indica sempre la dimensione e il termine “capacità” viene sempre utilizzato per la dimensione / lunghezza della struttura dati sottostante.)

Usiamo un esempio di vita reale. Considerate un autobus da diciotto posti, la capacità è di diciotto passeggeri. La dimensione dei passeggeri in un dato momento può essere inferiore a diciotto ma non superiore a Quando il numero dei passeggeri è diciotto, un altro passeggero non può essere ospitato.

In una ArrayList, la capacità ha qualcosa in comune con quella del nostro bus in quanto definisce il numero di elementi che possono essere contenuti. Diversamente dal nostro bus, tuttavia, la capacità si espande per accogliere il numero di elementi fino a Integer.MAX_VALUE.

Lo stesso vale per le dimensioni, proprio come il nostro autobus, la dimensione degli elementi nell’elenco non può superare la capacità. Immagina quando 50 passeggeri stanno viaggiando su un autobus a diciotto posti! Sei sicuro di non voler essere su quell’autobus.