¿Qué es una matriz asociativa?

Una matriz asociativa, también llamada tabla hash o mapa hash, es similar a una matriz estándar, excepto que el índice de la matriz puede ser una cadena en lugar de un entero. En muchas aplicaciones de bases de datos y en otros programas que manejan grandes cantidades de datos, una matriz asociativa es un elemento vital para ayudar a clasificar y acceder a la información de manera eficiente. En el núcleo de una matriz asociativa hay una matriz estándar que está indexada con enteros, como normalmente sería el caso. Un algoritmo especial llamado función hash convierte el índice de cadena en un índice entero para encontrar el valor. Esta es una conversión consistente, por lo que el índice entero real nunca necesita ser almacenado, sino que se calcula a partir de la cadena según sea necesario cada vez.

La terminología utilizada al referirse a una matriz asociativa puede ser ligeramente diferente de la utilizada cuando se habla de una matriz normal. Lo que normalmente se llamaría un índice, la ubicación numérica de un elemento dentro de una matriz, se llama clave. Los datos asociados con la clave se denominan valor. Esto significa que, dentro de una matriz asociativa, una clave está asociada con un valor, que se correlaciona con un índice que hace referencia a un elemento en una matriz estándar en la estructura de datos.

En el corazón de cada matriz asociativa está la función hash. Este es un algoritmo utilizado para determinar el índice numérico de un valor basado en la clave. Hay varios tipos de funciones hash, algunas diseñadas para operar en teclas que son enteras y otras diseñadas para trabajar en teclas que son cadenas. En el caso de una clave entera, un método popular es dividir el valor de la clave por el tamaño de la matriz y usar el resto de la división para, con suerte, obtener un valor de índice único.

La función hash puede ser mucho más compleja para las teclas que son cadenas. Algunos métodos incluyen agregar el valor numérico de cada carácter en la cadena y luego dividirlo por algún número, o usar solo los primeros caracteres de la cadena para obtener un número único. Hay muchas formas de derivar un número de una cadena de caracteres.

Cuando se trata con una gran cantidad de pares clave-valor en una matriz asociativa, un problema que puede surgir se llama colisión. La colisión ocurre cuando el índice entero derivado de una clave es idéntico al índice entero de otra clave. Estas dos claves apuntan efectivamente al mismo índice en la matriz de valores. Existen varias soluciones para la colisión, principalmente porque tiene una alta probabilidad de ocurrir en la mayoría de las aplicaciones prácticas.

Una solución a la colisión es hacer que cada índice de valor sea en realidad una lista vinculada para que, cuando más de una clave se resuelva en esa ubicación de índice, la ubicación pueda contener más de un valor. Esto se llama encadenamiento y es una forma sencilla de manejar una colisión, aunque también puede ralentizar el tiempo que lleva recuperar la información. Otro método para tratar una colisión se llama sondeo lineal. Cuando se produce una colisión, el sondeo lineal funciona moviéndose a través de la matriz de valores hasta que se encuentra un índice no utilizado. Esta solución puede ayudar a mantener los datos distribuidos uniformemente en la matriz asociativa, pero también puede aumentar la cantidad de tiempo necesaria para buscar un valor.