Algoritmos: Ejemplo de un HashMap en Java y acelerando nuestras búsquedas de datos

Gaspar Fernández

hace 11 años

Un hashmap es una estructura donde podemos asociar muchas claves con sus respectivos valores, eso sí, una única clave a un valor, no podremos tener una clave con varios valores (eso sería un multimapa, no tiene implementación nativa en Java, a no ser que incluyamos bibliotecas como la commons collections de Apache).
La gracia de este tipo de estructuras está en las búsquedas, que se portan como si fueran Arrays, es decir el tiempo de acceso al elemento no depende del número de elementos de la estructura, la complejidad será O(1), aunque puede que haya casos un poquito peores, casi siempre será así.
Bueno, basta de teoría ¡vamos a probarlo! (El código se podrá descargar al final del post)

Vamos a recopilar datos sobre pilotos de fórmula 1, su escudería, fecha de nacimiento y puntuación, para ello creamos la siguiente clase:

Piloto.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class Piloto
{
private String nombre;
private String escuderia;
// Podría ser de otro tipo, pero para simplificar ponemos la fecha como String
private String nacimiento;
private double puntos;

public Piloto(String nombre, String escuderia, String nacimiento, double puntos)
{
this.nombre=nombre;
this.escuderia=escuderia;
this.nacimiento=nacimiento;
this.puntos=puntos;
}

public String getNombre()
{
return nombre;
}

public String getEscuderia()
{
return escuderia;
}

public String toString()
{
return nombre+" ["+puntos+"] ("+escuderia+") Nacimiento: "+nacimiento;
}
}

Y ahora, vamos a almacenar los datos en una lista, de Piloto, para ello creamos la siguiente clase:
PilotoList.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.*;

public class PilotoList
{
private List<Piloto> pilotos = new ArrayList<Piloto>();

public PilotoList()
{
}

public void add(String nombre, String escuderia, String nacimiento, double puntos)
{
pilotos.add(new Piloto(nombre, escuderia, nacimiento, puntos));
}

public String toString()
{
String ret = "";
for (Piloto p : pilotos)
ret+=p+"\n";

return ret;
}

public Piloto busca(String nombre)
{
for (Piloto p : pilotos)
if (p.getNombre().equals(nombre))
return p;

return null;
}

public List<Piloto> getList()
{
return pilotos;
}
}

Ok, ahora creamos un programa principal:

MainLista.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

import java.util.*;

public class MainLista
{
public static void main(String argv[])
{
PilotoList pilotos=new PilotoList();

pilotos.add("Sebastian Vettel", "Red Bull", "1987/07/03", 1057);
pilotos.add("Mark Webber", "Red Bull", "1976/08/27", 848.5);
pilotos.add("Jenson Button", "McLaren", "1980/01/19", 999);
pilotos.add("Lewis Hamilton", "McLaren", "1985/01/17", 913);
pilotos.add("Fernando Alonso", "Ferrari", "1981/07/29", 1367);
pilotos.add("Nico Rosberg", "Mercedes", "1985/06/27", 399.5);
pilotos.add("Kimi Raikkonen", "Lotus", "1979/10/17", 785);
pilotos.add("Paul di Resta", "Force India", "1986/04/16", 73);
pilotos.add("Kaumi Kobayasi", "Sauber", "1986/09/13", 125);
pilotos.add("Daniel Ricciardo", "Toro Rosso", "1989/07/01", 10);
pilotos.add("Pastor Maldonado", "Williams", "1985/03/09", 43);
pilotos.add("Vitaly Petrov", "Caterham", "1984/09/08", 64);
pilotos.add("Pedro de la Rosa", "HRT", "1971/02/24", 35);
pilotos.add("Timo Glock", "Marussia", "1982/03/18", 51);

pilotos.add("Felipe Massa", "Ferrari", "1985/04/25", 704);
pilotos.add("Michael Schumacher", "Mercedes", "1969/01/03", 1566);
pilotos.add("Romain Grosjean", "Lotus", "1986/04/17", 86);
pilotos.add("Nico Hulkenberg", "Force India", "1987/08/19", 85);
pilotos.add("Sergio Perez", "Sauber", "1980/01/26", 80);
pilotos.add("Jean Eric Vergne", "Toro Rosso", "1980/04/25", 12);
pilotos.add("Bruno Serna", "Williams", "1983/10/15", 33);
pilotos.add("Heikki Kovalainen", "Caterham", "1989/10/19", 105);
pilotos.add("Narain Karthikeyan", "HRT", "1977/01/14", 5);
pilotos.add("Charles Pic", "Marussia", "1980/02/15", 0);
String s="";
for (int i=0; i<100000; i++)
s = pilotos.toString();

System.out.println(s);
}
}

