El rehash: cuándo y cómo se redimensiona una tabla

Si la parte array tiene un tamaño fijo N y la parte hash es una potencia de dos, la pregunta obvia es quién elige esos dos números y cuándo. La respuesta es un único procedimiento, rehash, que se dispara en un momento muy concreto —cuando hay que insertar una clave nueva y no queda ni un hueco libre en la dispersión— y que no ajusta nada de forma incremental: cuenta todas las claves de la tabla, resuelve un pequeño problema de optimización para decidir el tamaño del vector, reserva las dos partes de nuevo y reinserta todo. Es la operación más cara que le puede ocurrir a una tabla, es invisible desde el lenguaje, y es la responsable de que un bucle aparentemente lineal tenga un perfil de tiempos con dientes de sierra.

El disparador

Un rehash no ocurre al leer, ni al sobrescribir una clave existente, ni al asignar nil a una clave que ya estaba. Ocurre en un único punto: al insertar una clave nueva cuando la parte hash ya no tiene ningún hueco libre. La implementación mantiene un puntero lastfree que desciende por el vector de nodos buscando posiciones vacías; cuando ese puntero llega al principio sin encontrar ninguna, la inserción no puede continuar y llama a rehash.

Nota el detalle que sorprende a casi todo el mundo: la parte array nunca desborda por sí sola. Si escribes t[N+1] en una tabla cuyo vector llega hasta N, esa clave es, según la regla de la lección anterior, una clave más para la parte hash. Solo cuando la dispersión se llena y se convoca al rehash se recalcula el tamaño del vector, y solo entonces esa clave puede mudarse al camino rápido. El crecimiento del vector es, literalmente, un efecto secundario del agotamiento de la dispersión.

flowchart TD
A[Asignar t de k igual a v] --> B[La clave k ya existe]
B -->|si| C[Sobrescribir valor y terminar]
B -->|no| D[Queda algun hueco libre en la parte hash]
D -->|si| E[Ocupar hueco, encadenar y terminar]
D -->|no| F[Rehash]
F --> G[Contar claves enteras por rangos de potencias de dos]
G --> H[Elegir el mayor tamano con mas de la mitad de huecos ocupados]
H --> I[Reservar vector nuevo y dispersion nueva]
I --> J[Reinsertar todas las claves existentes]
J --> K[Insertar por fin la clave k]

El algoritmo que elige los dos tamaños

El corazón de rehash es un histograma. Se construye un vector nums donde nums[i] cuenta cuántas claves enteras de la tabla caen en el intervalo que va desde 2 elevado a i-1 sin incluirlo hasta 2 elevado a i incluido. Se recorren las dos partes de la tabla para rellenarlo, se cuenta también la clave nueva que provocó el redimensionado, y se acumulan dos totales: na, el número de claves enteras positivas, y totaluse, el número total de entradas vivas.

Con ese histograma se resuelve la decisión clave. Se recorren las potencias de dos de menor a mayor acumulando cuántas claves enteras caben por debajo de cada una, y se retiene la mayor potencia 2 elevado a i para la cual más de la mitad de los huecos entre 1 y ese valor están efectivamente ocupados.

-- Traduccion en Lua del criterio de computesizes, con fines didacticos.
local function tamano_optimo(nums)     -- nums[i] = claves en (2^(i-1), 2^i]
  local optimo, na_optimo = 0, 0
  local acumulado = 0
  local twotoi = 1
  for i = 0, 31 do
    acumulado = acumulado + (nums[i] or 0)
    if acumulado == 0 then break end
    if acumulado > twotoi // 2 then    -- mas de la mitad ocupada
      optimo, na_optimo = twotoi, acumulado
    end
    twotoi = twotoi * 2
  end
  return optimo, na_optimo             -- tamano del vector y claves que caben
end

Ese criterio de ocupación superior a la mitad es la garantía de diseño del vector: el desperdicio de la parte array está acotado por debajo del cincuenta por ciento. Nunca verás a Lua reservar un millón de huecos porque escribiste t[1000000], porque un solo elemento no supera la mitad de un millón. Y por eso mismo una tabla con claves dispersas jamás obtiene parte array por mucho que sus claves sean enteros positivos.

Merece la pena entender por qué el criterio es exactamente ese y no otro. Si se exigiera una ocupación menor —digamos, una cuarta parte—, el vector crecería con más facilidad y más claves disfrutarían del camino rápido, a cambio de tolerar hasta un setenta y cinco por ciento de huecos vacíos en tablas dispersas. Si se exigiera más —tres cuartas partes—, el desperdicio bajaría pero muchas secuencias con algún agujero perderían su vector y caerían a la dispersión, que es la peor de las dos opciones porque cuesta más memoria por entrada. La mitad es el punto donde la garantía de desperdicio acotado coincide con la condición de que el vector nunca sea peor que la dispersión: con más de la mitad ocupada, N huecos a nueve bytes siempre cuestan menos que las mismas entradas a veinticuatro.

