Genericidad y Java Collections
Programación II
Dr. Javier Nieves Acedo
Jouuu, estamos aprendiendo un montón
en Programación II !!!!!!
Utilizamos herramientas
potentes en nuestros programas
Pero siempre necesitamos usar
lo mismo…
Genericidad (generics) (1)
 Problema
 Al trabajar con contenedores (Collection)
estamos obligados a hacer casting continuo:
static void quitaVacios(Collection c) {
for (Iterator i = c.iterator();
i.hasNext(); )
if (((String) i.next()).length() == 0)
i.remove();
}
 Esto es incómodo y también inseguro
(puede generar un error en ejecución)
Genericidad (generics) (2)
 La genericidad permite informar al compilador
del tipo de la colección, de modo que puede ser
chequeado en compilación, y evita el cast:
static void quitaV(Collection<String> c) {
for (Iterator<String> i = c.iterator();
i.hasNext(); )
if ((i.next()).length() == 0)
i.remove();
}
Genericidad (generics) (3)
 El uso de la genericidad obliga a que todos los
elementos de la colección sean ahora de la clase
indicada entre < y > (String en el ejemplo)
 Similar al “template” de C++
 Las colecciones (las vemos después) no son el
único uso de la genericidad, se pueden usar en
otros puntos (aunque programar nuevas clases
genéricas es complejo)
Genericidad (generics) (4)
 La genericidad en Java 1.5 afecta a todas las
clases contenedoras, como List, Vector, Tree...
 Una clase puede ser genérica sobre un tipo...
 Vector<E>
(ej. Vector<Integer>)
 ArrayList<E>
(ej. ArrayList<Persona>)
 O sobre varios...
 HashMap<K,V>

(ej. HashMap<Integer,Persona>)
Genericidad (generics) (5)
 Además, los tipos genéricos pueden “anidarse”
si son contenedores:
 ArrayList<Persona>
 ArrayList<ArrayList<Persona>>
 ArrayList<HashMap<String,Persona>>
 Con lo que pueden conseguirse estructuras de
datos muy completas muy fácilmente
La versión 1.7 proporciona
mejoras
Genericidad (generics) (6)
 Inferencia de tipos genéricos
Map<String, List<String>> myMap
= new HashMap<String, List<String>>();
// En Java SE 7 se puede poner el "diamond" <>:
Map<String, List<String>> myMap = new HashMap<>();
Tenemos
nuevos bucles
Bucle For-Each (1)
 Relacionado con las colecciones, se permite
un nuevo tipo de bucle. Para evitar la pesada
construcción:
for (Iterator i = palos.iterator();
i.hasNext();) {
Palo palo = (Palo) i.next();
...
}
 Se puede utilizar un nuevo tipo de for:
for (Palo palo: palos) {
...
}
Bucle For-Each (2)
 El símbolo “:” se lee “en”
 Pueden anidarse bucles sin problema:
for (Palo p : listaPalos)
for (Numero n : listaNumeros)
baraja.add( new Carta(p,n) );
 Y la construcción es aplicable a arrays:
int sumaArray(int[] a) {
int res = 0;
for (int i : a)
res += i;
return res;
}
 En general, for-each puede utilizarse siempre que no
se modifica la colección según se recorre (para ese
caso hay que volver al esquema tradicional)
Y otro nuevo concepto, el
boxing
Boxing
 Donde se espere un objeto no se puede poner un valor
primitivo (p. ej. lista de enteros)
 Solución: wrappers (Integer en vez de int)
 Problema: código muy “sucio”:
LinkedList l = new LinkedList();
l.add( new Integer(i) );
...
int j = ((Integer) l.get(0)).intValue();
 Java 1.5 incorpora autoboxing (convertir primitivo al
wrapper) y unboxing (convertir el wrapper a primitivo) de
forma transparente:
l.add( i );
...
int j = l.get(0);
Y si conocemos la
lista de elementos
Enumeraciones (1)
 Java 1.4 no permite enumeraciones, lo que obliga a
utilizar constantes:
public
public
public
public
static
static
static
static
final
final
final
final
int
int
int
int
PRIMAVERA
VERANO
OTOÑO
INVIERNO
=
=
=
=
0;
1;
2;
3;
 Esto presenta múltiples problemas:
 No hay un tipo diferenciado (podría pasarse cualquier otro
entero por error)
 No hay nombres diferenciados (podrían confundirse con
otros nombres)
 No hay información (cada valor es un número, sin relación
con su “significado”)
 Los lenguajes modernos mejoran esto con las
