Publi

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


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....

There are 21 comments left Ir a comentario

  1. Pingback: Bitacoras.com /

  2. Galo /
    Usando Google Chrome Google Chrome 50.0.2661.102 en Windows Windows 7

    Gracias muy instructivo,

    1. Gaspar Fernández / Post Author
      Usando Mozilla Firefox Mozilla Firefox 46.0 en Ubuntu Linux Ubuntu Linux

      Muchas gracias Galo!

  3. Erick /
    Usando Google Chrome Google Chrome 63.0.3239.132 en Windows Windows 7

    Una consulta, si creas el HashMap con la clave (nombre,p) y cuando haces el pilotos.add solo agregas por lo que veo, según el orden el objeto «p» y que agregas en la clave «nombre» ?

    1. Gaspar Fernández / Post Author
      Usando Mozilla Firefox Mozilla Firefox 57.0 en Linux Linux

      Disculpa Erick, no entiendo muy bien tu pregunta.

    2. Alvaro /
      Usando Google Chrome Google Chrome 67.0.3396.79 en Windows Windows NT

      La clase PilotosHashMap tiene el metodo pilotos.add es fue creado en el ejemplo para agregar el piloto al hashmap que es privado, en el cual va nombres.put(nombre, p);

      1. Gaspar Fernández / Post Author
        Usando Mozilla Firefox Mozilla Firefox 61.0 en Ubuntu Linux Ubuntu Linux

        Exacto, nos interesa tener el Hashmap como privado para poder limitar lo que podemos hacer con él desde fuera. El método add() simplemente crea un objeto de tipo Piloto y lo añade al HashMap.

  4. Kunal Tomar /
    Usando Google Chrome Google Chrome 118.0.0.0 en Windows Windows NT

    You should contact us if you want a woman who can unwind as you pass by when you are on an upward trek. As a result, you may choose from most model Escorts in Delhi at our agency. Delhi Call Girls Service She will let you unwind while you travel a distance, giving you greater pleasure and elevating the value of your adventure.

  5. Kunal Tomar /
    Usando Google Chrome Google Chrome 118.0.0.0 en Windows Windows NT

    If you want to take our girl on a romantic date or to a surprising place for romance, then our girls are ready to go with you. Our Delhi Escorts Service will drive you to the different worlds of fantasy and give lots of love to feel satisfied. They can make you comfortable with them, and every single moment you spend with them, that moment will become memorable for you.

  6. Rahian Khan /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    Searching for a really hot suggestive back rub in? Then, at that point, you ought to call our escort office in and book a few hot modest escorts for provocative tomfoolery. These modest Ghaziabad Escort in will give you bare back rub on the web and will improve your time than at any other time. Presently you really want to get our internet based call number and message us on WhatsApp to book your modest escorts for the evening.

  7. muneer ahmed /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    definately enjoy every little bit of it and studio te huur I have you bookmarked to check out new stuff of your blog a must read blog!

  8. muneer ahmed /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    Waow this is quite pleasant article, my sister love to read such type of post, panties for women I am going to tell her and bookmarking this webpage. Thanks

  9. ghori92 /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    It a fabulous blog post As i looked at caused by have the application. Advise everything that Need be to find expectation on potential future you certainly will persist designed for writing a great wonderful blog post. carbon fiber pickleball paddle

  10. ghori92 /
    Usando Google Chrome Google Chrome 120.0.0.0 en Windows Windows NT

    This kind of is a wonderful submit My partner and i noticed as a result of discuss that. It is just what I desired to find out desire inside upcoming you may keep on regarding revealing this kind of outstanding submit. Beste taxibedrijven in Gent 2024

  11. yitzchak kerrigan /
    Usando Google Chrome Google Chrome 121.0.0.0 en Windows Windows NT

    This really fascinating put up not to mention i like to study this unique put up. your website might be awesome and also need fantastic people on your blog page. decent showing keep writing. motorcycle key replacement

  12. platform for trading /
    Usando Google Chrome Google Chrome 121.0.0.0 en Windows Windows NT

    the nation’s certainly fabulous web log. the nation’s realy informative together with a a great decent project. i want it. platform for trading

  13. ghori92 /
    Usando Google Chrome Google Chrome 121.0.0.0 en Windows Windows NT

    My partner and i astonished with all the examination an individual built to get this distinct distribute extraordinary. Great action! автовоз от германия

  14. yitzchak kerrigan /
    Usando Google Chrome Google Chrome 121.0.0.0 en Windows Windows NT

    Decent put up, her the most fascinating blog page which are in this case, cultivate monetary management give good results, could be spine. Solar panel supplier kenya

  15. Jadon Josephus /
    Usando Google Chrome Google Chrome 122.0.0.0 en Windows Windows NT

    Hiya, I am really glad I have found this information. Today bloggers publish just about gossips and web and this is really annoying. A good web site with exciting content, that is what I need. Thank you for keeping this site, I will be visiting it. Do you do newsletters? Can not find it.

    Investasi

  16. mustafa khan /
    Usando Google Chrome Google Chrome 122.0.0.0 en Windows Windows NT

    Pretty good post. I have just stumbled upon your blog and enjoyed reading your blog posts very much. I am looking for new posts to get more precious info. Big thanks for the useful info. forex robot

  17. MUZAMMIL SEO MUZAMMIL SEO /
    Usando Google Chrome Google Chrome 122.0.0.0 en Windows Windows NT

    I went over this website and I believe you have a lot of wonderful information, saved to my bookmarks forex robot

Leave a Reply