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 número 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 números enteros, como sería el caso normalmente. Un algoritmo especial llamado función hash convierte el índice de la 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 cuando se hace referencia a una matriz asociativa puede ser ligeramente diferente a la que se utiliza cuando se habla de una matriz normal. Lo que normalmente se llamaría í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 con claves que son números enteros y otras diseñadas para funcionar con claves 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 claves 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 a partir de una cadena de caracteres.
Cuando se trata de 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 entonces apuntan efectivamente al mismo índice en la matriz de valores. Existen varias soluciones para la colisión, principalmente porque tiene una alta probabilidad de que ocurra 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 de modo 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 hacer frente a una colisión se llama sondeo lineal. Cuando ocurre 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 necesario para buscar un valor.