¿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 tratan 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 sería el caso normalmente. 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 almacenarse, 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 lo que se usa 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 llamallave. 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. Existen varios tipos de funciones hash, algunas diseñadas para operar en claves que son enteros y otras diseñadas para funcionar en claves que son cadenas. En el caso de una clave entera, un método popular es dividir el valor 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.

Al tratar con una gran cantidad de pares de valor clave 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 valor. Hay varias soluciones a la colisión, principalmente porque tiene una alta probabilidad de suceder en la mayoría de las aplicaciones prácticas.

Una solución a la colisión es que cada índice de valor sea realmente una lista vinculada para que, cuando más de una clave se resuelva a esa ubicación de índice, la ubicación puede contener más de un valor. Esto se llama encadenamiento y es una forma simple de manejar una colisión, aunque también puede ralentizar el tiempo que lleva recuperar la información. Otro método para tratar con 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 valor 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 requerida para buscar un valor.