Download Informática III

Informática 5260
Contenedores Asociativos:
SET
MAP
Contenedores asociativos (1)
Los contenedores asociativos son una
extensión de las secuencias. Mientras que en
estas para acceder a los elementos solo pueden
utilizarse claves numéricas, que señalan el
número de orden del elemento dentro de la
secuencia (al estilo de los índices en las
matrices).
Los contenedores asociativos admiten cualquier
tipo de clave de acceso. Las más frecuentes son
las cadenas alfanuméricas (strings).
Contenedores asociativos (2)
 Las asociaciones almacenan sus miembros en forma
de árbol indexado, razón por la que son denominados
también contenedores asociativos ordenados, y resultan
adecuados para accesos aleatorios mediante claves.
 La ordenación se realiza según los valores de ciertos
miembros del contenedor. Estos elementos son
denominados "de claves" ("Key values"). Lo que exige
que los objetos "de clave" sean de un tipo para el que
estén definidos los operadores relacionales. El
contenedor es mantenido ordenado de forma
automática por los algoritmos de inserción y borrado.
Contenedores asociativos (3)
 Un contenedor asociativo almacena objetos de forma
ordenada basandose en una llave. La llave puede ser el
propio objeto (como es el caso de los conjuntos) o ser
otro tipo completamente diferente (como en el caso de
los diccionarios).
 Existen cuatro tipos de contenedores asociativos:
sin llaves repetidas
con llaves repetidas
llave
set
multiset
llave + datos
map
multimap
Contenedores asociativos (4)
Tanto los set y los map se pueden
implementar usando las clases contenidas en
la JAVA COLLECTIONS FRAMEWORK (JCF).
En cambio, multiset y multimap se
implementan de una forma mas cómoda y
eficiente usando las clases del Proyecto
Guava, anteriormente conocido como Google
Collections.
La interface Set
 Colección que no puede contener elementos
duplicados. Abstracción del concepto
matemático de conjunto.
 Contiene los métodos heredados de Collection.
 Sólo añade restricciones para prohibir
elementos duplicados.
 Los elementos no están ordenados
La interface Set
 La interface Set representa un conjunto de
objetos, lo cual significa que cada elemento puede
existir solamente una vez en el Set.
 Implementaciones de Set: Al ser un subtipo de
Collection, todos los métodos de Collection se
encuentran disponibles en Set.
 Como Set es una interface, es necesario instanciar
una implementación concreta de la interfaz para
poder usarla.
La interface Set
 Existen varias clases en el API de Java que
implementan la interfaz Set:
CLASES:
• java.util.EnumSet
• java.util.HashSet
• java.util.LinkedHashSet
• java.util.TreeSet
EJEMPLOS:
Set setA = new EnumSet();
Set setB = new HashSet();
Set setC = new LinkedHashSet();
Set setD = new TreeSet();
Cada una de estas implementaciones se comporta de manera ligeramente
distinta respecto al orden de los elementos cuando se itera el Set, y en el
tiempo que toma el insertar y agregar elementos a los sets.
La interface Set
 HashSet es respaldado por un HashMap. No garantiza
la secuencia de los elementos cuando éstos son
iterados.
 LinkedHashSet difiere de un HashSet , ya que
garantiza que el orden de los elementos durante la
iteración es el mismo orden en el cual fueron insertados.
 Reinsertar un elemento que ya se encontraba en el
LinkedHashSet no cambia su orden.
La interface Set
 TreeSet también garantiza el orden de los elementos al
iterarlos, pero el orden es el orden de ordenamiento de
los elementos. En otras palabras, el orden en el cual
dichos elementos se almacenarían si se utilizara el
método Collections.sort() en una lista o arreglo que
contenga dichos elementos.
 Este orden es determinado por su orden natural (si
implementan la interfaz Comparable) o mediante un
comparador (Comparator) específico para la
implementación.
Uso de Set
Set set = new HashSet(); // instancia de un set concreto
// ...
set.add(obj); // inserta elementos
// ...
int n = set.size(); // obtiene tamaño
// ...
if (set.contains(obj)) {...} // verifica miembro
// iterata a través del set
Iterator iter = set.iterator();
while (iter.hasNext()) {
Object e = iter.next();
// downcast e
// ...
}
Métodos más Usados
de la Interface Set






