En esta entrada vamos a profundizar sobre las tablas HashMap en Java. Los HashMaps son unas estructuras de datos donde los valores se insertan indexados por una clave, y se accede a ellos a través de la misma clave. Son extremadamente eficientes para realizar búsquedas, ya que el tiempo de búsqueda en un HashMap se considera constante, también tiene algunos inconvenientes como:
- Ocupan más memoria que otras estructuras de datos. Esto hoy en día no es un problema ya que todos contamos con memoria más que suficiente es nuestros ordenadores de propósito general. Pero hay que tener cuidado si se está programando en dispositivos con poca memoria, ya que puede haber mejores estructuras de datos para organizar nuestros datos.
- Dependiendo de la función de «hash» que se aplique nuestro HashMap será más eficiente o menos a la hora de realizar búsquedas.
¿ Cómo se representa un HashMap ?
Un HashMap está constituido de «cubetas» y cada «cubeta» tiene asociado una lista de valores indexados por el índice de la «cubeta»:
Como podéis apreciar tenemos en la parte izquierda de la imagen una serie de cubetas, indexadas por su índice, esto podría ser perfectamente un Array, y cada elemento de dicho Array tiene asociada una lista de elementos que han sido indexados por su clave.
¿ Cómo se indexa un elemento en un HashMap ?
Supongamos que tenemos nuestra famosa clase Coche, y queremos indexar los elementos a partir de su id. Nuestra clase coche:
import java.io.Serializable;
public class Coche implements Serializable{
private int id;
private int numPuertas;
private String marca;
private String modelo;
private int numeroCaballos;
private int cilindrada;
private double precio;
public Coche() {
}
public Coche(int id, int numPuertas, String marca, String modelo, int numeroCaballos, int cilindrada, double precio) {
super();
this.numPuertas = numPuertas;
this.marca = marca;
this.modelo = modelo;
this.numeroCaballos = numeroCaballos;
this.cilindrada = cilindrada;
this.precio = precio;
this.id = id;
}
public int getNumPuertas() {
return numPuertas;
}
public void setNumPuertas(int numPuertas) {
this.numPuertas = numPuertas;
}
public String getMarca() {
return marca;
}
public void setMarca(String marca) {
this.marca = marca;
}
public String getModelo() {
return modelo;
}
public void setModelo(String modelo) {
this.modelo = modelo;
}
public int getNumeroCaballos() {
return numeroCaballos;
}
public void setNumeroCaballos(int numeroCaballos) {
this.numeroCaballos = numeroCaballos;
}
public int getCilindrada() {
return cilindrada;
}
public void setCilindrada(int cilindrada) {
this.cilindrada = cilindrada;
}
public double getPrecio() {
return precio;
}
public void setPrecio(double precio) {
this.precio = precio;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
}
Supongamos que tenemos 2 coches cuyos id’s son «3» y «16» y los queremos indexar. ¿ Cómo se procedería ?
Para cada elemento de los 2:
- Se aplica una función de «hash» al «id» del coche, esto nos dará como resultado el valor del índice de la «cubeta» donde se encuentra la lista donde debemos almacenar nuestro valor.
- Una vez tenemos el índice de la «cubeta» donde está la lista donde debemos insertar nuestro Coche, simplemente la añadimos al final de la lista.
- Ya tenemos nuestro elemento indexado en nuestro HashMap.
¿ Cómo se accede a un elemento indexado por su clave ?
Para acceder a un elemento a través de su clave se procede de la siguiente manera:
- Se realiza la función de «hash» a la clave del elemento al cuál queremos acceder. Esto nos dará el índice de la cubeta donde se encuentra el elemento que estamos buscando.
- Se recorre la lista asociada a la «cubeta» hasta encontrar nuestro elemento.
Un ejemplo teórico con los datos anteriores
Supongamos que partimos de la siguiente base:
0 -> [ {coche con id 43}, {coche con id 14} ]
1 -> [ ]
2 -> [ {coche con id 55}, {coche con id 83} ]
3 -> [ ]
Tenemos 4 cubetas:
- En la lista asociada a nuestra primera cubeta tenemos los coches con id «43» y «14».
- Nuestra segunda cubeta tiene su lista vacía.
- En la lista asociada a nuestra tercera cubeta tenemos los coches con id «55» y «83».
- Nuestra cuarta cubeta está vacía.
Vamos a indexar nuestro coche con id «3»:
- Aplicamos la función de «Hash» sobre el «id», supongamos que nos da como resultado el índice 0.
- Añadimos el coche a la lista asociada a la cubeta 0 en la última posición.
Nuestro HashMap quedaría de la siguiente manera:
0 -> [ {coche con id 43}, {coche con id 14}, {coche con id 3} ]
1 -> [ ]
2 -> [ {coche con id 55}, {coche con id 83} ]
3 -> [ ]
Vamos a indexar nuestro coche con id «16»:
- Aplicamos la función de «Hash» sobre el «id», supongamos que nos da como resultado el índice 1.
- Añadimos el coche a la lista asociada a la cubeta 1.
Nuestro HashMap quedaría de la siguiente manera:
0 -> [ {coche con id 43}, {coche con id 14}, {coche con id 3} ]
1 -> [ {coche con id 16} ]
2 -> [ {coche con id 55}, {coche con id 83} ]
3 -> [ ]
La importancia de elegir una buena función de «hash»
Imaginaros por un momento que nuestra función de «hash» tiene una probabilidad de un 60 % de devolver la cubeta 0 para cualquier clave que queramos indexar, esto provocaría una descompensación muy grande entre el número de elementos de las listas asociadas a cada cubeta y esto provocaría que las búsquedas fuesen cada vez más lentas conformes vamos insertando más elementos debido a que nuestra lista en la posición 0 va creciendo cada vez más.
Este es el principal problema que presentan las tablas Hash que tiene muy fácil solución, elegir una función de «hash» lo más cercana a la equiprobabilidad posible, es decir, en el caso más optimo si tenemos 10 cubetas e insertamos 10 elementos, deberíamos tener 1 elemento en la lista de cada cubeta:
0 -> [ {elemento1} ]
1 -> [ {elemento2} ]
2 -> [ {elemento3} ]
3 -> [ {elemento4} ]
4 -> [ {elemento5} ]
5 -> [ {elemento6} ]
6 -> [ {elemento7} ]
7 -> [ {elemento8} ]
8 -> [ {elemento9} ]
9 -> [ {elemento10} ]
Este sería el caso óptimo, pero es prácticamente imposible encontrar una función de «hash» con esta equiprobabilidad, sin embargo, si se pueden encontrar funciones que se comportan de forma bastante óptima y no producen grandes descompensaciones en el tamaño de los elementos de cada lista asociada a la cubeta.
Vamos al lio ya con el código fuente en Java.
¿ Cómo se instancia un HashMap en Java ?
HashMap es una clase propia de Java, por lo tanto se instancia de la siguiente forma:
HashMap<Integer, Coche> miHashMap = new HashMap<>();
Aquí estamos instanciando un HashMap que hemos parametrizado para que su clave sea un valor de tipo entero y el valor que va a guardar va a ser un «Coche». Se puede utilizar cualquier objeto como clave y cualquier objeto como valor.
Insertando elementos en nuestro HashMap
Para insertar elementos en nuestro HashMap utilizaremos el método «put»:
//Creamos los objetos que queremos indexar en nuestra tabla Hash
Coche coche1 = new Coche(1, 5, "Opel", "Astra", 90, 1800, 10000);
Coche coche2 = new Coche(15, 3, "Citroen", "C3", 88, 1600, 12000);
Coche coche3 = new Coche(34, 3, "Seat", "Ibiza", 76, 1200, 12000);
//Insertamos los elementos
miHashMap.put(coche1.getId(), coche1);
miHashMap.put(coche2.getId(), coche2);
miHashMap.put(coche3.getId(), coche3);
Buscando elementos en nuestro HashMap
Para buscar elementos en un HashMap se utiliza el metodo «get», que puede devolver el elemento si la clave se encuentra indexada o «null» en caso contrario:
//Buscamos el elemento con clave = 1
if (miHashMap.get(1) != null) {
Coche cocheBuscadoQueExiste = miHashMap.get(1);
System.out.println("Marca:" + cocheBuscadoQueExiste.getMarca());
System.out.println("Modelo:" + cocheBuscadoQueExiste.getModelo());
}
//Buscamos un coche que no existe con clave 73
if (miHashMap.get(73) == null) {
System.out.println("El coche con id 73 no existe en el HashMap");
}
Hemos buscado un elemento que existe y otro que no existe.
Iterar sobre todos los elementos de nuestro HashMap
//Si solo queremos iterar sobre las claves sin obtener el valor
for (Integer key : miHashMap.keySet()) {
System.out.println("Hay un elemento con clave: " + key);
}
//Si queremos acceder solo a los valores
for (Coche coche : miHashMap.values()) {
System.out.println("Marca: " + coche.getMarca());
System.out.println("Modelo: " + coche.getModelo());
}
//Si queremos acceder tanto a las claves como a los valores
for (Map.Entry<Integer, Coche> entry : miHashMap.entrySet()) {
System.out.println("El " + entry.getValue().getMarca() + " " + entry.getValue().getModelo() + " está indexado a través de la clave: " + entry.getKey());
}
La salida de nuestro programa
Hay un elemento con clave: 1
Hay un elemento con clave: 34
Hay un elemento con clave: 15
Marca: Opel
Modelo: Astra
Marca: Seat
Modelo: Ibiza
Marca: Citroen
Modelo: C3
El Opel Astra está indexado a través de la clave: 1
El Seat Ibiza está indexado a través de la clave: 34
El Citroen C3 está indexado a través de la clave: 15
¿ Cuándo utilizar un HashMap en contraposición con otras estructuras de datos ?
Siempre se debe utilizar un HashMap cuando la principal operación que vuestro algoritmo va a realizar recurrentemente son búsquedas y no existen problemas de memoria que sean tan restrictivos que no permitan utilizar esta estructura de datos. La decisión de utilizar un HashMap en las búsquedas es debido a que el tiempo de búsqueda es constante, por lo tanto, es la mejor estructura de datos para realizar búsquedas.
En la próxima entrada implementaremos un HashMap desde 0, o como se diría en inglés «from scratch».
Si queréis ver más información sobre la clase HashMap os dejo el siguiente enlace de la documentación oficial de Java.
Si os ha gustado la entrada de «HashMap en Java» dejad un comentario en la caja de comentarios, y si no entendéis algo también! Un saludo programadores