corsoJava
  • Corso JAVA
  • Introduzione linguaggio
  • Verifica tipi primitivi vs reference
  • Esercizi su equals
  • Introduzione su oggetti
  • Packages e import
  • Polimorfismo
    • Pit stop
  • Enum
  • String รจ speciale
  • Eccezioni
  • Nested Classes
  • Array, ArrayList e Hash Table
    • Esempio gioco carte
  • Linked data structures
  • Tipi generici
  • Comparing Java and C# Generics - Jonathan Pryor's web log
  • Contenitori
    • Esempi con classi container
  • Input/Output streams, Files
  • Basic I/O
  • Java IO Tutorial
  • Networking
  • I Thread e concorrenza
    • Esercizi multithreading
    • Thread interference
    • Esercizi thread interference
    • wait(), notify() e notifyAll() per la sincronizzazione tra i thread
    • Verifiche produttore/consumatore
    • Lock esplicito - java.util.concurrent.Locks
    • Semafori
    • Programmare con i thread
    • I Virtual Thread
    • Materiale
  • I Thread e networking
  • Esempi Java Socket Programming
  • Esempi Javascript Socket Programming
  • Messaggi datagram e invio multicast
  • Lambda Expression
  • Java Stream
  • Data Oriented Programming in Java
  • Java improved its 'Hello World' experience
  • Appendice A: utilizzo classe Scanner
  • Java For The Experienced Beginner
  • Modern Java
  • CodeJava - Java Core
  • Is OOP Relevant Today?
  • Book
Powered by GitBook
On this page
  • Creazione di array
  • Estremi degli array
  • Accedere agli array
  • Iterare sugli array
  • Sono gli array oggetti?
  • Dichiarare variabili di tipo array e argomenti
  • Copiare gli array
  • Array utilities
  • ArrayList
  • Ricerca e Ordinamento su array
  • Lista associativa
  • Hash Table e Hash Code
  • Ordinamento
  • Sorting in Java
  • Array Multidimensionali

Array, ArrayList e Hash Table

Approfondimento su array e array dinamici

PreviousNested ClassesNextEsempio gioco carte

Last updated 6 years ago

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.

Creazione di array

Ci sono due modi per creare un array. La prima รจ tramite new e specificando la lunghezza dell'array:

byte octet_buffer[] = new byte[1024];
Button buttons[] = new Button[10];

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:

int[] list = new int[5];
  • array di tipi reference:

// Rect, Line e FilledOval sono sottoclassi di Shape

Shape[] shapes = new Shape[100]; // Array to hold up to 100 shapes.
shapes[0] = new Rect();          // Put some objects in the array.
shapes[1] = new Line(); 
shapes[2] = new FilledOval();

Il secondo modo per creare un array e con un inizializzatore, che assomigli alla modalitร  del linguaggio C.

int lookup_table[] = {1, 2, 4, 8, 16, 32, 64, 128};

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:

Menu m = createMenu("File", new String[] { "Open...", "Save", "Quit" });

Gli array sono garbage collected come gli altri oggetti.

Estremi degli array

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 .

Accedere agli array

int a[] = new int[100]; 
a[0] = 0; 
for(int i = 1; i < a.length; i++) 
    a[i] = i + a[i-1];

Iterare sugli array

int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
int sumOfPrimes = 0;

for(int i = 0; i < primes.length; i++)
    sumOfPrimes += primes[i];

Oppure,

for(int p : primes) sumOfPrimes += p;

Sono gli array oggetti?

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.

Dichiarare variabili di tipo array e argomenti

void reverse(char[] strbuf, int buffer_size) { 
    char[] buffer = new char[500]; 
    ... 
    }

Copiare gli 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.

int[] data = { 1, 2, 3 };
int[] copy = (int[]) data.clone();

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.

Array utilities

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:

Arrays.copyOf( list, lengthOfCopy )

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:

B = Arrays.copyOf( A, A.length );

otteniamo un array B della stassa lunghezza di A con copia degli stessi elemento, e con questo codice:

playerList = Arrays.copyOf( playerList, 2*playerList.length );

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.

Array dinamici

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;

import java.util.Arrays;

/**
 * Represents a list of int values that can grow and shrink.
 */
public class DynamicArrayOfInt {
	private int[] items = new int[8]; // partially full array holding the ints
	private int itemCt;

	/**
	 * Return the item at a given index in the array. Throws
	 * ArrayIndexOutOfBoundsException if the index is not valid.
	 */
	public int get(int index) {
		if (index < 0 || index >= itemCt)
			throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
		return items[index];
	}

