Función hash
Una función hash es cualquier función que se pueda utilizar para asignar datos de tamaño arbitrario a valores de tamaño fijo. Los valores devueltos por una función hash se llaman valores hash , códigos hash , digiere , o simplemente hash . Los valores se utilizan generalmente para indexar una tabla de tamaño fijo llamada tabla hash . El uso de una función hash para indexar una tabla hash se denomina hash o direccionamiento de almacenamiento disperso .
Las funciones hash y sus tablas hash asociadas se utilizan en aplicaciones de almacenamiento y recuperación de datos para acceder a los datos en un tiempo pequeño y casi constante por recuperación. Requieren una cantidad de espacio de almacenamiento solo una fracción mayor que el espacio total requerido para los datos o registros en sí. Hashing es una forma de acceso a datos que ahorra espacio desde el punto de vista computacional y de almacenamiento que evita el tiempo de acceso no lineal de listas ordenadas y no ordenadas y árboles estructurados, y los requisitos de almacenamiento a menudo exponenciales de acceso directo de espacios de estado de claves grandes o de longitud variable.
El uso de funciones hash se basa en las propiedades estadísticas de la interacción de teclas y funciones: el comportamiento en el peor de los casos es intolerablemente malo con una probabilidad muy pequeña, y el comportamiento del caso promedio puede ser casi óptimo ( colisión mínima ). [1]
Las funciones hash están relacionadas con (y a menudo se confunden con) sumas de verificación , dígitos de verificación , huellas dactilares , compresión con pérdida , funciones de aleatorización , códigos de corrección de errores y cifrados . Aunque los conceptos se superponen en cierta medida, cada uno tiene sus propios usos y requisitos y está diseñado y optimizado de manera diferente. Las funciones hash se diferencian de los conceptos enumerados principalmente en términos de integridad de los datos.
Una función hash toma una entrada como clave, que se asocia con un dato o registro y se usa para identificarlo en la aplicación de almacenamiento y recuperación de datos. Las claves pueden tener una longitud fija, como un número entero, o una longitud variable, como un nombre. En algunos casos, la clave es el propio dato. La salida es un código hash que se utiliza para indexar una tabla hash que contiene los datos o registros, o punteros a ellos.
Una buena función hash satisface dos propiedades básicas: 1) debe ser muy rápida de calcular; 2) debe minimizar la duplicación de valores de salida (colisiones). Las funciones hash se basan en generar distribuciones de probabilidad favorables para su efectividad, lo que reduce el tiempo de acceso a casi constante. Los factores de carga de la tabla altos, los conjuntos de claves patológicos y las funciones hash mal diseñadas pueden hacer que los tiempos de acceso se acerquen a los lineales en el número de elementos de la tabla. Las funciones hash pueden diseñarse para ofrecer el mejor rendimiento en el peor de los casos, [Notas 1]buen rendimiento con factores de carga de tabla elevados y, en casos especiales, mapeo perfecto (sin colisiones) de claves en códigos hash. La implementación se basa en operaciones de bits que preservan la paridad (XOR y ADD), multiplicar o dividir. Un complemento necesario de la función hash es un método de resolución de colisiones que emplea una estructura de datos auxiliares como listas enlazadas , o un sondeo sistemático de la tabla para encontrar un espacio vacío.
