Array, ArrayList e Hash Table
Approfondimento su array e array dinamici
Last updated
Approfondimento su array e array dinamici
Last updated
Slide argomento: e .
L' array, struttura dati presente in tutti i linguaggi di programmazione moderni, è un tipo di contenitore di oggetti o tipi primitivi omogenei (tutti dello stesso tipo). L' array è una struttura dati di base nel linguaggio Java. Le altre strutture dati di tipo contenitore sono invece classi della libreria del JDK, vedi , comunemente dette java collections.
Molto di quello che abbiamo appreso sui refetence type e gli oggetti si applica anche agli array:
gli array sono manipolati tramite reference;
gli array sono creati dinamicamente tramite new;
sono automaticamente garbage collected quando non sono più riferiti;
Le sezioni seguenti spiegano questi e altri dettagli.
Ci sono due modi per creare un array. La prima è tramite new e specificando la lunghezza dell'array:
Nell'esempio sopra abbiamo creato due array uno di 1024 byte e un altro di 10 reference a oggetti di tipo Button e assegnati alle variabili rispettivamente octet_buffer e buttons.
Poiché la creazione dell’array non crea gli oggetti che sono immagazzinati nell’array, non c’è costruttore da richiamare, e la lista degli argomenti è omessa con questo uso di new .
Gli elementi dell’array sono creati in questo modo e sono inizializzati al loro valore di default per il loro tipo. Gli elementi di un array di int sono ad esempio inizializzati a 0, metre gli elementi di un array di oggetti sono inizializzati a null.
Quest’ultimo punto è importante da capire: la creazione di un array di oggetti alloca solo lo spazio per contenere le reference degli oggetti, non gli oggetti.
array di tipi primitivi:
array di tipi reference:
Il secondo modo per creare un array e con un inizializzatore, che assomigli alla modalità del linguaggio C.
Con questa sintassi, dinamicamente viene creato un array e inizializza gli elementi con i valori specificati. Gli elementi specificati nell'inizializzatore dell'array possono essere espressioni arbitrarie. In questo differisce dal C dove devono essere costanti.
Gli array possono essere anche creati anonimous (come anonimi, senza nome) combinado la sintassi della new con l'inizializzazione, esempi:
Gli array sono garbage collected come gli altri oggetti.
Ricorda che il primo elemento dell'array aè a[0]mentre l'ultimo è a[ a.lenght -1 ] . Un bug comune nell'utilizzo degli array è l'utilizzo di un indice troppo basso (un numero negativo) o troppo grande (più grande o uguale alla lunghezza dell'array). In linguaggi come il C o C++ l'accesso prima dell'inizio o dopo la fine dell'array poteva portare a comportamenti imprevedibili e bachi che magari non si evidenziavano subito e in seguito difficili da individuare. Anche se comunque in Java è semplice scrivere codice errato che accede fuori dai limiti dell'array (o indice troppo basso o oltre la lunghezza), la JVM garantisce un comportamento univoco: a runtime l'accesso con indice all'elemento dell'array viene sempre controllato che sia nei limiti consentiti e se si tenta di accedere fuori dai limiti viene lanciata una runtime exception, java.lang.ArrayIndexOutOfBoundsException .
Oppure,
E' utile considerare gli array come un tipo di reference type diverso dagli oggetti. Ma in un certo modo gli array si comportano come oggetti. Come aggiamo visto gli array usano la sintassi deli oggetti .length per accedere al valore della lunghezza dell'array. Un array può anche assere assegnato a una variabile di tipo Object e i metodi di Object possono essere invocati su una variabile di tipo array.
Tutti i tipi di array implementano l'interfaccia Clonable, e l'array può essere copiato invocando il metodo clone() dell'array. Da notare che è necessario un'operazione di cast per convertire l'oggetto nell'appropriato tipo di array.
Il metodo clone esegue quella che si chiama una shallow copy (copia superficiale): se gli elementi contenuti nell'array sono di tipo reference, solo le referenze sono copiate ma non gli oggetti puntati. Siccome la copia è shallow, ogni array può essere clonato anche se il tipo degli elementi potrebbe anche non essere Clonable.
Delle volte si vuole semplicemente copiare il gli elementi di un array dentro gli elementi di un altro array, per questo esiste il metodi statico System.arraycopy() che esegue una copia molto efficiente lavorando sui blocchi di memoria.
La classe java.util.Arrays contiene una serie di metodi statici di utilità per lavorare sugli array. Molti di questi metodi hanno versioni overloaded per ogli tipo di array primitivo e per array di oggetti. Particolarmente utili sono i metodi sort() per ordinare e binarySearch() per la ricerca di un elemento quando l'array è già ordinato. Il metodo equals() permette di comparare il contenuto di due array. Il metodo Arrays.toString() è utile per convertire il contenuto di un array in una stringa (per debugging o per loggare l'output).
Il metodo copyOf è utile per fare una copia di un array di partenza:
restituisce un array dato un array di input (list nel nostro esempio) della dimensione specificata. Se la lengthOfCopy è maggiore della lunghezza dell'array di input, l'array di output avrà gli elementi eccedenti valorizzati con il valore di default per il tipo base dell'array. Se invece lengthOfCopy è <= di list.length, viene compiato nel nuovo array solo il numero di elementi da list che ci stanno nel nuovo array.
Così se A è un array:
otteniamo un array B della stassa lunghezza di A con copia degli stessi elemento, e con questo codice:
possiamo raddoppiare la dimensione di un array, in questo caso playerList.
La classe Arrays ha altri metodi statici molto utili per lavorare con array:
Arrays.fill( array, value) - Riempie tutto l'array con il valore specificato. Il tipo del valore deve essere compatibile con il tipo base dell'array. Per esempio, assumendo che numList è un array di double[], allora Arrays.fill( numList, 17), settera ogni elemento di numList al valore 17;
Arrays.fill( array, fromIndex, toIndex, value) - Riempie parte dell'array con value, partendo da fromIndex e finendo a toIndex -1, Da notare che toIndex non è incluso.
Arrays.toString( array) - Una funzione che ritorna una String contenente tutti gli elementi dell'array, separati da virgole e inclusi tra parentesi quadre. I valori dell'array, sono convertiti a String, nello stesso modo in cui sarebbero stampati a standard output.
Arrays.sort( array) - Ordina un intero array. Ordinare un array significa disporre gli elementi dell'array in ordine crescente. Il metodo funziona per tipi primitivi (eccetto i boolen) e per oggetti che implementano l'interfaccia Comparable;
Arrays.sort( array, fromIndex, toIndex) - Ordina solo gli elementi da array[fromIndex] a array[toIndex -1];
Arrays.binarySearch( array, value) - Ricerca il valore nell'array. Prerequisito è che l'array sia già ordinato in ordine crescente. La funzione ritorna un int. Se il valore è ritrovato nell'array, ritorna il valore dell'indice dell'elemento nell'array. Se il valore invece non è presente, viene ritornato il valore -1;
Utilizziamo ora Arrays.copyOf() per create un array dinamico: l'array dinamico è una struttura dati che a differenza dell'array fin qui definito, non viene dichiarato in fase di inizializzazione la dimensione, ma varia in base all'esigenza.
Definiamo una nuova classe che modella un array dinamico si interi. Le operazioni definite per l'array dinamico:
aggiungere un elemento alla fine dell'array;
rimuovere un elemento a una specifica posizione dell'array;
prendere il valore di uno degli elementi dell'array;
settare il valore di uno degli elementi dell'array;
avere il numero degli elementi attualmente nell'array;
Supponiamo che vogliamo creare un array dinamico che contenga ohhetti di tipo String . Non possiamo più utilizzare la classe DynamicArrayOfInt, ma dovremmo definire una classe ad esempio DynamicArrayOfString che contenga al suo interno un vettore di String. O se vogliamo avere un vettore dinamico che contenga dei giocatori, dovremmmo fare una classe DynamicArrayOfPlayer. E così via, per ogni tipo di dato di cui vogliamo creare un array dinamico. Sembra piuttosto scomodo. Java ha una classe della libreria standard che implementa gli array dinamici ma che può essere utilizzata per ogni tipo di dato (non del tutto vero, perchè non può essere utilizzata sui tipi primitivi, ma comunque in Java ci sono i tipi wrapper dei tipi primitivi, es di int è la classe Integer). Questa classe è java.util.ArrayList e vediamo nel prossimo paragrafo di trattare qualche esempio.
Abbiamo visto nel paragrafo precedente la costruzione di un array dinamico in modo molto semplice, ma sembra che bisogni fare un array dinamico per ogni tipo di classe di oggetti dell'array. Java ha una soluzione a questo tipo di problemi con i "tipi parametrici". Java ha una classe java.util.ArrayList che implementa l'array dinamico è può funzionare con ogni tipo di dato.
ArrayList<T> è un tipo parametrico, nel senso che la stessa classe può essere utilizzata per lavorare con Integer o String o con classi da noi definite come ed esempio Player (che rappresenta ed esempio un giocatore). Vediamo ad esempio come definiamo due variabili di tipo ArrayList per i tipi String e Player:
Un tipo parametrico è un tipo generico (da ArrayList<T> possimo creare diversi tipi ArrayList<String> o ArrayList<Player>), che viene poi specializzato una volta che viene create una variabile del tipo desiderato.
Un oggetto di tipo ArrayList<T> ha tutti i metodi che ci aspetteremmo da un array dinamico:
list.size() - questo metodo ritorna la dimensione corrente della lista, cioè il numero di elementi al momento nella lista. Le sole posizioni valide nella lista sono i numeri nel ranga 0 e list.size() - 1. Da notare che li size può essere 0. Una chiamata del costruttore di default, new ArrayList<T>(), crea una lista di size 0.
list.add(obj) - aggiunge un elemento alla fine della lista, incrementando la size di 1. Il parametro obj, può essere un oggetto di tipo T, o può essere il valore null.
list.get(N)- questa funzione ritorna il valore immagazzinato nella posizione N della lista. Il tipo del parametro di ritorno deve essere T. N deve essere un intero nel range 0 e list.size() - 1. Se N è fuori dal range lancia IndexOutOfBoundException se N >= list.size(). Chiamare questa funzione è come fare A[N] di un array A, eccetto che non si può usare get(N) nella parte sinistra di un assegnamento.
list.set(N, obj) - Assegno un oggeto, obj, alla posizione N dell'ArrayList, rimpiazzando l'elemento precedente immagazzinato nella posizione N. Il parametro obj deve esere di tipo T. L'intero N deve essere nel range 0 e list.size() -1. La chiamata è equivalente a A[N] = obj, per un array A.
list.clear() - rimuove tutti gli elementi della lista, settando la dimensione a 0.
list.remove(N) - per un itero, N, rimuove l'ennesimo elemento dall'ArrayList. N deve essere nel range 0 a list.size() - 1. Tutti gli elementi nella lista che vengono dopo l'elemento rimosso, vengono spostati indietro di una posizione. La dimenzione della lista viene decrementata di 1.
list.remove(obj) - se l'oggetto, obj, è presente nella lista, è rimosso dalla lista. tutti gli oggetti che vengono dopo nella lista, dell'oggetto rimosso, sono spostati indietro di 1. La dimensione dell'ArrayList è decrementata di 1. Se un oggetto è presente più di una volta nella lista, solo la prima copia è rimossa. Se un oggeto non è presente nella lista, non succede nulla, non è un errore.
list.indexOf(obj) - la funzione ricerca l'oggetto, obj, nella lista- Se l'oggetto è trovato nella lista, la posizione del primo elemento trovato è ritornata. Se invece l'oggetto non è trovato, ritorna -1.
Gli ultimi due metodi obj è confrontato con gli altri elementi della lista tramite obj.equals(item).
Esempio di utilizzo di ArrayList per stampare gli interi dati in input in ordine inverso. Utilizziamo per contenere gli interi in questo caso, ArrayList<Integer>.
La versione del codice non è molto robusta? Digitate invece di un numero una stringa con numerica e vedete cosa succede.
ESERCIZIO: Potreste come esercizio rendere il codice più robusto gestendo questo caso.
Se volessi fare la stessa funzionalità con liste oggetti di tipo String potrei utilizzare la classe ArrayList<String>.
Il metodo più semplice ma più costoso a livello computazionale per la ricerca su un array è la ricerca lineare: scorro tutto l'array cercando l'elemento.
Qui il caso in cui cerco la posizione di un intero all'interno di un vettore di interi:
Nel caso l'array di partensa sia già ordinato, posso utilizzare la ricerca binaria:
Un'altra struttura dati che può essere costruita da semplici array è una lista associativa. Un esempio tipico di una lista associativa è un dizionario: da una parola è possiblie trovare una definizione legata a quella parola.
Noi possiamo pensare a un dizionario come a una lista (sequemza ordinata) di coppie (k, v), dove k sta per "key" (chiave) e v sta per "value" valore, associato a quella chiave. In genere assumiamo che non ci siano due coppie nella lista con la stessa chiave.
Data una lista associativa ci sono due possibili operazioni: data una k, chiave, si trova se c'è la v, valore, corrispondente. E data una chiave, k e il corrispettivo valore v, si aggiunge la coppia (k, v) all'association list (rimpiazzando la coppia se c'era già una coppia con la medesima chiave). Le due operazioni sono in genere chiamate get e put.
Vediamo un esempio di lista associativa, implementata tramite un array:
Questa classe utilizza un metodo privato find() che usa la ricerca lineare, sia quando fa la putNumber(name, number), sia quando fa la getNumber(): si potrebbe migliorare il metdodo facendo una ricerca binaria, tenendo l'array ordinato. Per array di piccole dimensioni, anche la ricerca lineare non è un grosso dispendio in più. Le cosa cambiano quando la lunghezza dell'array supera del decine di migliaia. Vedremo nei prossimo paragrafi come eseguire l'ordinamento (sorting).
Esempio di utilizzo della classe PhoneDirectory nel programma TestPhoneDirectory:
Dall'esecuzione di TestPhoneDirectory, il seguente output:
Vediamo come utilizzando un java.util.HashMap la classe PhoneDirectory diventi semplicissima, pur esponendo le stesse funzionalità dell'altra versione che utilizzava un array per contenere le PhoneEntry:
Come abbiamo detto, esistono strutture dati molto più performanti, per implementare una lista associativa, rispetto al semplice array. Nell'esempio della prima implementazione di PhoneDirectory è stato utilizzato un array. mentre nella seconda implementazione, quando abbiamo utilizzato la classe java.util.HashMap, quest'ultima utilizza internamente una struttura dati chiamata hash table, struttura dati tra le classiche come linked list e alberi binari. Vediamo nel prossimo parametro la descrizione della struttura dati hash table.
La hash table, è una struttura dati, addatta alla problematica della ricerca, per evitare di eseguire la ricerca su ogni elemento.
Hash table, immagazzina i sui dati in un array, e l'indice dell'array, dove la chiave è immagazzinata, è basata sulla chiave. L'indice non è uguale alla chiave, ma è calcolata dalla chiave. L'indice dell'array per la chiave è detto hash code della chiave. Una funzione che computa un hash code, data una chiave, è chiamata hash function. Per trovare una chiave in un'hash table, dobbiamo calcolare l'hash code della chiave e andare direttamente nella posizione dell'array data dall'hash code. Se l'hash code è 17, andiamo nella posizione dell'array 17.
Ora, siccome ci sono meno posizione dell'array rispetto alle possibili chiavi, è possibile, che tu possa cercare di immagazzinare due o più chiavi nella stessa locazione dell'array. Questo caso è chiamato collision (collisione). Una collision non è un errore. Non si rigetta una chiave solo perchè un'altra chiave ha lo stesso hash code. Un'hash table deve essere in grado di gestire le collision in modo opportuno. Nella implementazione in Java dell'hash table, ogni elemento dell'array ha una reference a una linked list di coppie chiave/valore (possibilmente anche una lista vuota). Quando due elementi hanno lo stesso hash code, essi sono nella stessa linked list. Sotto è una figura di come è implementata un hash table.
C'è ancora la questione da dove arrivano gli hash code. Ogni oggetto java ha un hash code. La classe Object definisce il metodo hashCode() che ritorna un int. Quando un oggetto, obj, è immagazzinato in un'hash table che ha N posti, un hash code nel range da 0 a N -1 è necessario. L'hash code è calcolato come Math.abs(obj.hashCode()) % N, il resto del valore assoluto di obj.hashCode() diviso per N. (Math.abs, per ottenere il valore assoluto è necessaria perché obj.hashCode() può essere un numero negativo, e noi abbiamo bisogno di un numero non negativo come indice dell'array).
Affinchè la tabella di hash funzioni correttamente bisogna che se due oggetti sono uguali secondo il metodo equals() devono avere lo stesso hash code.
Nella classe Object, questa condizione è soddisfatta perché, entrambi i metodi equals() e hashCode() sono basati sull'indirizzo di memoria degli oggetti. Abbiamo visto però che molte volte è utile ridefinire equals() (tipo quando inserisco gli oggetti in una lista poi per ritrovarli). Se una classe ridefinisce il metodo equals(), e la classe è utilizzata come tipo degli oggetti chiave nella hast table, allora la classe deve ridefinire anche il metodo hashCode(): l'hash code dovrà dipendere dal contenuto dell'oggetto e dovrà garantire che se due oggetti sono uguali per equals() il valore di tipo int di hashCode() dei due oggetti deve essere ==.
Per esempio, nella classe String, il metodo equals() è stato ridefinito così che due oggetti di tipo String sono considerati uguali se contengono la stessa sequenza di caratteri. Anche il metodo hashCode() è stato ridefinito nella classe String, così che l'hash code è calcolato in base ai caratteri contenuti nella stringa e non in base all'indirizzo di memoria.
Vedi anche esempio sotto package addresslist in cui nella classe addresslist.AddressDirectory viene tenuta l'associazione tra oggetti di tipo Customer e tipo Address , tramite una HashMap<Customer, Address>. Le classi Customer e Address contengono i dati rispettivamente del cliente (nome, cognome) e il suo indirizzo (via, città, CAP).
Come abbiamo visto ci sono delle buone ragioni per ordinare un array. Vediamo due diversi algoritmi, tra i più semplici, di ordinamento.
Supponiamo di avere una lista ordinata e di voler aggiungere un elemento alla lista. Se si vuole che la nuova lista sia ancora ordinata, allora il nuovo elemento deve essere inserito nel posto giusto (rispetto all'ordinamento), cioè con gli elementi più piccoli messi prima e quelli più grandi messi dopo. Questo vuol dire muovere gli elementi più grandi avanti di un elemento per fare posto al nuovo elemento.
Concettualmente questo può essere esteso, per ordinare un array, prendendo ogni elemento di un array non ordinato, uno alla volta, per inserirlo di nuovo dentro l'array in modo ordinato. Ogni inserimento può essere fatto con la routine insert vista sopra.
Qui sotto una illustrazione di un passo durante l'esecuzione dell'insert sort. Questo mostra cosa succede durante una esecuzione del loop for nel metodo sopra, quando itemsSorted è 5:
Un altro semplice algoritmo per ordinare consiste nel trovare il più grande elemento della lista e spostarlo alla fine - dove deve stare se si vuole ordinare in modo crescente. Una volta che l'ememento più grande è nell'ultima posizione, si può riapplicare l'idea ai rimanenti. Cioè travare il prossimo elemento più grande, e spostarlo nella posizione precedente l'ultima, e così via. Questo algoritmo si chiama selection sort.
Un altro esempio di utilizzo dell'algoritmo di selection sort per ordinare un mazzo di carte (utilizzando la classe ArrayList al posto dell'array). In questo caso la carte sono contenute in una lista di tipo ArrayList<Card>. Un oggetto di tipo Card contiene due metodi d'istanza getSuit() e getValue(). In questo algoritmo di sorting, viene creata una nuova lista di carte: le carte sono prese dalla vecchia lista in ordine crescente, e messe nella nuova lista. Alla fina alla variabile hand (che conteneva la vecchia lista di carte non ordinate) viene assegnata la nuova lista con le carte ordinate.
Un argomento legato all'ordinamento, è quello di mettere un elemento in modo casuale in un array o unsorting. Il tipico caso è quello di mischiare un mazzo di carte. Un buon algoritmo per mischiare (shuffling) è simile al selection sort, eccetto che invece di spostare l'elemento maggiore alla fine della lista, un elemento è selezionato a caso e messo alla fine della lista. In questo esempio sotto viene mischiato in array di int:
Abbiamo visto due algoritmi di sorting, insertion sort e selection sort, applicati ad array di interi. Si è scelto volutamente di utilizzare una struttura dati semplice come array e un tipo di dati int che naturalmente ha un criterio di ordinamento, quello dei numeri naturali.
Esistono anche altri algoritmi di ordinamento, come merge sort o quicksort che non vediamo, ma quello che hanno in comune tutti questi algoritmi è che:
operano su una struttura dati di tipo lista, come ad esempio un array, un java.util.ArrayList o java.util.LinkedList;
per ordinare gli elementi, ci deve essere un criterio per stabilire tra due elementi della lista quale dei due è maggiore;
In Java, le classi java.util.Arrays e java.util.Collections hanno i metodi di sort, con già implementato l'algoritmo, per ordinare rispettivamente array o strutture del tipo java.util.List ( come java.util.ArrayList e java.util.LinkedList).
Nell'esecuzione dell'algoritmo di sort, il metodo, poi dovrà confrontare due valori (due tipi primitivi o due oggetti):
se i valori sono di tipo primitivo (come int, float o double). hanno implicitamente già il criterio di ordinamento;
se i valori sono non primitivi (oggetti):
o implementano java.lang.Comparable con il metodo quindi int compareTo(T o) che dà il criterio per decidere quale dei due maggiore;
o al metodo di sort viene passato anche un oggetto di tipo java.util.Comparator con il metodo int compare(T o1, T o2).
Il contratto dei due metodi (Comparable.compareTo e Comparator.compare) stabilisce che ritornino un intero > 0, se il primo valore è maggiore del secondo valore, = 0, se sono uguali e un intero < 0 altrimenti.
Sono creati come array di array. Esempio di array bidimensionale:
Esso crea un array bidimensionale di 12 int disposto su 3 righe e 4 colonne. Si possono inizializzare gli array multidimensionali, con gli array literals, ad esempio:
oppure si può essegnare:
Si può estendere naturalmente ad array di 3-dimensioni, 4-dimensioni e così via.
Java nella realtà non ha array bidimensionali, intesi come una zona di memoria contigua di in certo numero di righe e colonne. Vediamo come l'array bidimensionale è gestito in Java e per analogia oltre le due dimensioni.
Java ha molti tipi parametri per rappresentare molte strutture dati. Qui abbiamo considerato solo ArrayList che fa parte del Java Collection Framework e sarà un argomento specifico in .
La lista associativa è anche chiamata "maps" e Java ha diverse classi che implementano l'interfaccia java.util.Map che rappresenta il tipo astratto di lista associativa. Vi sono diverse implementazioni dell'interfaccia java.util.Map che sono ad esempio java.util.HashMap e java.util.TreeMap, pronte per l'uso qualora aveste bisogno di una lista associativa. L'implementazione è molto più efficiente di qualsiasi cosa si possa fare con gli array. Vedremo in .
Vedi codice in particolare esempio in package withMap il codice che utilizza HashMap<String, String> per mappare nome utente a numero di telefono (trattato come oggetto di tipo String) e contenere i dati.
Vedi Card.java e Hand.java il per il codice completo.
Vedi classe Deck.java per utilizzo del metodo shuffle() per mischiare le carte di un mazzo, in .
Vedi: , e le classi e , per i metodi di sort su array e collezioni.
In , sotto la classe utilizza java.util.Collections.sort() e java.util.Comparator per eseguire l'ordinamento.