add(i,o) Inserta o en la posición i
add(o) Añade o al final
get(i)
Devuelve el i-ésimo elemento
remove(i) Eliminia e i-ésimo elemento
remove(o) Elimina el elemento o
set(i,o)
Remplaza el i-ésimo
elemento con o
Ejemplo1: Set
 Cuando se iteran los elementos de un Set el orden de
los elementos depende de cuál implementación de Set
se utilice como se mencionó anteriormente. Un ejemplo
de sus uso sería:
Set setA = new HashSet();
setA.add("elemento 0");
setA.add("elemento 1");
setA.add("elemento 2");
Ejemplo2: Set
// acceso mediante iterador
Iterator iterador = setA.iterator();
while(iterador.hasNext(){
String elemento = (String) iterador.next();
}
// acceso mediante ciclo for
for(Object objecto : setA) {
String elemento = (String) objecto;
}
 Los elementos se remueven llamando al método remove(Object o).
No hay manera de remover un objeto mediante un índice en un Set,
ya que el orden de los elementos depende de la implementación.
Ejemplo2: Set
import java.util.*;
public class FindDups {
public static void main(String args[]) {
Set s = new HashSet();
for (int i=0; i<args.length; i++)
if (!s.add(args[i]))
System.out.println(" duplicado: "+args[i]);
System.out.println(s.size()+" palabras detectadas: "+s);
}
}
Sets Genéricos
 Por default se puede almacenar cualquier tipo de objeto
en un Set; sin embargo, es posible limitar el tipo de
objetos que se pueden insertar mediante el uso de
genéricos. Un ejemplo:
Set<MyObject> set = new HashSet<MyObject>();
 Este Set ahora únicamente puede tener instancias
MyObject dentro de él. Se puede acceder e iterar sus
elementos sin realizar casting:
for(MyObject anObject : set){
//do someting to anObject...
}
Interface SortedSet
 Conjunto que mantiene los elementos ordenados en
forma ascendente
 los elementos deben implementar Comparable o
 se debe suministrar un Comparator en el
momento de la creación
 Operaciones: Iterator atraviesa SortedSet en orden.
 Operaciones adicionales:
 de vista de rango
 se puede retornar el primer o el último elemento
 acceso al Comparator
Interface SortedSet
 En el API de Java existe únicamente una clase que
implementa SortedSet: java.util.TreeSet.
 Ejemplos sobre cómo instanciar un SortedSet:
SortedSet setOrdenadoA = new TreeSet();
Comparator comparador = new MyComparator();
SortedSet setOrdenadoB = new TreeSet(comparador);
La interface Map
 Colección de pares clave/valor (tabla-diccionario)
 No puede contener claves duplicadas
 Una clave puede mapear a lo sumo un valor
 Todo objeto puede ser usado como un clave de hash
 public int Object.hashcode()
 Objetos iguales (equals()) deben producir el mismo
hashcode
 Métodos que permiten ver al mapa como colección:
 keySet- Set de claves del mapa
 values- Collection de valores del mapa
 entrySet- Set de pares claves/valor del mapa
La
interfase
Map
 Los mapas almacenan objetos basados en
llaves únicas.
 Los mapas pueden soportar elementos
repetidos, pero no llaves repetidas.
 Esta clase no extiende de la interfase Collection
Implementaciones de Map
HashMap
- Usa el algoritmo de hashing para almacenar los
elementos.
- Una implementación de Map con una tabla hash.
- El método hashCode de cada clave se utiliza
para seleccionar un lugar en la tabla.
- Una colección de utilidad muy general con
tiempos relativamente cortos de búsqueda e
inserción.
Implementaciones de Map
TreeMap
 Provee un Mapa ordenado. Los elementos deben ser
ordenables, ya sea implementando la interfase
Comparable o utilizando la clase Comparator.
 Una implementación de SortedMap utilizando un árbol
binario equilibrado que mantiene sus elementos
ordenados por clave.
 Útil para conjuntos de datos ordenados que requieren
una búsqueda por clave moderadamente rápida.
- Asume que los elementos son comparables si no se le ha
pasado un comparator en el constructor.
Interface Map











Clear()
Elimina todos las asociaciones
containsKey(k) Si contiene una asoc. para k
containsValue(v) Si contiene una asoc. para v
SetentrySet()
Conjunto de pares de valores clave
get(k)
Valor asociado con k
isEmpty()
Si está vacío
keySet()
Conjunto de claves
put(k,v)
Asociar v con k
remove(k)
Eliminar asoc. para k
size()
Número de pares
values()
Colección de valores
La interface Map
Map
// Operaciones básicas
put(Object, Object):Object;
get(Object):Object;
remove(Object):Object;
containsKey(Object):boolean;
containsValue(Object):boolean;
size():int;
isEmpty():boolean;
// Operaciones completas
void putAll(Map t):void;
void clear():void;
// Vistas como colecciones
keySet():Set;
values():Collection;
entrySet():Set;
Uso de Map
Map map = new HashMap(); // instancia un map concreto
// ...
map.put(key, val); // inserta par llave-valor
// ...
// obtiene el valor asociado a la llave
Object val = map.get(key);
map.remove(key); // elimina par llave-valor
// ...
if (map.containsValue(val)) { ... }
if (map.containsKey(kay)) { ... }
Set keys = map.keySet(); // obtiene el conjunto de llaves
// itera a través del conjunto de llaves
Iterator iter = keys.iterator();
while (iter.hasNext()) {
Key key = (Key) iter.next();
// ...
}
Ejemplo1: Map
import java.util.*;
public class Frecuencia {
private static final Integer UNO = new Integer(1);
public static void main(String args[]) {
Map m = new HashMap();
for (int i=0; i<args.length; i++) {//inicializa tabla de línea de cmd
Integer freq = (Integer) m.get(args[i]);
m.put(args[i],
(freq==null ? UNO : new Integer(freq.intValue() + 1)));
}
System.out.println(m.size()+" pal. distintas");
System.out.println(m);}}
% java Freq if it is to be it is up to me to delegate
8 pal. distintas
{to=3, me=1, delegate=1, it=2, is=2, if=1, be=1, up=1}
Ejemplo 2: MAP
1/2
Generar números al azar (Math.random) y contar
cuantas veces sale cada uno.
HashMap = Colección de pares (clave-valor)
Clave = número aleatorio generado
Valor = contador que acumula las veces que ha aparecido
class Contador {
private int i;
public Contador(){ i=1;}
public void incrementar(){++i;}
public String toString() {
return Integer.toString(i);
}
}
Ejemplo 2: MAP
2/2
class Estadistico {
public static void main( String args[] ) {
HashMap tabla = new HashMap();
for(int i=0; i < 10000; i++) {
// Generar un número entre 0 y 20
Integer num = new Integer((int)(Math.random()*20));
if(tabla.containsKey(num))
//Incrementamos el contador asociado al número
((Contador)tabla.get(num)).incrementar();
else
//Añadimos nuevo par: numero-contador
tabla.put(num, new Contador());
}
System.out.println(tabla);
}
}
Interface SortedMap
 Mapa que mantiene sus entradas en orden ascendente
 los elementos deben implementar Comparable o
 se debe suministrar un Comparator en el momento de
la creación
 Operaciones: Iterator atraviesa el SortedMap en cualquiera
de sus vistas de colección en orden de las claves
 Operaciones adicionales:
 vista de rango
 puntos finales (claves)
 acceso al Comparator