Tablas hash y montículos

En cualquier estructura vista hasta ahora, encontrar un dato exige recorrer o comparar. La tabla hash cambia el planteamiento: en lugar de buscar dónde está un elemento, calcula dónde debe estar. Una función hash transforma la clave en un número, y ese número es directamente el índice de la casilla (o cubeta) donde el elemento se guarda.

La función hash más sencilla es el resto de la división entera por el tamaño de la tabla, porque garantiza que el resultado cae siempre dentro del rango de casillas disponibles. Es la misma operación que sitúa el índice de escritura en un buffer circular: cuando se llega al final, el resto devuelve el índice al principio.

// Tabla de 250 casillas: la función reparte cualquier clave entre 0 y 249.
posicion(clave) = clave mod 250

posicion(1024)  ->  24
posicion(1274)  ->  24     // colisión: 1274 = 1024 + 250
posicion(  37)  ->  37

La tabla hash es la estructura del acceso por clave: da tiempo constante en promedio, pero no mantiene ningún orden entre sus elementos. Si hace falta recorrer los datos ordenados, la estructura correcta es un árbol de búsqueda, no una tabla hash.

Como la función hash comprime un universo enorme de claves posibles en un número limitado de casillas, tarde o temprano dos claves distintas dan el mismo resultado. Eso es una colisión, y no es un fallo evitable: es matemáticamente inevitable en cuanto hay más claves que casillas.

Lo que sí depende del diseño es la frecuencia con la que ocurren. Una función hash que reparta mal, o una tabla demasiado pequeña para los datos que va a guardar, amontonan claves en las mismas casillas. Y ahí se pierde justo la ventaja que se buscaba: la posición ya no identifica un único elemento, así que hay que recorrer los que comparten casilla comparándolos uno a uno.

El acceso a una tabla hash es O(1) en caso medio, pero O(n) en el peor caso, cuando todas las claves colisionan en la misma casilla y la estructura degenera en una lista.

Hay dos familias de solución, y se distinguen por dónde acaba el elemento que llega a una casilla ocupada.

• Encadenamiento separado: cada casilla guarda una lista con todos los elementos que le han tocado. La tabla nunca se llena, y la búsqueda dentro de la casilla es lineal en el número de colisionados.
• Direccionamiento abierto: todo se guarda dentro del propio array, y cuando la casilla está ocupada se prueba otra siguiendo una regla fija. Con sondeo lineal se prueba la siguiente casilla; con sondeo cuadrático se salta cada vez más lejos; con hash doble el salto lo decide una segunda función hash.

El factor de carga mide cuán llena está la tabla: es el número de elementos dividido entre el número de casillas. Cuanto más alto, más colisiones. Cuando supera un umbral (típicamente en torno a 0,75 con encadenamiento) se hace un rehashing: se crea una tabla mayor y se recolocan todos los elementos, porque su posición depende del tamaño de la tabla y ya no sirve la anterior.

Con direccionamiento abierto la tabla puede llenarse y el rendimiento se hunde al acercarse el factor de carga a 1; con encadenamiento solo se degrada progresivamente.

Un montículo (heap) es un árbol que cumple una condición local repetida en todos sus nodos: cada padre está ordenado respecto a sus hijos. En un max-heap todo nodo es mayor o igual que sus descendientes, con lo que el mayor de todos queda en la raíz. En un min-heap ocurre lo contrario y la raíz guarda el mínimo.

Conviene entender qué NO garantiza esa propiedad. El montículo no está ordenado: solo sabe quién es el mayor (o el menor). Entre dos hermanos no hay ninguna relación establecida, y por eso recorrer un montículo no devuelve los datos en orden.

Cuando el árbol es binario se llama montículo binario, y como además es un árbol completo (todos los niveles llenos salvo quizá el último, que se rellena de izquierda a derecha) se puede guardar en un array sin un solo puntero: la aritmética de índices sustituye a los enlaces.

// Montículo binario guardado en un array, sin punteros.
hijo izquierdo de i  ->  2i + 1
hijo derecho de i    ->  2i + 2
padre de i           ->  (i - 1) div 2

array:  [90, 70, 80, 30, 40, 10]

                 90
               /    \
             70      80
            /  \     /
          30    40  10

Al insertar, el elemento se coloca en la primera posición libre y va subiendo mientras sea mayor que su padre. Al extraer la raíz, el último elemento pasa a ocupar su lugar y va bajando mientras sea menor que alguno de sus hijos. Las dos operaciones recorren como mucho la altura del árbol, y la altura de un árbol binario completo con n nodos es logarítmica.

Insertar y borrar en un montículo son O(log n), no O(n log n). El O(n log n) aparece al construirlo insertando los n elementos uno a uno, y ni siquiera es la mejor forma: heapify lo construye en O(n).

Buscar un elemento arbitrario es O(n) porque la propiedad de montículo no sirve para decidir por qué rama bajar. Si el problema exige buscar, la estructura adecuada es otra: un árbol de búsqueda o una tabla hash.