Array, ArrayList e Hash Table

Approfondimento su array e array dinamici

Slide argomento: Array & ArrayList e Ricerca, Ordinamento e array associativi.

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 contenitori, 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 primitivi

• 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();

Array di tipi reference

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

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

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

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

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.

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 codice Esempio liste associative 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 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;
}

Vedi Card.java e Hand.java il Esempio carte per il codice completo.

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

Vedi classe Deck.java per utilizzo del metodo shuffle() per mischiare le carte di un mazzo, in Esempio carte.

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.

Vedi: java.lang.Comparable.compareTo(T), java.util.Comparator.compare(T, T) e le classi java.util.Arrays e java.util.Collections, per i metodi di sort su array e collezioni.

In Esempio carte, sotto la classe improved.Hand utilizza java.util.Collections.sort() e java.util.Comparator per eseguire l'ordinamento.

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.