En PC Resumen vamos a hablar de "Map" en Java. Los objetos Map asocian claves a valores y no pueden contener claves duplicadas (es decir cada clave puede asociarse solamente a un valor; a este tipo de asociación se la conoce como asociación uno a uno. Estos objetos se diferencian de los objetos siete en cuanto a que los primeros contienen claves y valores, mientras que los segundos contienen solamente valores. Tres de las muchas clases que implementan la interfaz son Hashtable, HashMap y TreeMap. los dos primeros almacenan los objetos en tablas hash y el último en un árbol. la interfaz SortedMap extiende a Map y mantiene las claves en orden, ya sea en el orden natural o en el orden especificado por un objeto Comparator. la clase TreeMap implementa a SortedMap.

Implementación de Map con tablas hash

Cuando disponemos de una clave que puede tomar muchos valores diferentes pero de las que no tenemos muchos valores se necesita un esquema de alta velocidad que nos permita convertir claves en índices de una tabla. Pensamos por ejemplo que tenemos 100 trabajadores y como clave utilizamos un número de seguridad social de 9 cifras. Obviamente sería impracticable generar una tabla de mil millones de trabajadores.

Este esquema es la base de una técnica llamada hashing. Un error en este esquema se denomina colisión; esto sucede cuando dos claves diferentes asocian a la misma posición en la tabla. Evidentemente no podemos almacenar dos valores en el mismo espacio y por lo tanto necesitamos encontrar otra posición. Hay muchas posibles soluciones a este problema y la discusión de qué es mejor supera el alcance de este curso. Digamos que la solución más "popular" en las colisiones es hacer que cada posición de la tabla sea una lista enlazada para todos los par clave / valor que se asocian a esta posición. Esta es la solución que adoptan las clases Hashtable y HashMap las que implementan la interfaz Map. Las principales diferencias es que HashMap no esta sincronizada y permite claves y valores null.

En el programa siguiente usamos un objeto HashMap para contar el número de ocurrencias de cada palabra en una cadena.

import java.util.StringTokenizer;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.TreeSet;
import java.util.Scanner;

public class ContarPalabras {
    private Map <String, Integer> mapa;
    private Scanner scanner;

    public ContarPalabras () {
        mapa = new HashMap<String, Integer>();
        scanner = new Scanner(System.in);
        crearMap();
        mostrarMap();
    }

    private void crearMap() {
        System.out.println("Escribir texto: ");
        String entrada = scanner.nextLine();
        StringTokenizer tokenizer = new StringTokenizer(entrada);
        while (tokenizer.hasMoreTokens()) {
            String palabra = tokenizer.nextToken().ToLowerCase();
            if (mapa.containsKey(palabra)) {
                int cuenta = mapa.get(palabra);
                mapa.put(palabra, cuenta + 1);
            } else {
                mapa.put(palabra, 1);
            }
        }
    }

    private void mostrarMap() {
        Set<String> claves = mapa.keySet();
        TreeSet<String> clavesOrdenadas = new TreeSet<String> (claves);
        System.out.println("El mapa contiene:\nClau\t\tValor");
        for (String clave: clavesOrdenadas) {
            System.out.printf("%-10s%10s\n", clave, mapa.get(clave));
        }
        System.out.printf("\nsize: %d \n isEmpty: %b \n", mapa.size(), mapa.isEmpty());
    }

    public static void main(String args[]) {
        new ContarPalabras();
    }
}

En primer lugar creamos un objeto HashMap vacío con una capacidad inicial predeterminada (16) y un factor de carga predeterminado (0.75). El factor de carga es la proporción del número de celdas ocupadas en la tabla con respecto al número total de celdas. Cuando el número de posiciones ocupadas se vuelve mayor que la capacidad multiplicada por el factor de carga, la capacidad se duplica de forma automática. Los dos parámetros del constructor son: el primero el tipo de clave (en este caso String) y el segundo el tipo de valor (en este caso Integer).

Después utilizamos el método containsKey para determinar si la palabra ya está en el mapa. Si está obtenemos el contador con el método get, la incrementamos y lo ponemos en el mapa utilizando el método put, sino ponemos la palabra con el contador igual a 1.

En el método mostarMap utilizamos el método keySet para obtener un conjunto de las claves. Utilizamos un TreeSet para ordenarlas y las imprimimos.

Finalmente se utilizan los métodos size para obtener el número de valores y isEmpty que nos devuelve si el mapa está vacío o no.

Pin It