PDF de programación - Colecciones

Colecciones

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y Computación

Universidad Complutense de Madrid

23 de abril de 2007

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Jerarquía de clases de colecciones

List

Collection

Set

SortedSet

AbstractCollection

AbstractList

AbstractSet

AbstractSequentialList

ArrayList

Vector

HashSet

TreeSet

LinkedList

Stack

Cloneable

Serializable

RandomAccess

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Colecciones

Collection Grupo de objetos.

Set Concepto matemático. El orden no importa, no hay

repeticiones. SortedSet.

List El orden es importante, admite repeticiones.

Map Concepto de función matemática. SortedMap

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Jerarquía de clases: Map

Map

SortedMap

AbstractMap

HashMap

IdentityHashMap

∗

WeakHashMap

∗

TreeMap

LinkedHashMap

Cloneable

Serializable

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Interfaz Collection

public i n t e r f a c e Collection <E > e x t e n d s Iterable <E > {

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
b o o l e a n add ( E e l e m e n t );
Iterator <E > i t e r a t o r ();
. . . . . . . . . . . . . . . . . . . . . . . . . .
Object [] t o A r r a y ();
<T > T [] t o A r r a y ( T [] a );

}

1
2
3
4
5
6
7
8

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Interface Iterador

public I n t e r f a c e I t e r a t o r {
public b o o l e a n h a s N e x t ();
public Object next ();
void

remove ();

}

1
2
3
4
5

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Uso de listas

p r i v a t e static List l e e P u n t o s ( String f i c h e r o )

throws F i l e N o t F o u n d E x c e p t i o n , I O E x c e p t i o n {

B u f f e r e d R e a d e r lector = new B u f f e r e d R e a d e r ( new F i l e R e a d e r ( f i c h e r o ));
List l i s t a P u n t o s = new L i n k e d L i s t ();
String datos = lector . r e a d L i n e ();
while ( datos != null ){

Punto p = new Punto ( datos );
l i s t a P u n t o s . add ( p );
datos = lector . r e a d L i n e ();

}
return l i s t a P u n t o s ;

}

