Una tabla (hash) o de dispersiones es
una estructura de datos que asocia llaves o claves con valores.
Las tablas de dispersión o hashing
tables (en inglés) es una técnica que se utiliza para implementar inserciones,
eliminaciones y búsquedas en un tiempo medio constante.
La operación principal que soporta de
manera eficiente es la búsqueda: permite el acceso a los elementos (teléfono y
dirección, por ejemplo) almacenados a partir de una clave generada (usando el
nombre o número de cuenta, por ejemplo). Funciona transformando la clave con
una función hashen un hash, un número que la tabla hash utiliza para localizar
el valor deseado.
Las tablas hash se suelen implementar
sobre vectores de una dimensión, aunque se pueden hacer implementaciones
multi-dimensionales basadas en varias claves. Como en el caso de los arrays,
las tablas hash proveen tiempo constante de búsqueda promedio O(1),1 sin
importar el número de elementos en la tabla. Sin embargo, en casos
particularmente malos el tiempo de búsqueda puede llegar a O(n), es decir, en
función del número de elementos.
Comparada con otras estructuras de
arrays asociadas, las tablas hash son más útiles cuando se almacenan grandes
cantidades de información.
Las tablas hash almacenan la
información en posiciones pseudo-aleatorias, así que el acceso ordenado a su
contenido es bastante lento. Otras estructuras como árboles binarios
auto-balanceables son más rápidos en promedio (tiempo de búsqueda O(log n))
pero la información está ordenada en todo momento.
Una estructura hash se construye con
tres elementos básicos :
• Un
vector direccionable mediante número de posición capaz de almacenar N
elementos.
• Una
función de dispersión que nos permita a partir de la clave obtener el índice
donde estará el dato asociado a esa clave.
• Una
función de resolución de colisiones.
BIBLIOGRAFIA
Bien; 2.
ReplyDelete