enumeraciones, y Java las incorpora en su versión 1.5.
Enumeraciones (2)
 En Java 1.5 esta enumeración se haría:
enum Estacion { PRIMAVERA, VERANO, OTOÑO, INVIERNO }
 Esta declaración define una NUEVA CLASE





Puede redefinir métodos de Object
Puede añadir métodos propios
Se visualiza como el string del nombre, no como un entero
Es Comparable y Serializable...
Automáticamente crea objetos de ese tipo, uno por cada valor de la
enumeración, con esos nombres
 Veamos un ejemplo
Enumeraciones (3)
public class Carta {
public enum Rango { DOS, TRES, CUATRO, CINCO, SEIS, SIETE,
SOTA, CABALLO, REY, AS }
public enum Palo { OROS, COPAS, ESPADAS, BASTOS }
Rango rango;
Palo palo;
public Carta(Rango r, Palo p) {
rango = r;
palo = p;
}
public String toString() { return rango + " de " + palo; }
public static List<Carta> baraja = new ArrayList<Carta>();
}
// Inicialización ...
public void static main (String s[]) {
for (Palo p : Palo.values())
for (Rango r : Rango.values())
baraja.add(new Carta(r,p));
}
Además, tenemos
más cosas
Parámetros variables - varargs (1)
 Java 1.4 no permite número de parámetros
variable
 Se puede simular pasando varios objetos dentro
de un único array de objetos
 Java 1.5 permite indicar parámetros múltiples
con puntos susp.:
public static int suma( Integer... listaEnts ) {
int sum = 0;
for (Integer i : listaEnts) {
sum += i; //combinado con unboxing
}
return sum;
}
Parámetros variables - varargs (2)
 Se comporta como un array de parámetros
 Con lo que podríamos hacer
int i = Arit.suma( 1, 2, 3 );
// autoboxing
int j = Arit.suma( 5, 10, 15, 20, 25, 30 );
...
 Se incorpora un nuevo método printf
Importación estática
 Los nombres estáticos (las antiguas variables y
funciones “globales”) obligan a abusar de los
prefijos de nombres de clase. Por ejemplo:
import java.lang.Math;
...
double r = Math.cos(Math.PI * alfa);
 Java 1.5 facilita este proceso permitiendo
importar también nombres de atributos y
métodos estáticos, para evitar el prefijo de
clase:
import static java.lang.Math.*;
// podría ser uno a uno:
//
import static java.lang.Math.PI;
...
double r = cos(PI * alfa);
¿Qué
son las Java Collections?
Es una serie de funcionalidades,
incluida en el API de Java…
… sobre
contenedores…
… que nos va a permitir NO
programar más un
contenedor…
… pero hay que aprender a
utilizar sus funciones…
… y va a ser muy
fácil…
… y para
comenzar…
… una
vista general…
Visión General (1)
 Las colecciones, contenedores
 Objetos que sirven para agrupar objetos.
 Se utilizan para almacenar, recoger, manipular
y comunicar datos.
 Representan grupos naturales
 Carpeta de documentos
 Directorio de contactos
 Empleados de una planta
Visión General (2)
 Las colecciones, contenedores
 Imprescindibles en todos los lenguajes.
 Permiten que organicemos nuestra
información.
 La colección más básica es el array (y el fichero en
memoria secundaria)
 En Java 1.2 se incorporan vector y Hashtable
 En Java 1.5 se introduce el framework completo de
Collections
Veamos las
Java Collections
Framework Java Collections (1)
 Arquitectura para manejar