p r i v a t e static void a n a l i z a L i s t a P u n t o s ( List c ){

I t e r a t o r itr = c . i t e r a t o r ();
int i =1;
while ( itr . h a s N e x t ()){

Punto p = ( Punto ) itr . next ();
. . . . . . . . . . . . . . . . . . . . . . . . . . .

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13

1
2
3
4
5
6
7
8

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Errores en tiempo de ejecución

¿Qué pasaría si añadiera un objeto que no sea de clase Punto?

Lista lista = l e e P u n t o s ( f i c h e r o );
lista . add ( new Recta ( new Punto (0 ,0) , new Punto (1 ,0)));
a n a l i z a P u n t o s ( lista );

La línea

Punto p = ( Punto ) itr . next ();

lanzaría un java.lang.ClassCastException.

1
2
3

1

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Clases genéricas

public I n t e r f a c e List <E > {

......
public Iterator <E > i t e r a t o r ()
.....

}

public I n t e r f a c e Iterator <E > {

public b o o l e a n h a s N e x t ();
public E next ();
void

remove ();

}

1
2
3
4
5

1
2
3
4
5

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Uso de listas con genéricos

p r i v a t e static List < Punto > l e e P u n t o s ( String f i c h e r o )

throws F i l e N o t F o u n d E x c e p t i o n , I O E x c e p t i o n {

B u f f e r e d R e a d e r lector = new B u f f e r e d R e a d e r ( new F i l e R e a d e r ( f i c h e r o ));
List < Punto > l i s t a P u n t o s = new LinkedList < Punto >();
String datos = lector . r e a d L i n e ();
while ( datos != null ){

Punto p = new Punto ( datos );
l i s t a P u n t o s . add ( p );
datos = lector . r e a d L i n e ();

}
return l i s t a P u n t o s ;

}

p r i v a t e static void a n a l i z a L i s t a P u n t o s ( List < Punto > c ){

Iterator < Punto > itr = c . i t e r a t o r ();
int i =1;
while ( itr . h a s N e x t ()){

Punto p = itr . next ();
. . . . . . . . . . . . . . . . . . . . . . . . . . .

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13

1
2
3
4
5
6
7
8

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Errores en tiempo de compilación

¿Qué pasaría si añadiera un objeto que no sea de clase Punto?

Lista < Punto > lista = l e e P u n t o s ( f i c h e r o );
lista . add ( new Recta ( new Punto (0 ,0) , new Punto (1 ,0)));

1
2

No compila, la lista es de puntos y puedo añadir rectas.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Interfaz Collection

public i n t e r f a c e Collection <E > e x t e n d s Iterable <E > {

int size ();
b o o l e a n i s E m p t y ();
b o o l e a n c o n t a i n s ( Object e l e m e n t );
b o o l e a n add ( E e l e m e n t );
b o o l e a n remove ( Object e l e m e n t );
Iterator <E > i t e r a t o r ();

b o o l e a n c o n t a i n s A l l ( Collection <? > c );
b o o l e a n addAll ( Collection <? e x t e n d s E > c );
b o o l e a n r e m o v e A l l ( Collection <? > c );
b o o l e a n r e t a i n A l l ( Collection <? > c );
void clear ();

Object [] t o A r r a y ();
<T > T [] t o A r r a y ( T [] a );

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Los métodos contains y remove comparan los objetos según el
método equals.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Interfaz Set

No añade métodos.

No puede haber elementos repetidos.

Subclases

HashSet La mejor en eficiencia, los iteradores no garantizan el

orden. Método hashCode en la clase Object.

TreeSet Implementación con árboles roji-negros. Los

iteradores recorren el conjunto según el orden
establecido por sus elementos

LinkedHashSet Otra implementación de las tablas hash.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Método equals

Definido en la clase Object. Hay que sobreescribirlo si se va a usar
una clase como elemento de una colección.

Debe ser una relación de orden: o1!=null, o2!=null y
o3!=null

Reflexivo o1.equals(o1)
Simétrico o1.equals(e2)==o2.equals(e1)
Si o1.equals(o2) y o2.equals(o3) entonces
o1.equals(o3)

Si o!=null entonces o.equals(null)==false.

Debe ser consistente: distintas invocaciones a lo largo de un
programa debe dar el mismo resultado si no cambian el valor
de los objetos.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Método hashCode

Definido en la clase Object. Hay que sobreescribirlo si se va a usar
una clase como elemento de una colección tipo hash.

Debe ser consistente.

Si o1.equals(o2), entonces o1.hashCode()=o2.hashCode.

No debe ser necesariamente inyectiva, dos objetos distintos
pueden tener el mismo valor.

Debería distribuir uniformemente los objetos.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Método CompareTo

public class Fecha i m p l e m e n t s Comparable < Fecha > , C l o n e a b l e {

. . . . . . . . . . . . . . . .
public int c o m p a r e T o ( Fecha f ) {

....

}
. . . . . . . . . .

}

Implementa relación de orden

1
2
3
4
5
6
7

x .compareTo

< 0 si x < y
= 0 si x = y
> 0 si x > y




Debe ser implementada para tener colecciones ordenadas.

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

Método CompareTo

sgn(x.compareTo(y)) == -sgn(y.compareTo(x)).
Debe ser reflexiva antisimétrica y transitiva, para objetos no
nulos

si x.compareTo(x)==0.
si x.compareTo(y)<=0 y y.compareTo(x)<=0 entonces
x.compareTo(z)==0 y z.compareTo(x)==0.
si x.compareTo(y)<=0 y y.compareTo(z)<=0 entonces
x.compareTo(z)<=0.

Debe ser consistente con el resto de los objetos. Si
x.compareTo(y)==0 entonces para todo z entonces
sgn(x.compareTo(z)) == sgn(y.compareTo(z)).

es conveniente que sea consistente con equals: x.equals(y)
sii x.compareTo(y)==0

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

PrColeccion

public class P r C o l e c c i o n {

public static void lee ( String nombre , Collection < String > c o n j u n t o )

throws I O E x c e p t i o n {
B u f f e r e d R e a d e r reader = null ;
try {

reader = new B u f f e r e d R e a d e r ( new F i l e R e a d e r ( nombre ));
String linea = reader . r e a d L i n e ();
while ( linea != null ) {

c o n j u n t o . add ( linea );
linea = reader . r e a d L i n e ();

}

} f i n a l l y {

if ( reader != null ) {
reader . close ();

}

}

}
public static void m u e s t r a ( Collection < String > c o n j u n t o ) {

for ( String s : c o n j u n t o ) {

System . out . p r i n t l n ( s );

}

}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Luis Fernando Llana Díaz

Departamento de Sistemas Informáticos y ComputaciónUniversidad Complutense de Madrid

Colecciones

PrConjunto

public class P r C o n j u n t o {

public static void main ( String [] args ) throws E x c e p t