Download Tema 5

Tema 5. Tipo Map y SortedMap
Autor: José C. Riquelme
1. El tipo Map
1.1 Definición
Java proporciona en el paquete java.util un tipo denominado Map que podría traducirse como
aplicación (aunque vulgarmente y por simplificar es común también el nombre de “mapa”). Un
tipo Map es la forma que tiene Java de guardar un conjunto de pares relacionados al igual que
se hace en teoría de conjuntos cuando se define una aplicación entre dos conjuntos, de
manera que a cada elemento del conjunto inicial le corresponde una y solo una imagen en el
conjunto final.
De esta manera Map se define sobre dos tipos de datos, los que están en el conjunto inicial,
llamados claves (keys) y los que están en el conjunto final, denominados valores (values). Un
Map entonces está definido por un conjunto (Set) de claves, una colección (Collection) de
valores y un conjunto de pares clave-valor. Como sucede en el concepto matemático de
aplicación sobreyectiva cada clave es única, de ahí que el conjunto inicial se modele con un
Set, para que no haya claves repetidas, pero el conjunto de valores puede tener elementos
“repetidos” ya que dos claves distintas pueden tener el mismo valor. Por ejemplo si a una
cadena de caracteres le hacemos corresponder su valor numérico, tendríamos una aplicación
como:
“uno”
1
“1”
“I”
“1.0”
“2”
2
“II”
“1+1”
Hay que señalar que el tipo Map no extiende a Collection y que no es Iterable, por tanto, sus
elementos no pueden ser recorridos con el for extendido. Ejemplos cotidianos de tipos Map
son los listines telefónicos (clave: nombre contacto, valor: número de teléfono), listas de clase
(clave: nombre del alumno, valor: calificaciones), ventas de un producto (clave: código de
producto, valor: total de euros de recaudación), índices de palabras por páginas en un libro
(clave: palabra, valor: lista de números de página donde aparece), la red de un Metro (clave:
2
Introducción a la Programación
nombre de la estación, valor: conjunto de líneas que pasan por esa estación), o al revés (clave:
número de línea, valor: lista de estaciones de esa línea), etc.
La clase que implementa la interfaz Map es HashMap y de nuevo obliga a definir de forma
correcta el método hashCode del tipo de las claves para evitar claves repetidas. Asimismo al
igual que pasa en el tipo Set, los objetos mutables que se introducen en un Map son “vistas” o
referencias a objetos y por tanto, si éstos cambian, el Map puede dejar de ser coherente, esto
es, podría tener claves repetidas.
Un Map cuyas claves sean String y cuyos valores sean Integer se definiría e inicializaría:
Map<String, Integer> m = new HashMap<String, Integer>();
1.2 Métodos
Los métodos que proporciona Java para el tipo Map son los siguientes. Como siempre más
información en http://docs.oracle.com/javase/7/docs/api/java/util/Map.html
void
clear()
Removes all of the mappings from this map.
boolean
containsKey(Object key)
Returns true if this map contains a mapping for the specified key.
boolean
containsValue(Object value)
Returns true if this map maps one or more keys to the specified value.
V
get(Object key)
Returns the value to which the specified key is mapped, or null if this
map contains no mapping for the key.
boolean
isEmpty()
Returns true if this map contains no key-value mappings.
Set<K>
keySet()
Returns a Set view of the keys contained in this map.
V
put(K key, V value)
Associates the specified value with the specified key in this map.
V
remove(Object key)
Removes the mapping for a key from this map if it is present.
int
size()
Returns the number of key-value mappings in this map.
Collection<V>
values()
Returns a Collection view of the values contained in this map.
5. Tipos Map y SortedMap
.Algunas consideraciones sobre los métodos son las siguientes:






