Páginas

20/7/16

Que es un HashMap y cómo funciona

Que es un HashMap y cómo funciona.

Que es un HashMap y cómo funciona.




Pregunta fija para una entrevista, a veces trabajamos con HashMap pero no sabemos en realidad el concepto del mismo y menos como funciona internamente. Un HashMap es la implementación de la interface Map, esta interface es un tipo de
CollectionUna Collection es una interface que agrupa un conjunto de elementos.
que almacena datos asociando una
llave a un valorMap<key, value>. key= la llave. value= String, Integer, Boolean...
, esta interface sirve para muchas cosas y tiene ciertas caracteristicas que la definen, por ejemplo, no permite key duplicados, cada key tiene que estar asociado a un valor como máximo, si agregas un key que ya existe sobrescribe el valor del key anterior, solo permite Object types lo que quiere decir que no puedes poner un valor primitivo...
Volviendo al tema casi siempre se utiliza el HashMap como implementación del Map pero tiene sus cosas, por ejemplo, no garantiza que los elementos que vamos agregando estén ordenados, no deberíamos usarla en aplicaciones multithread porque no es synchronized, pero como todo en el mundo de Java, esto se puede lograr con unas líneas de código.

El HashMap funciona con el
principio del hashingEl principio se basa en asignar una ubicación para cierta key, dependiendo de una key determinada se le asigna un id único, en este caso se utiliza el método hashCode() el cual heredan todos los objetos en Java, algo importante de resaltar es que un objeto solo retornara un id, lo que quiere decir que si invocamos el hashcode con otro objeto idéntico devolverá el mismo id.
, como ya explique trabaja asignando una ubicación a una key con el método hashCode() de Java.

Comenzando desde el principio, así podemos crear un HashMap:
  // Un HashMap simple de llave String y valor Integer.
     HashMap<String, Integer> hashMapEdad = new HashMap<String, Integer>();
    
El constructor del HashMap que invocamos automáticamente le asigna la
capacidadLa capacidad o tamaño inicial del HashMap va ser 16.
y el
load factorEl load factor por defecto es 0.75, este valor indica que ese es el máximo de items que puede tener un HashMap dependiendo de su capacidad, por ejemplo, si la capacidad es 100 solo puede tener 75 items, en el caso de aumentar a 76 ítems la capacidad automáticamente aumenta al doble.
.
  /**
   * Constructs an empty HashMap with the default initial capacity
   * (16) and the default load factor (0.75).
   */
  public HashMap() {
   this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }
    
En el ejemplo vamos a utilizar un HashMap para guardar la edad de ciertas personas, tenemos a Pedro, Pepe y Jose, vamos agregarlos para ver cómo funciona el HashMap internamente:
  // Con el metodo put() agregamos un item al HashMap.
     hashMapEdad.put("Pedro", 21);
    
Este es el código del método put():
  public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
    
Explicando el método put() al agregar a Pedro:
  • Línea 2: como el HashMap está vacío se inicia la
    listaUn HashMap internamente es una lista.
    , se le asigna el tamaño y el límite de ítems que pueden haber.
  • Línea 7: se calcula el hash de esta key con el método HashCode().
  • Línea 8: con el hash se calcula un índice en el hashMap para esta key.
  • Línea 9: esta es la parte más complicada, como mencione anteriormente en el tooltip del "principio del hashing", dos objetos idénticos tendrán el mismo id retornado por el método hashCode(), como en la linea 8 se calcula el índice en donde va a ir el item puede ocurrir una colision si calculamos índices con el mismo id, la solución que implementa el metodo put() para esto es la clase anidada Entry que posee HashMap, esta clase contiene un atributo de tipo LinkedList el cual se utiliza para agregar los ítems como si de una LinkedList se tratará, lo que funcionará para obtener el valor si hay una colision en el HashMap.
  • Después de toda esa lógica se procede agregar el ítem al HashMap.
Suponiendo que ya agregamos a "Pepe" y a "Jose":
  hashMapEdad.put("Pepe", 35);
  hashMapEdad.put("Jose", 15);
    
Y ahora queremos obtener la edad de "Pepe", es prácticamente el mismo concepto del método put(), solo que invocamos el método get(key) pasándole como parámetro la key, en este caso el nombre de la persona de la cual queremos obtener la edad y este internamente busca el hash de la key y retorna el valor.
 // Obtener la edad de Pepe
 int edad = hashMapEdad.get("Pepe");
    
Esto retorna la edad de "Pepe". Muchas veces necesitamos recorrer un HashMap y podemos hacerlo de varias maneras, pero la que yo recomiendo por sencillez y facilidad es con el bucle foreach:
 for(String key: hashMapEdad.keySet()){
     System.out.println(key + " tiene " + hashMapEdad.get(key) + " años de edad.");
 }
    
Esto imprime:
  Pedro tiene 21 años de edad.
  Jose tiene 15 años de edad.
  Pepe tiene 35 años de edad.
    
Como se puede observar en la salida de la consola los resultados no están ordenados, para ordenar un HashMap podemos utilizar TreeMap de esta manera.
  TreeMap<String, Integer> treeMap = new TreeMap<String, Integer>(hashMapEdad);
  for (String key : treeMap.keySet()) {
   System.out.println(key + " tiene " + treeMap.get(key) + " años de edad.");
  }
    
Esto imprime:
  Jose tiene 15 años de edad.
  Pedro tiene 21 años de edad.
  Pepe tiene 35 años de edad.
    
Para pasar los keys o valores de un HashMap a un ArrayList:
  ArrayList<String> keyList = new ArrayList<String>(hashMapEdad.keySet());
  ArrayList<Integer> valueList = new ArrayList<Integer>(hashMapEdad.values());
    
Si en algún momento queremos hacer que un HashMap sea synchronized:
  Map map= Collections.synchronizedMap(hashMapEdad);
    
Esto hace que todos los métodos del HashMap sean synchronized y por ende se pueda usar en aplicaciones multithread. Este pequeño repaso siempre cae bien, tanto para el trabajo, estudio como para una entrevista, si tienes alguna duda, quieres que agregue algo interesante o importante al artículo no dudes en dejar tu comentario, suerte.

4 comentarios :