contenedores en Java (desde la 1.5)
Interfaces (representaciones abstractas)
Implementaciones (clases instanciables)
Algoritmos (búsqueda, ordenación
 Es del estilo de la STL de C++
Framework Java Collections (2)
 De amplio espectro
Se pueden usar en muchos casos
concretos
Hay que conocerlas bien
 El API de Java será nuestra herramienta
Java Collections – Interfaces (1)
 Las interfaces son la semántica de
agrupación
 Tienen diferentes usos
 Son interfaces abstractos
 Forman dos jerarquías
Java Collections – Interfaces (2)
 Todas las colecciones son genéricas
 Los tipos se controla en compilación
 También pueden hacerse polimórficas
conteniendo a su vez clases padre o interfaces.
 Para simplificar, las variantes de
implementación no está incluidas en los
interfaces
Java Collections – Interfaces (3)
 Las variantes de implementación son 3:
 Innmutables, tamaño fijo, append-only
 Las diferencias se introducen como
métodos opcionales
 “optional” indicado en la documentación
 Cada clase puede o no soportarlos
 Si se llaman y no están, excepción
UnsupportedOperationException
Java Collections – Interfaces (4)
 Collection: Agrupación de elementos
 Set (conjunto): colección sin duplicados
 SortedSet: Ordenado por valor (comparación)
 List (lista, secuencia): Colección ordenada por
posición (estilo array). Puede tener duplicados.
 Queue (cola): Almacén ordenado de elementos hasta
su proceso
Java Collections – Interfaces (5)
 Map: Agrupación de emparejamientos
clave-elemento (sin duplicados)
 SortedMap: Ordenado por clave
Java Collections – Implementaciones (1)
 Las clases que permiten hacer todo
son:
Java Collections – Implementaciones (2)
 Lo habitual será utilizar:
Set: HashSet
 SortedSet: TreeSet
List: ArrayList
Map: HashMap
 SortedMap: TreeMap
Queue: LikedList (FIFO)
 No están sincronizadas (threads)
Java Collections – Implementaciones (3)
 Funciona con wrappers para cambios
 Se crea una segunda colección que envuelve a la
original con otras características.
 Sincronización de hilos
List<Nombre> ln = Collections.synchronizedList(
new ArrayList<Nombre>() );
 No modificables (no cambian los objetos)
List<Nombre> ln = Collections.unmodifiableList(
new ArrayList<Nombre>() );
 Otras especializadas
Java Collections – Implementaciones (4)
 Vista de un array como una List
Nombre[] vNoms = new Nombre[100];
(...)
List<Nombre> lNoms = Arrays.asList( vNoms );
 No permite modificar, es solo la visualización
 Si se necesita el paso de un valor vacío, existen
constantes para ello
 Collections.emptySet()
 Collections.emptyList()
 Collections.emptyMap()
Hablemos ahora de la
ordenación…
Java Collections – Ordenación (1)
 Algunos tipos son ordenados y otros
permiten ordenar
List l = ...
Collections.sort( l );
Imprescindible implementar
Comparable<T>
public int compareTo( T o );
Hay clases básicas comparables
 Boolean, Byte, Character, Long, Integer,
Short, Double, Float, BigInteger…
Java Collections – Ordenación (2)
 Podemos definir las nuestras
import java.util.*;
public class Nombre implements Comparable<Nombre> {
private final String nombre, apellidos;
public Nombre(String nombre, String apellidos) {
if (nombre == null || apellidos == null)
throw new NullPointerException();
this.nombre = nombre;
this.apellidos = apellidos;
}
public String nombre() { return nombre; }
public String apellidos() { return apellidos; }
public boolean equals(Object o) {
if (!(o instanceof Nombre)) return false;
Nombre n = (Nombre) o;
return n.nombre.equals(nombre) &&
n.apellidos.equals(apellidos);
}
Java Collections – Ordenación (3)
public int hashCode() {
// objetos iguales (equals) deben tener hash iguales
return 31*nombre.hashCode() + apellidos.hashCode();
}
public String toString() {
return nombre + " " + apellidos;
}
public int compareTo(Nombre n) {
int ultimaCmp = apellidos.compareTo(n.apellidos);
return (ultimaCmp != 0 ? ultimaCmp :
nombre.compareTo(n.nombre));
}
}
Java Collections – Ordenación (3)
 ¿Cómo se ordena?
Nombre n1, n2, n3, n4, n5;
// Uso 1: explícita (ALGORITMO) de Collections
ArrayList<Nombre> ln = new ArrayList<Nombre>();
ln.add( n1 = new Nombre( "Buzz", "Lightyear" ));
ln.add( n2 = new Nombre( "Woody", "Allen" ));
ln.add( n3 = new Nombre( "Tim", "Burton" ));
ln.add( n4 = new Nombre( "Richard", "Marx" ));
ln.add( n5 = new Nombre( "Groucho", "Marx" ));
Collections.sort( ln );
System.out.println( ln );
[Woody Allen, Tim Burton, Buzz Lightyear, Groucho Marx,
Richard Marx]
Java Collections – Ordenación (4)
 ¿Cómo se ordena?
// Uso 2 de ordenación: en estructura ordenada
TreeSet<Nombre> sn = new TreeSet<Nombre>();
sn.add( n1 );
sn.add( n2 );
sn.add( n3 );
sn.add( n4 );
sn.add( n5 );
System.out.println( sn );
[Woody Allen, Tim Burton, Buzz Lightyear, Groucho Marx,
Richard Marx]
 Los tipos T incluidos en TreeSet y TreeMap deben
implementar Comparable<T>
¿Y si queremos
más de un orden?
Java Collections – Ordenación (4)
 Solo podemos implementar un Comparable
 Para ello necesitamos crear un comparador
específico a utilizar
static final Comparator<Nombre> ORDEN_DE_NOMBRE =
new Comparator<Nombre>() {
public int compare(Nombre n1, Nombre n2) {
return n1.nombre.compareTo(n2.nombre);
}
};
(...)
Collections.sort( ln, ORDEN_DE_NOMBRE );
System.out.println( ln );
[Buzz Lightyear, Groucho Marx, Richard Marx, Tim Burton, Woody
Allen]
Java Collections – Otros algoritmos (1)
 Hay una serie de algoritmos genéricos que
nos permite trabajar con los contenedores.
 Todos están en la clase Collections
 Ordenación
 sort(list)
 sort(list, Comparator)
 Desordenación
 shuffle(list)
Java Collections – Otros algoritmos (2)
 Manipular datos
 Invertir posición: reverse(list)
 Rellenar de un valor: fill(list)
 Copiar de una lista a otra: copy(list1, list2)
 Intercambiar elementos: swap(list, ind1, ind2)
 Añadir varios elementos: addAll(list, elementos…)
 Buscar valores extremos
 Mínimo: min
 Máximo: max
Java Collections – Otros algoritmos (3)
 Buscar datos
 Búsqueda en lista ordenada:
binarySearch(list, elem)
 Búsqueda por orden específico:
binarySearch(list, elemen, Comparator)
 Composición:
 Contar elementos: frequency
(colección, elemn)
 Comprobar que no hay elementos comunes:
disjoint(coleccion1, coleccion2)
Hablemos de una
situación concreta
Java Collections – Problemática (1)
 ¿Cómo guardar una serie no prefijada de objetos para
poderlos buscar rápido?
 Coste lineal (porporcional al número de elementos)
¿dni
57575757F?
0
1
2
3
4
5
...
n
74524344G Emilio L...
12534244A Ana Mar...
58966321Z Luis Ort...
98673212G Aitziber I...
55426992L Aitor Zu...
43598824V Inma Esc...
Java Collections – Problemática (2)
 Solución 1: Ordenándolos
 Coste logarítmico, la inserción también lo es.
 ¿Se puede hacer más rápido?
¿dni
57575757F?
0
1
2
3
4
5
...
n
12534244A Ana Mar...
43598824V Inma Esc...
55426992L Aitor Zu...
58966321Z Luis Ort...
74524344G Emilio L...
98673212G Aitziber
I...
Java Collections – Problemática (1)
 Solución 2: Tablas hash
 Coste mínimo y fijo (en el mejor de los casos)
 ¿Qué hace falta para el hash? – Una función hash
¿dni
57575757F?
hash
0
1
2
3
4
5
...
n
74524344G Emilio L...
12534244A Ana Mar...
58966321Z Luis Ort...
98673212G Aitziber I...
55426992L Aitor Zu...
43598824V Inma Esc...
Java Collections – Función Hash (1)
 Pone cualquier objeto (clave) en una
posición fija de índice
 Convierte una clave o valor de un rango
muy grande en un valor único en un
rango prefijado.
 Búsqueda: se calcula el hash y si el objeto
está solo puede estar en esa posición
 Inserción: se calcula el hash y se deja el
objeto en esa posición
Java Collections – Función Hash (2)
 Pero hay un problema, las colisiones
 Por muy buena que sea la función de hash es
imposible que un rango “grande” de objetos
quepa en un rango menor sin repeticiones
(colisiones)
 Se resuelven aprovechando huecos cercanos o
almacenándolas en listas de colisiones
Java Collections – Función Hash (3)
 En Java todo es “hasheable”
public int hashCode()
// clase Object!!!
 Si queremos usar nuestras clases en estructuras
hash… (HashSet, HashMap…)
 Reimplementamos hashCode() con una función
sensata de distribución.
 Reimplementamos equals(Object) cumpliendo que
si tienen el mismo hashCode se devuelve true.
 equals y hashCode deben depender de una serie de
atributos fijos que determinan la clave.
Adiós a los arrays,
hola Java Collections
Ya vamos teniendo todo preparado,
queda poco para…
3, 2, 1…
a
volar…
Genericidad y Java Collections
Programación II
Dr. Javier Nieves Acedo
Descargar

Slides