En principio lo que queremos hacer es listar los elementos, un millón de veces, para poder cronometrar el código resultante. Esto variará entre ordenadores, sistemas operativos e implementaciones de JRE, pero es para hacernos una idea del tiempo que tarda.

Después de 3 pruebas, la media de tiempo resultante es: 2.836s

Ahora cambiamos ligeramente el código, e introducimos búsquedas:

1
2
3
4
5
6
7
8
9

List <Piloto> ps = pilotos.getList();

for (int i=0; i<10000000; i++)
{
for (Piloto p : ps)
{
Piloto pn = pilotos.busca(p.getNombre());
}
}

Con este código, unos 10 millones de veces (10^7) haremos una búsqueda de todos los pilotos que hay en la lista. Recordemos que para hacer esa búsqueda, hemos recorrido la lista hasta encontrar el elemento deseado:

Después de 3 pruebas, la media de tiempo resultante es: 12.960
Tarda un poco más, pero es que son muchas búsquedas. Ahora hacemos lo mismo, pero con un HashMap:

PilotoHashmap.java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*;

public class PilotoHashmap
{
private HashMap<String, Piloto> nombres = new HashMap<String, Piloto>();

public PilotoHashmap ()
{
}

public void add(String nombre, String escuderia, String nacimiento, double puntos)
{
Piloto p=new Piloto(nombre, escuderia, nacimiento, puntos);
nombres.put(nombre, p);
}

public String toString()
{
String ret = "";
for (Piloto p : nombres.values())
ret+=p+"\n";

return ret;
}

public Piloto busca (String nombre)
{
return nombres.get(nombre);
}

public Collection<Piloto> getList()
{
return nombres.values();
}
}

Y un programa principal, primero, para enumerar:

MainHashmap.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import java.util.*;

public class MainHashmap
{
public static void main(String argv[])
{
PilotoHashmap pilotos=new PilotoHashmap();

pilotos.add("Sebastian Vettel", "Red Bull", "1987/07/03", 1057);
pilotos.add("Mark Webber", "Red Bull", "1976/08/27", 848.5);
pilotos.add("Jenson Button", "McLaren", "1980/01/19", 999);
pilotos.add("Lewis Hamilton", "McLaren", "1985/01/17", 913);
pilotos.add("Fernando Alonso", "Ferrari", "1981/07/29", 1367);
pilotos.add("Nico Rosberg", "Mercedes", "1985/06/27", 399.5);
pilotos.add("Kimi Raikkonen", "Lotus", "1979/10/17", 785);
pilotos.add("Paul di Resta", "Force India", "1986/04/16", 73);
pilotos.add("Kaumi Kobayasi", "Sauber", "1986/09/13", 125);
pilotos.add("Daniel Ricciardo", "Toro Rosso", "1989/07/01", 10);
pilotos.add("Pastor Maldonado", "Williams", "1985/03/09", 43);
pilotos.add("Vitaly Petrov", "Caterham", "1984/09/08", 64);
pilotos.add("Pedro de la Rosa", "HRT", "1971/02/24", 35);
pilotos.add("Timo Glock", "Marussia", "1982/03/18", 51);

pilotos.add("Felipe Massa", "Ferrari", "1985/04/25", 704);
pilotos.add("Michael Schumacher", "Mercedes", "1969/01/03", 1566);
pilotos.add("Romain Grosjean", "Lotus", "1986/04/17", 86);
pilotos.add("Nico Hulkenberg", "Force India", "1987/08/19", 85);
pilotos.add("Sergio Perez", "Sauber", "1980/01/26", 80);
pilotos.add("Jean Eric Vergne", "Toro Rosso", "1980/04/25", 12);
pilotos.add("Bruno Serna", "Williams", "1983/10/15", 33);
pilotos.add("Heikki Kovalainen", "Caterham", "1989/10/19", 105);
pilotos.add("Narain Karthikeyan", "HRT", "1977/01/14", 5);
pilotos.add("Charles Pic", "Marussia", "1980/02/15", 0);

String s="";
for (int i=0; i<100000; i++)
s = pilotos.toString();

System.out.println(s);
}
}

Tras ejecutarlo 3 veces el tiempo medio es de : 2.9040s (prácticamente es como con la lista)

Ahora modificamos el código para hacer búsquedas como antes:

1
2
3
4
5
6
7
8
9

Collection <Piloto> ps = pilotos.getList();

for (int i=0; i<10000000; i++)
{
for (Piloto p : ps)
{
Piloto pn = pilotos.busca(p.getNombre());
}
}

El tiempo ahora, tras 3 ejecuciones, es de 2.885 (casi unas 5 veces menos).

El inconveniente es que ocupa un poco más de memoria, ya que repetimos algo de información, pero está clara la ventaja en este tipo de casos, tardamos mucho menos tiempo en hacer búsquedas de elementos.

Podéis descargar el código desde aquí: Formula1HashMap.tar (2Kb)

También podría interesarte....