Tablas hash
¿Dónde encuentro el capítulo que me interesa de un libro? ¿A dónde se dirige el pedido de Ana García? ¿Dónde puedo comprar ese reloj con la correa de cuero marrón? Lo que estas frases tienen en común, además de que son preguntas, es que preguntan por un lugar: ¿dónde? ¿adónde? Otro punto en común es que las tres suponen que el objeto buscado existe. Esta estructura de pensamiento puede usarse fácilmente como ejemplo de lo que sucede en una base de datos.
Imagina una tienda online con miles de artículos y de clientes. Los datos de todos ellos se almacenan en bases de datos: el cliente busca en una base de datos un artículo concreto y hace su pedido; el expedidor usa una base de datos para asignar el artículo al comprador y a su dirección postal. Este proceso conlleva tareas de clasificación, adición y eliminación mientras se realiza el pedido. Para poder gestionarlas de forma más eficiente, se resumen grandes cantidades de datos con elementos en común en una posición de dirección en la base de datos. Dicha posición se calcula con valores hash y está compuesta por una tabla con combinaciones de cifras y letras, todas de la misma longitud. En este artículo te explicamos los conceptos básicos para que puedas usar tablas hash (hash tables).
¿Qué principio sigue una tabla hash?
A partir de los datos de un registro se calcula, en primer lugar, un valor hash. Los valores hash de todos los registros de una base de datos se guardan en la tabla hash. Mediante otra operación matemática, a partir del valor hash se calcula la ubicación de dicha información en la base de datos. Si el usuario introduce entonces un término en el campo de búsqueda, este término también se hashea. A partir de entonces, por lo tanto, ya no se busca “reloj con la correa de cuero marrón”, sino una coincidencia entre el valor hasheado inicialmente para el artículo y el valor hash del término buscado en ese momento. En otras palabras, se busca una coincidencia entre dos combinaciones de cifras y letras. Este enfoque se usa para todo tipo de aplicaciones.
Seguridad con valores hash
Una tabla hash es el resultado de asignar hashes generados automáticamente a ciertos términos de búsqueda. Para ello se usa una función hash, que genera una secuencia de caracteres con una longitud constante llamada hash. La longitud de la secuencia y los caracteres que la forman son establecidos por el método hash que se esté utilizando. Este método se usa, por ejemplo, para proteger datos de acceso frente al robo de datos.
En los inicios de sesión registrados en la base de datos de la imagen, la contraseña introducida por el usuario se convierte a un valor hash mediante el mismo procedimiento. Este valor se coteja entonces con la entrada que le corresponde en el campo user_pass de la base de datos. Si ambos hashes de 34 caracteres coinciden, se concede el acceso. En sentido opuesto, no es posible descifrar una contraseña a partir de un valor hash: esta es una de las cualidades de las funciones hash.
Si el intento de acceso no autorizado, en cambio, se basa en un ataque de fuerza bruta, la secuencia debe probarse usando todos los caracteres permitidos hasta dar con una coincidencia exacta. Si se incluyen minúsculas, mayúsculas y números, y suponiendo que el atacante conozca la función hash utilizada, una contraseña de 10 caracteres requeriría exactamente 839.299.365.868.340.200 intentos para dar a ciencia cierta con la combinación correcta.
Acelerar los procesos de las bases de datos
En las bases de datos se utilizan tablas hash para acelerar los procesos de búsqueda, de registro y de eliminación de conjuntos de datos. Imaginemos que se busca un apellido en una base de datos que incluya a todos los trabajadores de una empresa: la tarea puede llevar mucho tiempo porque, de manera convencional, se busca la coincidencia en cada uno de los campos de la base de datos, uno tras otro (de manera secuencial). Si, en cambio, se convierte el término de búsqueda en un valor hash para luego buscarlo en la tabla hash, el proceso suele llevar mucho menos tiempo.
¿Cómo se hace esto exactamente? A cada conjunto de datos se le asigna una dirección inequívoca. Las reglas que rigen esta asignación son siempre las mismas dentro de cada base de datos (001, 002, 003 o 00A1, 00A2, 00A3, etc.). La dirección se calcula con ayuda de la función hash.
Como ejemplo sencillo, pongamos que tenemos una base de datos con espacio para 11 entradas, en las posiciones de 0 a 10. El nombre Lisa está formado por 4 caracteres ASCII, cada uno con un código ASCII: L es 76, i es 105, s es 115 y a es 97. Puedes comprobar esta asignación tú mismo usando el teclado numérico: verás que con [Alt] + 0076, por ejemplo, se muestra una L. Se suman entonces todos los valores ASCII de Lisa, dando como resultado el valor hash 393. En este caso, la suma de los valores ASCII corresponde a una función hash.
A continuación, se realiza un cálculo del residuo con números enteros: 393 % 11 (entradas que caben en la base) = 35, residuo 8 (en muchos lenguajes de programación el símbolo de porcentaje % corresponde al operador matemático del cálculo del residuo). Este residuo será el que determine en qué lugar de la base de datos (en nuestro cálculo de ejemplo, el índice número 8) se guardará Lisa y todos los datos relacionados con ella. Como ya habrás imaginado, en este tipo de direccionamiento, los residuos resultantes a menudo se repiten. Cuanto más espacio de almacenamiento y más largo sea el valor hash utilizado, menor será la probabilidad de que ocurran tales repeticiones. En el caso del nombre Alis, aunque las letras del nombre coincidan con las de Lisa, el posicionamiento sería diferente, ya que la A es mayúscula y la L es minúscula.
En la imagen anterior podemos ver un problema de repetición: es posible que nombres distintos reciban los mismos valores de índice, causando así las llamadas colisiones (flechas azul claro). ¿Cómo reacciona la base de datos ante este obstáculo? Ubica el registro en la posición libre más cercana. Así, si se busca Berta Torres, por ejemplo, la búsqueda no comenzará en la posición 001, sino que el puntero de búsqueda irá directamente a la posición de índice 003, lo cual supone una (ligera) aceleración del proceso. Este método, en el que luego se busca de forma lineal, se conoce como hashing con direccionamiento abierto (o sondeo lineal).
Por su parte, el método del hashing encadenado (chaining) funciona de manera diferente: no se abre ningún conjunto de datos nuevo, sino que se va encadenando el primer conjunto de datos coincidente con el siguiente. De esta manera, el conjunto de datos buscado se localiza con una sola solicitud de búsqueda, ya que está localizado tras el primer conjunto en la posición de la memoria. Como consecuencia, el procesamiento se vuelve más rápido.
Al buscar Berta Torres, el puntero de datos se coloca así desde el principio sobre el valor 003, calculado a partir de la tabla hash, y a partir de entonces ya solo le queda examinar un conjunto encadenado de datos. De esta forma pueden agruparse y examinarse grandes cantidades de datos de forma más rápida y sofisticada.
El método conocido como caching también utiliza este principio para recuperar datos que hayan sido usados alguna vez. Estos datos se guardan en la memoria temporal o memoria caché, desde donde se recuperan en caso de coincidencia con un patrón de actividad. Esto se aplica, por ejemplo, a páginas webs que han sido visitadas, de manera que en una segunda visita ya no se tienen que cargar completamente desde el servidor, sino que se recuperan, de forma mucho más rápida, de la memoria caché. Las cookies también funcionan como una especie de identificación por comparación que indica qué lugares de la web ha visitado el usuario.
¿Qué variantes del proceso hash existen?
El proceso de hashing que hemos descrito en este artículo se denomina también hashing abierto o externo, ya que en él pueden almacenarse datos en forma de listas encadenadas dentro de un espacio infinito, al menos en teoría. Si bien las claves sí son limitadas, el encadenamiento permite procesar mayores cantidades de datos. La calificación de abierto hace referencia al direccionamiento.
En el caso del hashing cerrado, en cambio, el número de claves está limitado por la capacidad de la tabla. Si se intentan guardar más datos, se produce un llamado overflow o desbordamiento. Con cada nueva examinación, la tabla se sondea para buscar posiciones libres en las que poder ubicar los elementos desbordados.
No hay reglas claras que definan el significado de los términos abierto y cerrado para calificar los procesos de hashing. En algunas publicaciones se utilizan incluso de forma opuesta a la que describimos aquí. Es recomendable, por lo tanto, tomar como referencia una descripción detallada de cada concepto.
Por otro lado, el llamado hash del cuco o cuckoo hashing también se aplica para evitar colisiones en la tabla de la base de datos. Este método debe su nombre al comportamiento del cuco, que quita los huevos de nidos ajenos para colocar en ellos los propios. De forma similar, el hash del cuco aplica dos funciones hash para definir dos posiciones de almacenamiento. Si la primera posición ya está ocupada, la clave allí ubicada será trasladada a otra posición, de forma que la segunda clave generada pueda colocarse en la primera posición. El inconveniente de esta variante es que puede generar un bucle inacabable de búsqueda, de forma que una rutina iniciada se interrumpiría porque superaría el tiempo asignado.
En lo que respecta al sondeo de la base de datos, existen diferentes métodos construidos a base de complejas fórmulas matemáticas y que se ocultan en forma de código de programa en una página web, por ejemplo, tras la barra de búsqueda con el icono de la lupa.
Por lo general, las bases de datos se vuelven cada vez más complejas; la cantidad de datos que comprenden aumenta cada vez más rápido. Por este motivo, el hashing dinámico aumenta la tabla hash para evitar colisiones. Esto, sin embargo, hace que se modifiquen también los valores hash de los datos ya almacenados. Para solucionar este problema de forma eficiente, se han desarrollado funciones hash especiales. Con ello, la capacidad de almacenamiento de datos pasa a ser, al menos en teoría, ilimitada, si bien los ciclos de búsqueda se vuelven menos eficientes.
Ventajas e inconvenientes de las tablas hash
La mayor ventaja que ofrece el uso de una tabla hash es la velocidad de búsqueda en grandes conjuntos de datos. Para lograrlo, sin embargo, los arquitectos de la base de datos se enfrentan al desafío de estimar por adelantado el tamaño necesario, con el fin de reducir el riesgo de colisiones. Pueden usarse muchos tipos de datos diferentes, siempre y cuando puedan calcularse valores hash a partir de ellos.
En cuanto a los puntos débiles de este método, uno de ellos es la posible degeneración grave del sistema si se producen muchas colisiones. La probabilidad de las colisiones aumenta a medida que lo hace la cantidad de datos almacenados. La presencia de una gran cantidad de funciones hash impide movimientos de un conjunto de datos al anterior o al siguiente.