La representación dual: toda tabla son dos tablas

Ya sabes que la tabla es el único tipo compuesto de Lua y que hace de array, de diccionario, de objeto y de módulo. Eso es cierto en la superficie del lenguaje y falso en la implementación: desde Lua 5.0 cada tabla lleva dentro dos estructuras de datos distintas, con costes distintos, y una única regla que decide en cuál acaba cada clave. Ningún programa Lua puede observar esa frontera —no existe función que te diga si t[7] vive en el vector o en la dispersión—, pero todo programa Lua la paga. La diferencia entre un bucle que recorre un millón de posiciones a velocidad de C y uno que hace un millón de búsquedas con hash está exactamente ahí, y no aparece en ninguna línea de tu código. Este nivel entero consiste en aprender a ver esa frontera invisible.

Dos estructuras bajo una sola cabecera

Una tabla en el intérprete de referencia es una cabecera pequeña que apunta a dos bloques de memoria independientes. La cabecera cabe holgadamente en una línea de caché y es lo único que existe siempre; los dos bloques pueden estar vacíos, y de hecho una tabla recién creada con {} no tiene ni parte array ni parte hash reales.

typedef struct Table {
  CommonHeader;
  lu_byte flags;       /* cache de metametodos ausentes */
  lu_byte lsizenode;   /* log2 del tamano de la parte hash */
  unsigned int alimit; /* limite de la parte array */
  TValue *array;       /* parte array: SOLO valores, sin claves */
  Node *node;          /* parte hash: clave + valor + enlace */
  Node *lastfree;      /* por debajo de aqui no quedan huecos libres */
  struct Table *metatable;
  GCObject *gclist;
} Table;

Las dos asimetrías importantes están en los tipos. La parte array es un TValue *: una secuencia de valores desnudos, sin claves, porque la clave de la posición i es implícitamente i. La parte hash es un Node *: cada entrada guarda su clave completa (valor y etiqueta de tipo), su valor y un entero next para resolver colisiones. Guardar la clave no es opcional en una dispersión, y ahí nace toda la diferencia de coste.

Los dos campos restantes de la cabecera merecen una nota, porque explican dos comportamientos que se atribuyen a magia. El puntero metatable es nulo mientras no le asignes una, y flags es una caché de un byte donde cada bit recuerda que un metamétodo concreto no existe en esa metatabla. Gracias a ese byte, una operación como sumar dos tablas sin metatabla no paga una búsqueda de __add: paga una comprobación de bit. Es el mismo principio que la parte array llevado al terreno de los metamétodos, y por eso el nivel de metatablas y este comparten más de lo que parece.

Una tabla recién creada con {} tiene los dos punteros de datos apuntando a estructuras vacías. El vector es sencillamente nulo con tamaño cero; la dispersión apunta a un nodo ficticio compartido por todo el estado, de solo lectura, cuya única función es que el código de búsqueda no tenga que comprobar si existe parte hash antes de leerla. Crear una tabla vacía cuesta, por tanto, una cabecera y nada más.

El tamaño de la parte hash es siempre una potencia de dos —se guarda su logaritmo en un solo byte, lsizenode— porque así el módulo de la función de dispersión se reduce a una operación de bits. El tamaño de la parte array no tiene esa restricción teórica, pero en la práctica el algoritmo que lo calcula produce potencias de dos, como verás en la lección siguiente.

flowchart TD
K[Clave k] --> N[Normalizar flotante a entero si su valor es integral]
N -->|entero entre 1 y el limite del array| A[Parte array]
N -->|cualquier otra clave| H[Parte hash]
A --> AV[Indice directo sin comparar claves]
H --> P[Posicion principal segun el hash de la clave]
P -->|libre| I[Ocupar esa posicion]
P -->|ocupada por un intruso| B[Mover al intruso y encadenar]

La regla que decide, clave por clave

La regla completa cabe en una frase: una clave va a la parte array si y solo si es un entero k tal que 1 <= k <= N, donde N es el tamaño actual de la parte array; cualquier otra clave va a la parte hash. No hay excepciones, no hay heurísticas adicionales, no hay tipos privilegiados más allá del entero positivo pequeño.

Antes de aplicar la regla, Lua normaliza. Un flotante cuyo valor es matemáticamente entero y cabe en un lua_Integer se convierte a entero, de modo que t[2.0] y t[2] son literalmente la misma clave. Esta normalización ocurre en la búsqueda y en la inserción, y es la razón de que una tabla nunca contenga dos entradas para el mismo número escrito de dos formas.

local t = {}
t[2] = "a"
t[2.0] = "b"          -- misma clave, sobrescribe
print(t[2])           --> b

t[0/0] = 1            -- error: table index is NaN
t[nil] = 1            -- error: table index is nil
t[2.5] = "c"          -- valido: clave flotante, va a la parte hash

Las dos claves prohibidas lo están por razones distintas. nil no puede ser clave porque el valor nil es precisamente la marca de ausencia: permitirlo haría indistinguible «no hay entrada» de «hay una entrada cuya clave es nada». NaN no puede ser clave porque no es igual a sí mismo, y una tabla de dispersión que no puede reencontrar una clave a partir de sí misma está rota por construcción. Ambos casos se aceptan en lectura —t[nil] devuelve nil sin error— y solo fallan al escribir.

