1

Tengo entendido que cuando declaramos un map como el siguiente:

Map<String, Integer> map = new HashMap();

El factor de carga por defecto es de 0.75 y su tamaño es de 16, cuando los buckets del map superan la cantidad de 12 elementos el tamaño cambia a 32.

Sin embargo la forma en la que el map escoge el index del bucket donde colocará el objeto al usar la función put, se define por hascode % n pero ¿Qué ocurre cuando el tamaño del map supera el factor de carga? n ya no tiene el mismo valor, por lo tanto ¿Cómo puede encontrar las entradas previamente seteadas si al aplicar hascode % n el index resultante no será el mismo que antes?

¿A las entradas que ya estaban se les volverá a asignar un nuevo index? Si es así, ¿No es algo ineficiente?

5
  • Así sin mirar el código, al montar la nueva estructura se guardan los valores de acuerdo a hashcode % n(nuevo)... La verdad no veo muy bien cuál es la duda.
    – SJuan76
    Commented el 26 oct. 2018 a las 7:38
  • Pero a los valores que ya estaban insertados, ¿Los vuelve a insertar? ¿Eso no es ineficiente? Commented el 26 oct. 2018 a las 7:41
  • 1
    Por eso cuando amplía el tamaño no añade uno o dos buckets sino que lo dobla, y te deja especificar el tamaño en uno de los constructores, para minimizar en lo posible el número de esos cambios. Además, de todas formas lo que hace es crear un nuevo array que almacena los datos, así que sea a la posición que sea, los datos se han de mover.
    – SJuan76
    Commented el 26 oct. 2018 a las 7:49
  • Ten en cuenta que la "asignación de un nuevo índice" es hacer la operación "a % b". La creación de las nuevas estructuras internas y la copia desde las antiguas puede ser algo de tiempo para hashmaps MUY grandes, calcular el nuevo índice es prácticamente instantáneo.
    – SJuan76
    Commented el 26 oct. 2018 a las 7:59
  • Ahora entiendo, ¿Podrías ponerlo como respuesta? Commented el 26 oct. 2018 a las 8:05

1 respuesta 1

3

La implementación de HashMap usa un array para guardar los nodos:

Node<K,V>[] table;

El tamaño de este array siempre es potencia de 2, empezando por 16. Cada vez que se llega al límite de ocupación, el tamaño de la tabla se dobla. Por tanto, cada vez que se tiene que reasignar un nodo se va a quedar en la misma posición P o se va a mover hasta P + antigua_capacidad.

Pongo un ejemplo con tamaños pequeños:

Imaginemos que guardamos elementos con unas claves cuyo hash es:

1, 2, 7, 4, 5, 9, 13, 17, 18, 19, 10

Empezamos con una tabla de 4 posiciones, que se incrementa a 8 con el tercer elemento, y al llegar a 6 se volverá a incrementar:

0 |     0 |        0 |
1 | 1   1 | 1 9    1 | 1 17
2 | 2 ->2 | 2      2 | 2 18
3 | 7   3 | 3      3 | 3 19
        4 | 4      4 | 4
        5 | 5  --> 5 | 5
        6 |        6 |
        7 | 7(P+4) 7 | 7
                   8 |
                   9 | 9 (P+8)
                  10 | 10
                  11 |
                  12 |
                  13 | 13 (P+8)
                  14 |
                  15 |

El algoritmo para reubicar cuando se incrementa la tabla es el siguiente (obtenido de aquí):

for (int j = 0; j < oldCap; ++j) {
    Node<K,V> e;
    if ((e = oldTab[j]) != null) {
        oldTab[j] = null;
        if (e.next == null)
            newTab[e.hash & (newCap - 1)] = e; // ***Elección de nueva posición ***
        else if (e instanceof TreeNode)
            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        else { // preserve order
            Node<K,V> loHead = null, loTail = null;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do { // *** bucle para colocar la cola de elementos que colisionaban ***
                next = e.next;
                if ((e.hash & oldCap) == 0) {
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                }
                else {
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
            } while ((e = next) != null);
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) {
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}

Exceptuando los casos en los que los nodos que colisionan sean TreeNodes1 , todo es muy directo: se mira el hash del elemento (que ya está precalculado en el nodo) y se elije si el índice será el mismo o si se moverá sumando la antigua capacidad.

Por tanto el coste es O(n), no especialmente costoso.

1En lugar de una lista parece que se usa un arbol binario para las colisiones, no tengo claro cuando se usa un sistema u otro

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.