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
hashcode % n(nuevo)
... La verdad no veo muy bien cuál es la duda.