	/**
	 * Set the value of the array element at a given index. Throws
	 * ArrayIndexOutOfBoundsException if the index is not valid.
	 */
	public void set(int index, int item) {
		if (index < 0 || index >= itemCt)
			throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
		items[index] = item;
	}

	/**
	 * Returns the number of items currently in the array.
	 */
	public int size() {
		return itemCt;
	}

	/**
	 * Adds a new item to the end of the array. The size increases by one.
	 */
	public void add(int item) {
		if (itemCt == items.length)
			items = Arrays.copyOf(items, 2 * items.length);
		items[itemCt] = item;
		itemCt++;
	}

	/**
	 * Removes the item at a given index in the array. The size of the array
	 * decreases by one. Items following the removed item are moved up one space in
	 * the array. Throws ArrayIndexOutOfBoundsException if the index is not valid.
	 */
	public void remove(int index) {
		if (index < 0 || index >= itemCt)
			throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
		for (int j = index + 1; j < itemCt; j++)
			items[j - 1] = items[j];
		itemCt--;
	}
} // end class DynamicArrayOfInt

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.

ArrayList

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 e tipi parametrici

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:

ArrayList<String> namelist = new ArrayList<String>();

ArrayList<Player> playerList = new ArrayList<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).

Programmare con ArrayList

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>.

import java.util.ArrayList;
import java.util.Scanner;

/**
* Reads a list of non-zero numbers from the user, then prints
* out the input numbers in the reverse of the order in which
* the were entered. There is no limit on the number of inputs.
*/

public class ReverseWithArrayList {

	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		
		ArrayList<Integer> list;
		list = new ArrayList<Integer>();
		System.out.println("Enter some non-zero integers. Enter 0 to end.");
		while (true) {
			System.out.print("? ");
			int number = scanner.nextInt();
			if (number == 0)
				break;
			list.add(number);
		}
		System.out.println();
		System.out.println("Your numbers in reverse are:");
		for (int i = list.size() - 1; i >= 0; i--) {
			System.out.printf("%10d%n", list.get(i));
		}
	}
}

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>.

Ricerca e Ordinamento su array

Ricerca

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:

/**
 * Searches the array A for the integer N. If N is not in the array, then -1 is
 * returned. If N is in the array, then the return value is the first integer i
 * that satisfies A[i] == N.
 */
static int find(int[] A, int N) {
	for (int index = 0; index < A.length; index++) {
		if (A[index] == N)
			return index; // N has been found at this index!
	}
	// If we get this far, then N has not been found
	// anywhere in the array. Return a value of -1.
	return -1;
}

Nel caso l'array di partensa sia giร  ordinato, posso utilizzare la ricerca binaria:

/**
 * Searches the array A for the integer N. Precondition: A must be sorted into
 * increasing order. Postcondition: If N is in the array, then the return value,
 * i, satisfies A[i] == N. If N is not in the array, then the return value is
 * -1.
 */
static int binarySearch(int[] A, int N) {
	int lowestPossibleLoc = 0;
	int highestPossibleLoc = A.length - 1;
	while (highestPossibleLoc >= lowestPossibleLoc) {
		int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
		if (A[middle] == N) {
			// N has been found at this index!
			return middle;
		} else if (A[middle] > N) {
			// eliminate locations >= middle
			highestPossibleLoc = middle - 1;
		} else {
			// eliminate locations <= middle
			lowestPossibleLoc = middle + 1;
		}
	}
	// At this point, highestPossibleLoc < LowestPossibleLoc,
	// which means that N is known to be not in the array. Return
	// a -1 to indicate that N could not be found in the array.
	return -1;
}

Lista associativa

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:


class PhoneEntry {
	String name;
	String number;
}
import java.util.Arrays;

/**
 * A PhoneDirectory holds a list of names with a phone number for each name. It
 * is possible to find the number associated with a given name, and to specify
 * the phone number for a given name.
 */
public class PhoneDirectory {

	private PhoneEntry[] data; // Array that holds the name/number pairs.
	private int dataCount; // The number of pairs stored in the array.

	/**
	 * Constructor creates an initially empty directory.
	 */
	public PhoneDirectory() {
		data = new PhoneEntry[1];
		dataCount = 0;
	}

	/**
	 * Looks for a name/number pair with a given name. If found, the index of the
	 * pair in the data array is returned. If no pair contains the given name, then
	 * the return value is -1. This private method is used internally in getNumber()
	 * and putNumber().
	 */
	private int find(String name) {
		for (int i = 0; i < dataCount; i++) {
			if (data[i].name.equals(name))
				return i; // The name has been found in position i.
		}
		return -1; // The name does not exist in the array.
	}