put(key, value) añade a la función la clave key, a la que le asocia el valor value.
Devuelve el valor que previamente tuviera asociada la clave, si ya estaba en el Map o
null en caso contrario.
get(key) devuelve el valor asociado con la clave key, si ésta existe en el Map o null si no
existe.
remove(key) elimina la clave key si estaba en el Map, en cuyo caso devuelve el valor
que tuviera asociado. Si no existía esa clave, no hace nada y devuelve null.
keySet() devuelve el conjunto de las claves que forman parte del Map. Como es un
conjunto SÍ es iterable.
values() devuelve una Collection con los valores que contiene el Map. Puede haber
elementos duplicados, de ahí que sea una Collection y no un Set. También es iterable.
Los objetos devueltos por estas operaciones son vistas del Map original, por lo que las
modificaciones que se hagan sobre el Map original repercutirán en las vistas devueltas
y viceversa.
1.3 Inicialización de un objeto de tipo Map
La inicialización de un objeto de tipo Map siempre sigue la misma estructura, según el
esquema siguiente
a. Creación del objeto (HashMap)
b. Para cada clave mediante un recorrido
c. Si la clave ya está (containsKey)
d. Obtener valor asociado (get)
e. Actualizar valor u obtener nuevovalor a partir de valor
f. Si es necesario añadir al map clave y nuevovalor (put)
g. Si la clave no está
h. Inicializar valor
i. Añadir clave y valor (put)
En el paso a. se construye el objeto tipo Map invocando al constructor de la clase HashMap.
El paso b. normalmente incluye un recorrido sobre la colección de elementos que se vayan
a insertar como claves. Para cada clave se calculará el valor correspondiente, normalmente
mediante algún tipo de cálculo u operación de acceso a una colección de datos a partir de
la clave. Una vez tenemos el par clave-valor a insertar en el Map, nos preguntamos en el
paso c. mediante el método containsKey si la clave ya estaba anteriormente en el Map. Si la
clave ya estaba debemos obtener el valor asociado a esa clave en el Map mediante el
método get. Dependiendo de si la actualización consiste en sustituir un nuevo valor por el
anterior o actualizar el ya existente se ejecutan los pasos e. y f.
Por ejemplo, si el Map es asociar a cada palabra una lista con los números de páginas de un
libro donde aparece, la actualización será añadir a la vista de la lista que conforma el valor
un nuevo elemento y por tanto no hace falta invocar al método put. Sin embargo, si el Map
fuera para actualizar las ventas de un producto, al invocar al método get obtendríamos el
3
4
Introducción a la Programación
valor de las ventas pasadas, a este dato se le debería sumar las nuevas ventas y ahora sí
actualizaríamos mediante el método put las ventas realizadas del producto clave.
Finalmente si la clave no estaba en el Map, se calcula el valor inicial en el paso h. para
añadir el par clave-valor mediante el método put en el paso i.
1.4 Ejemplo 1
Supongamos que se quiere calcular la frecuencia absoluta de aparición de los caracteres de un
String. Para ello se define un Map cuyas claves son de tipo Character y los valores de tipo
Integer. El método recibirá un String y devolverá un objeto de tipo Map<Character, Integer>.
El código del método sería:
public static Map<Character, Integer> contador_carac(String frase){
Map<Character,Integer> contador = new HashMap<Character,Integer>();
frase=frase.toUpperCase(); // todos los caracteres en mayúsculas
for(int i=0;i<frase.length();i++)
{
Character caracter = frase.charAt(i);
if (contador.containsKey(caracter)) {
Integer valor=contador.get(caracter);
valor++;
contador.put(caracter, valor);
}
else
contador.put(caracter, 1);
}
return contador;
}
Nótese como el método sigue fielmente el esquema antes indicado. Se recorren los caracteres
del String de entrada mediante un for clásico. Para cada carácter se pregunta si ya está, de
forma que si está, se obtiene el valor correspondiente al número de veces que ha aparecido
anteriormente, se incrementa en uno y se vuelva a actualizar. La llamada al método put es
obligatoria ya que valor es de tipo Integer y por tanto inmutable. En el caso de que el carácter
no estuviera se inicia la frecuencia a 1.
1.5 Ejemplo 2
Supongamos que dado una lista de String que denominamos libro se quiere obtener un índice
de las posiciones que ocupan las cadenas de libro mediante una lista de enteros. El argumento
de entrada será por tanto de tipo List<String> y el argumento de salida un Map<String,
List<Integer>>. El método tendría el siguiente código:
public static Map<String, List<Integer>> indice_pal(List<String>libro){
Map<String,List<Integer>> indice=new HashMap<String,List<Integer>>();
int pos=0;
for(String palabra: libro)
{
if (indice.containsKey(palabra)) {
indice.get(palabra).add(pos);
5. Tipos Map y SortedMap
}
else{
List<Integer> lis = new ArrayList<Integer>();
lis.add(pos);
indice.put(palabra, lis);
}
pos++;
}
return indice;
}
Nótese que la principal diferencia con el ejercicio anterior es que no es necesario invocar al
método put en el caso de que la palabra ya esté en el índice. Observe la sentencia
indice.get(palabra).add(pos);
equivalente a
List<Integer> lis = indice.get(palabra);
lis.add(pos);
Igualmente debe observar que incluso en este caso tampoco es necesario invocar a put ya que
lis es una vista de la lista correspondiente y por tanto al añadir un elemento a lis, ya lo estamos
haciendo a la lista guardada en el conjunto imagen del Map.
Este problema se puede restringir también a algunas palabras claves, no a todas las de la lista
libro. Supongamos que tenemos las palabras claves en un Set de String, ¿Cómo modificaría el
código del método anterior para que en el Map sólo estuvieran las palabras claves?
2. El tipo SortedMap
2.1 Definición
El tipo SortedMap es un Map en el que el conjunto de las claves está ordenado. La clase que
implementa SortedMap es TreeMap necesita que el tipo de las claves o bine implemente
Comparable o se proporcione un orden externo mediante un Comparator. Por tanto,
inicializaciones de SortedMap como:
SortedMap<String,List<Integer>> indice = new TreeMap<String,List<Integer>>();
Crea un SortedMap donde las claves de tipo String están ordenadas por el orden natural de
String. Para crear un SortedMap por un orden no natural debemos invocar al constructor
pasándole como argumento un comparator:
Comparator<Persona> cm_ed = new ComparatorPersonaEdad();
SortedMap<Persona,List<Integer>>mp=new TreeMap<Persona,List<Integer>>(cm_ed);
5
6
Introducción a la Programación
Las reflexiones que se hicieron para el tipo SortedSet respecto del orden definido por un
Comparator siguen siendo válidas para el SortedMap. Esto es, dos claves c1 y c2 son iguales
para un SortedMap si compare(c1,c2)==0. Por tanto, si el Comparator no rompe los empates
por el orden natural, en el SortedMap anterior sólo habría una Persona clave por cada edad.
2.2 Métodos
SortedMap hereda de Map, por tanto, todos los métodos de Map son válidos también para un
objeto SortedMap. Además Java proporciona algunos métodos para manejar el orden en el
conjunto de las claves: http://docs.oracle.com/javase/7/docs/api/java/util/SortedMap.html
K
firstKey()
Returns the first (lowest) key currently in this map.
SortedMap<K,V>
headMap(K toKey)
Returns a view of the portion of this map whose keys are strictly less than
toKey.
Set<K>
keySet()
Returns a Set view of the keys contained in this map.
K
lastKey()
Returns the last (highest) key currently in this map.
SortedMap<K,V>
subMap(K fromKey, K toKey)
Returns a view of the portion of this map whose keys range from fromKey,
inclusive, to toKey, exclusive.
SortedMap<K,V>
tailMap(K fromKey)
Returns a view of the portion of this map whose keys are greater than or equal to
fromKey.
Hay que tener en cuenta que si no vamos a usar estos métodos y sólo queremos que la
visualización del Map salga ordenada se puede declarar un Map mediante la clase TreeMap.
Por ejemplo, pruebe a definir en el Ejemplo 2:
Map<String,List<Integer>> indice=new TreeMap<String,List<Integer>>();
Y verá como al imprimir el Map en la consola las palabras salen ordenadas alfabéticamente.
2.3 Ejemplo 3
Dado el Map construido en el ejemplo 1 que relaciona cada carácter con su frecuencia
absoluta de aparición en un texto, se quiere construir un Map inverso, en el que las claves sean
de tipo Integer y los valores asociados a cada clave sean de tipo List<Character> con los
caracteres cuya frecuencia absoluta es la clave del Map. Además se desea mostrar los
caracteres ordenados por frecuencia de mayor a menor, por tanto se necesitará crear un
SortedMap. Por tanto, el método recibirá un Map<Character, Integer> y devolverá un
SortedMap<Integer,List<Character>>. Su código es:
5. Tipos Map y SortedMap
public static SortedMap<Integer, List<Character>> invierteMap
(Map<Character, Integer> m) {
SortedMap<Integer, List<Character>> res =
new TreeMap<Integer,List<Character>>(new ComparadorIntegerInverso());
Set<Character> sp = m.keySet();
for(Character caracter: sp){
Integer num=m.get(caracter);
if (res.containsKey(num)) {
res.get(num).add(caracter);
}
else {
List<Character> lista = new LinkedList<Character>();
lista.add(caracter);
res.put(num, lista);
}
}
return res;
}
Nótese que para que el orden del SortedMap sea de mayor a menor ha debido crearse un
Comparator para Integer inverso. Su código es muy simple:
public class ComparadorIntegerInverso implements Comparator<Integer> {
public int compare(Integer arg0, Integer arg1) {
return arg1.compareTo(arg0);
}
}
3. Ejercicios propuestos
1. ¿Cómo modificaría el código del ejemplo 2 para que en el Map sólo estuvieran las palabras
claves dadas por un Set de String?
2. Modifique los constructores de los ejemplos 1 y 2 para que las claves estén ordenadas.
3. Modifique el ejemplo 3 para que el método reciba un entero F y devuelva un Map con sólo
aquellas palabras cuya frecuencia absoluta sea mayor que F.
4. Cambie el código de los ejemplos 1 y 3 para que en vez de frecuencias absolutas trabajen
con frecuencias relativas. ¿Cuáles son los 3 caracteres de mayor frecuencia relativa en
inglés y en español?
5. A partir del tipo Gen definido en los boletines de problemas y dado un conjunto (Set) de
genes de distintas especies, y un nucleótido mediante un carácter, implemente un método
estático en la clase Genes que devuelva el número de veces que dicho nucleótido aparece
en los genes de cada especie. Esto es, dados los genes:
Gen g1 = new GenImpl("BDH1", 5, "Homo Sapiens", "ATGCTGGCCAT");
Gen g2 = new GenImpl("LGALS8", 5, "Homo Sapiens","TGCTCCGAATGG");
Gen g3 = new GenImpl("PAOX", 5, "Homo Sapiens","GGCCTTAATGC");
7
8
Introducción a la Programación
Gen g4 = new GenImpl("ZNF324B", 1, "Homo Sapiens","GCTTAGCCA");
Gen g5 = new GenImpl("LYZL4", 0, "Homo Sapiens","GTTCCATGACATT");
Gen
Gen
Gen
Gen
Gen
g6 = new GenImpl("BIRC5", 9, "Canis Lupus", "TGCCATGACC");
g7 = new GenImpl("MYL4", 9, "Canis Lupus","TTTGGACAGT");
g8 = new GenImpl("PRKCA", 9, "Canis Lupus","GGCCATACTGA");
g9 = new GenImpl("PYY", 9, "Canis Lupus","CCAGTATGCA");
g10 = new GenImpl("KRT10", 9, "Canis Lupus","GTACCTAGTAC");
Queremos obtener esta salida si se invoca al método con cada uno de los nucleótidos :
Nucleótido
Nucleótido
Nucleótido
Nucleótido
A:
C:
G:
T:
{Homo
{Homo
{Homo
{Homo
Sapiens=11,
Sapiens=15,
Sapiens=14,
Sapiens=16,
Canis
Canis
Canis
Canis
Lupus=13}
Lupus=14}
Lupus=12}
Lupus=13}