Fijado el tamaño del vector en optimo, las claves que quedan fuera son totaluse - na_optimo, y ese es el número de entradas que debe alojar la nueva dispersión, cuyo tamaño se redondea hacia arriba a la siguiente potencia de dos. Después viene el reinsertado: se recorre la tabla antigua y cada clave se vuelve a colocar según la regla habitual, lo que significa que muchas claves que estaban en la dispersión aterrizan ahora en el vector, y que las que estaban en el vector por encima del nuevo tamaño hacen el viaje contrario.

Coste amortizado y bucles calientes

Un rehash es O de n sobre el número de entradas vivas: hay que contarlas todas y reinsertarlas todas. Que eso no arruine el rendimiento depende de un argumento de amortización idéntico al del vector dinámico clásico. Como el tamaño resultante siempre deja hueco libre —la parte hash se redondea a una potencia de dos y el criterio de la mitad implica que el vector puede aceptar al menos tantas claves nuevas como las que ya tiene—, entre dos rehashes consecutivos hay que hacer un número de inserciones proporcional al tamaño actual. El coste lineal se reparte entre esas inserciones y el coste por inserción es constante amortizado. Construir una secuencia de un millón de elementos elemento a elemento hace del orden de veinte rehashes, no un millón.

Vale la pena ver la traza de un caso concreto para que el argumento deje de ser abstracto. Supón una tabla vacía a la que insertas las claves 1, 2, 3 y así sucesivamente:

-- Insercion 1: no hay dispersion, rehash. nums[0] = 1 clave en (0,1].
--              1 > 1/2, luego vector de tamano 1. Dispersion vacia.
-- Insercion 2: la clave 2 no cabe en el vector, va a la dispersion,
--              que esta llena. Rehash: 2 claves, vector de tamano 2.
-- Insercion 3: mismo mecanismo. Rehash: 3 claves, vector de tamano 4.
-- Insercion 4: cabe en el vector. Sin rehash.
-- Insercion 5: rehash. 5 claves, vector de tamano 8.
-- Inserciones 6, 7, 8: caben. Sin rehash.
-- Insercion 9: rehash. Vector de tamano 16. Y asi sucesivamente.

Los rehashes ocurren en las inserciones 1, 2, 3, 5, 9, 17, 33… es decir, en las potencias de dos más uno. Para un millón de inserciones son veintiún rehashes, y el trabajo total de reinsertado es la suma de una serie geométrica acotada por el doble del tamaño final. De ahí el coste constante amortizado.

Amortizado no significa gratis, y hay tres consecuencias prácticas que sí duelen:

-- 1. Preasignar: Lua 5.5 expone table.create(tam_secuencia [, tam_resto])
local t = table.create(1000000)
for i = 1, 1000000 do t[i] = i * i end     -- cero rehashes

-- 2. Reutilizar en lugar de recrear dentro del bucle caliente
local buf = table.create(64)
for _, linea in ipairs(entrada) do
  for i = #buf, 1, -1 do buf[i] = nil end  -- vaciar sin soltar el vector
  procesar(linea, buf)
end

-- 3. El constructor tambien preasigna: el compilador emite el tamano
local punto = { x = 0, y = 0, z = 0 }      -- dispersion de tamano 4, sin rehash

Desde C el equivalente es lua_createtable(L, narr, nrec), que es exactamente lua_newtable con las dos capacidades declaradas por adelantado; en LuaJIT, donde no existe table.create, el idioma es require("table.new"). En cualquier caso la regla es la misma: si sabes cuántos elementos va a tener la tabla, decirlo cuesta un argumento y ahorra todos los rehashes.

Lo que el rehash no hace

Igual de importante que saber cuándo se dispara es saber cuándo no se dispara, porque casi todas las sorpresas de memoria salen de ahí. Un rehash solo puede ocurrir al insertar una clave nueva sin sitio. En consecuencia, una tabla nunca encoge sola.

local t = table.create(0, 1024)
for i = 1, 1000 do t["clave" .. i] = i end
-- La dispersion tiene 1024 nodos ocupados.

for i = 1, 1000 do t["clave" .. i] = nil end
-- Sigue teniendo 1024 nodos reservados y 1000 claves muertas
-- que mantienen vivas sus cadenas. No se ha liberado nada.

t.disparador = true
-- ESTA insercion encuentra la dispersion llena de claves muertas,
-- convoca al rehash, cuenta una sola entrada viva y reserva
-- una dispersion minima. Aqui, y solo aqui, baja la memoria.

El patrón es contraintuitivo pero completamente coherente con el diseño: como el borrado no libera nada, la única forma de recuperar la memoria de una tabla que ha adelgazado es forzar una inserción o, más honestamente, construir una tabla nueva y dejar que la vieja muera. La biblioteca ofrece table.move precisamente para eso, porque copia un rango de una tabla a otra sin pasar por Lua elemento a elemento.

Tampoco disparan un rehash la sobrescritura de una clave existente, la lectura de una clave ausente ni el cambio de metatabla. Y hay un caso límite que merece la pena tener presente: si la parte hash está llena de claves muertas, la inserción de una clave nueva provoca un rehash que reduce el tamaño en lugar de aumentarlo, de modo que un rehash no es sinónimo de crecimiento. Es, literalmente, un recálculo desde cero.