	/**
	 * Finds the phone number, if any, for a given name.
	 * 
	 * @return The phone number associated with the name; if the name does not occur
	 *         in the phone directory, then the return value is null.
	 */
	public String getNumber(String name) {
		int position = find(name);
		if (position == -1)
			return null; // There is no phone entry for the given name.
		else
			return data[position].number;
	}

	/**
	 * Associates a given name with a given phone number. If the name already exists
	 * in the phone directory, then the new number replaces the old one. Otherwise,
	 * a new name/number pair is added. The name and number should both be non-null.
	 * An IllegalArgumentException is thrown if this is not the case.
	 */
	public void putNumber(String name, String number) {
		if (name == null || number == null)
			throw new IllegalArgumentException("name and number cannot be null");
		int i = find(name);
		if (i >= 0) {
			// The name already exists, in position i in the array.
			// Just replace the old number at that position with the new.
			data[i].number = number;
		} else {
			// Add a new name/number pair to the array. If the array is
			// already full, first create a new, larger array.
			if (dataCount == data.length) {
				data = Arrays.copyOf(data, 2 * data.length);
			}
			PhoneEntry newEntry = new PhoneEntry(); // Create a new pair.
			newEntry.name = name;
			newEntry.number = number;
			data[dataCount] = newEntry; // Add the new pair to the array.
			dataCount++;
		}
	}
} // end class PhoneDirectory

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:

public class TestPhoneDirectory {

	public static void main(String[] args) {
		
		PhoneDirectory phoneDirectory = new PhoneDirectory();
		
		phoneDirectory.putNumber("Massimo", "223234332");
		phoneDirectory.putNumber("Carlo", "1111111111");
		
		String phoneNumber = phoneDirectory.getNumber("Massimo");
		
		System.out.println("phoneNumber Massimo: " + phoneNumber);
		
		phoneNumber = phoneDirectory.getNumber("Carlo");
		
		System.out.println("phoneNumber Carlo: " + phoneNumber);
		
		phoneNumber = phoneDirectory.getNumber("Gigi");
		
		System.out.println("phoneNumber: " + phoneNumber);
		
		// modifico numero telefono di Massimo
		phoneDirectory.putNumber("Massimo", "44444444");
		
		phoneNumber = phoneDirectory.getNumber("Massimo");
		
		System.out.println("Nuovo phoneNumber Massimo: " + phoneNumber);
	}

}

Dall'esecuzione di TestPhoneDirectory, il seguente output:

phoneNumber Massimo: 223234332
phoneNumber Carlo: 1111111111
phoneNumber: null
Nuovo phoneNumber Massimo: 44444444

Lista associativa in Java

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:

package withMap;

import java.util.HashMap;
import java.util.Map;

/**
 * A PhoneDirectory holds a list of names with a phone number for each name. It
 * is possible to find the number associated with a given name, and to specify
 * the phone number for a given name.
 */
public class PhoneDirectory {

	private Map<String, String> data; // Array that holds the name/number pairs.
	
	/**
	 * Constructor creates an initially empty directory.
	 */
	public PhoneDirectory() {
		data = new HashMap<>();
	}

	/**
	 * Finds the phone number, if any, for a given name.
	 * 
	 * @return The phone number associated with the name; if the name does not occur
	 *         in the phone directory, then the return value is null.
	 */
	public String getNumber(String name) {
		return data.get(name);
	}

	/**
	 * Associates a given name with a given phone number. If the name already exists
	 * in the phone directory, then the new number replaces the old one. Otherwise,
	 * a new name/number pair is added. The name and number should both be non-null.
	 * An IllegalArgumentException is thrown if this is not the case.
	 */
	public void putNumber(String name, String number) {
		if (name == null || number == null)
			throw new IllegalArgumentException("name and number cannot be null");
		
		data.put(name, number);
		
	}
} // end class PhoneDirectory

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.

Hash Table e Hash Code

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).

Ordinamento

Come abbiamo visto ci sono delle buone ragioni per ordinare un array. Vediamo due diversi algoritmi, tra i piรน semplici, di ordinamento.

Insertion sort

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.

/*
 * Precondition: itemsInArray is the number of items that are stored in A. These
 * items must be in increasing order (A[0] <= A[1] <= ... <= A[itemsInArray-1]).
 * The array size is at least one greater than itemsInArray. Postcondition: The
 * number of items has increased by one, newItem has been added to the array,
 * and all the items in the array are still in increasing order. Note: To
 * complete the process of inserting an item in the array, the variable that
 * counts the number of items in the array must be incremented, after calling
 * this subroutine.
 */