Para las claves de tipo cadena hay un detalle que explica por qué usar cadenas como claves es tan barato en Lua: las cadenas cortas están internadas. Solo existe una copia de cada cadena corta en todo el estado, con su hash calculado en el momento de crearla. Comparar dos claves de cadena corta es, por tanto, comparar dos punteros, y calcular su posición principal es leer un campo. Las cadenas largas —por encima del umbral de la implementación— no se internan y calculan su hash de forma perezosa, la primera vez que se usan como clave.

Así queda un nodo de la parte hash, ya empaquetado a mano desde Lua 5.4 para que las dos etiquetas y el enlace compartan los huecos que dejaría la alineación:

typedef union Node {
  struct NodeKey {
    Value value_;       /* 8 bytes: el valor */
    lu_byte tt_;        /* 1 byte:  etiqueta del valor */
    lu_byte key_tt;     /* 1 byte:  etiqueta de la clave */
    int next;           /* 4 bytes: enlace de colision */
    Value key_val;      /* 8 bytes: la clave */
  } u;                  /* 24 bytes en total, solo 2 de relleno */
  TValue i_val;         /* acceso al valor como TValue completo */
} Node;

Veinticuatro bytes por entrada frente a los dieciséis —nueve desde Lua 5.5— que cuesta un hueco del vector. Y no es solo memoria: la clave hay que compararla, y el enlace hay que seguirlo.

La parte hash resuelve colisiones con dispersión encadenada sobre el propio vector de nodos, usando la variación de Brent. Cada clave tiene una posición principal determinada por su hash. Si esa posición está libre, la ocupa. Si está ocupada por una clave cuya posición principal es esa misma, la nueva se coloca en un hueco libre cualquiera y se encadena mediante el campo next. Y si está ocupada por un intruso —una clave que colisionó desde otra posición principal—, es el intruso quien se muda, y la recién llegada se queda con la posición que le corresponde. El resultado es que la cadena de colisiones de una clave siempre empieza en su posición principal, lo que acorta las búsquedas fallidas.

Por qué el array es rápido sin que existan arrays

El acceso a la parte array no es «más o menos» rápido: es una comparación y una indexación. La implementación usa un truco de aritmética sin signo para verificar las dos cotas con una sola comparación.

const TValue *luaH_getint (Table *t, lua_Integer key) {
  lua_Unsigned k = l_castS2U(key) - 1u;   /* desplaza el rango a 0 .. N-1 */
  if (k < t->alimit)                      /* cubre k < 1 y k > N a la vez */
    return &t->array[k];                  /* acceso directo, sin comparar claves */
  /* ... camino lento: buscar en la parte hash ... */
}

Si key es cero o negativa, la resta sin signo produce un número enorme que falla la comparación; si es mayor que el límite, falla igual. Una resta, una comparación y una lectura indexada. Ningún hash, ninguna comparación de claves, ninguna cadena de colisiones que recorrer.

Compara eso con el camino de la dispersión, que en el mejor de los casos es: calcular o leer el hash, reducirlo módulo el tamaño, leer el nodo de esa posición, comparar la etiqueta de tipo de su clave con la buscada, comparar el valor de la clave, y —si no coincide— seguir el campo next hasta agotar la cadena. Media docena de operaciones y al menos un salto dependiente de datos en el mejor caso, frente a tres instrucciones sin ramificación. Esa es la razón, y la única, de que exista la parte array.

La frontera se filtra en el recorrido

Dijimos que ningún programa Lua puede observar la frontera, y es cierto en el sentido estricto: no existe consulta que la revele. Pero sí se filtra, y el sitio por donde lo hace es el recorrido genérico. La función next —el motor de pairs— está obligada a visitar todas las entradas de la tabla exactamente una vez, y para conseguirlo recorre primero el vector de principio a fin, saltándose los huecos vacíos, y después el vector de nodos en su orden de almacenamiento.

local t = {}
t.zeta = 1
t.alfa = 2
t[1] = "uno"
t[2] = "dos"

for k, v in pairs(t) do print(k, v) end
-- Imprime 1 y 2 antes que las claves de texto, casi siempre.
-- Y el orden relativo de zeta y alfa depende de sus hashes,
-- que dependen de la semilla aleatoria del estado de Lua.

De ahí salen tres consecuencias que conviene tener claras. La primera es que ver los índices numéricos aparecer en orden al principio de un pairs es un artefacto de la implementación, no una garantía: en cuanto una de esas claves viva en la dispersión, el orden se rompe. La segunda es que el orden de las claves no numéricas es genuinamente impredecible entre ejecuciones, porque las cadenas cortas se dispersan con una semilla que cambia en cada estado para dificultar ataques por colisiones; cualquier código que dependa de ese orden es incorrecto aunque funcione hoy. La tercera es la regla que el manual enuncia y que ahora entiendes: durante un recorrido con next puedes asignar nil a claves existentes, pero no puedes añadir claves nuevas, porque una clave nueva puede desencadenar un redimensionado que reubique todo y deje al iterador señalando a un sitio que ya no significa lo mismo.