static void insert(int[] A, int itemsInArray, int newItem) {
	int loc = itemsInArray - 1; // Start at the end of the array.
	/*
	 * Move items bigger than newItem up one space; Stop when a smaller item is
	 * encountered or when the beginning of the array (loc == 0) is reached.
	 */
	while (loc >= 0 && A[loc] > newItem) {
		A[loc + 1] = A[loc]; // Bump item from A[loc] up to loc+1.
		loc = loc - 1; // Go on to next location.
	}
	A[loc + 1] = newItem; // Put newItem in last vacated space.
}

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.

static void insertionSort(int[] A) {
		// Sort the array A into increasing order.
		int itemsSorted; // Number of items that have been sorted so far.
		for (itemsSorted = 1; itemsSorted < A.length; itemsSorted++) {
			// Assume that items A[0], A[1], ... A[itemsSorted-1]
			// have already been sorted. Insert A[itemsSorted]
			// into the sorted part of the list.
			int temp = A[itemsSorted]; // The item to be inserted.
			int loc = itemsSorted - 1; // Start at end of list.
			while (loc >= 0 && A[loc] > temp) {
				A[loc + 1] = A[loc]; // Bump item from A[loc] up to loc+1.
				loc = loc - 1; // Go on to next location.
			}
			A[loc + 1] = temp; // Put temp in last vacated space.
		}
	}

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:

Selection sort

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.

static void selectionSort(int[] A) {
		// Sort A into increasing order, using selection sort
		for (int lastPlace = A.length - 1; lastPlace > 0; lastPlace--) {
			// Find the largest item among A[0], A[1], ...,
			// A[lastPlace], and move it into position lastPlace
			// by swapping it with the number that is currently
			// in position lastPlace.
			int maxLoc = 0; // Location of largest item seen so far.
			for (int j = 1; j <= lastPlace; j++) {
				if (A[j] > A[maxLoc]) {
					// Since A[j] is bigger than the maximum weโ€™ve seen
					// so far, j is the new location of the maximum value
					// weโ€™ve seen so far.
					maxLoc = j;
				}
			}
			int temp = A[maxLoc]; // Swap largest item with A[lastPlace].
			A[maxLoc] = A[lastPlace];
			A[lastPlace] = temp;
		} // end of for loop
	}

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.

/**
 * Sorts the cards in the hand so that cards of the same suit are grouped
 * together, and within a suit the cards are sorted by value. Note that aces are
 * considered to have the lowest value, 1.
 */
public void sortBySuit() {
	ArrayList<Card> newHand = new ArrayList<Card>();
	while (hand.size() > 0) {
		int pos = 0; // Position of minimal card.
		Card c = hand.get(0); // Minimal card.
		for (int i = 1; i < hand.size(); i++) {
			Card c1 = hand.get(i);
			if (c1.getSuit() < c.getSuit() 
				|| (c1.getSuit() == c.getSuit() && c1.getValue() < c.getValue())) {
				pos = i; // Update the minimal card and location.
				c = c1;
			}
		}
		hand.remove(pos); // Remove card from original hand.
		newHand.add(c); // Add card to the new hand.
	}
	hand = newHand;
}

Unsorting

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:

/**
 * Postcondition: The items in A have been rearranged into a random order.
 */
static void shuffle(int[] A) {
	for (int lastPlace = A.length - 1; lastPlace > 0; lastPlace--) {
		// Choose a random location from among 0,1,...,lastPlace.
		int randLoc = (int) (Math.random() * (lastPlace + 1));
		// Swap items in locations randLoc and lastPlace.
		int temp = A[randLoc];
		A[randLoc] = A[lastPlace];
		A[lastPlace] = temp;
	}
}

Sorting in Java

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.

Array Multidimensionali

Sono creati come array di array. Esempio di array bidimensionale:

int[][] A = new int[3][4];

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:

int[][] A = { {1, 0, 12, -1}, 
                {7, -3, 2, 5}, 
                {-5, -2, 2, -9}
                };

oppure si puรฒ essegnare:

A =  new int[][]{ {1, 0, 12, -1}, 
                {7, -3, 2, 5}, 
                {-5, -2, 2, -9}
                };

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.

Array & ArrayList
Ricerca, Ordinamento e array associativi
contenitori
Contenitori
Contenitori
Esempio liste associative
Esempio carte
Esempio carte
java.lang.Comparable.compareTo(T)
java.util.Comparator.compare(T, T)
java.util.Arrays
java.util.Collections
Esempio carte
improved.Hand
Array di tipi primitivi
Array di tipi reference
hash table