El hash de 2 opciones , también conocido como encadenamiento de 2 opciones , es "una variante de una tabla hash en la que las claves se añaden mediante hash con dos funciones hash . La clave se coloca en la posición de la matriz con menos claves (en colisión). Se necesita algún esquema de resolución de colisiones , a menos que las claves se mantengan en contenedores. El coste medio de una búsqueda exitosa es , donde es la cantidad de claves y es el tamaño de la matriz. La mayor cantidad de colisiones es con alta probabilidad". [1]
El hash de 2 opciones utiliza dos funciones hash h 1 ( x ) y h 2 ( x ) que funcionan como se espera que funcionen las funciones hash (es decir, asignando números enteros del universo a un rango específico). Las dos funciones hash deben ser independientes y no tener correlación entre sí. Tener dos funciones hash permite que cualquier clave x tenga hasta dos ubicaciones potenciales para almacenarse en función de los valores de las salidas respectivas, h 1 ( x ) y h 2 ( x ). Es importante tener en cuenta que, aunque hay dos funciones hash, solo hay una tabla; ambas funciones hash se asignan a ubicaciones en esa tabla.
Las funciones más importantes de la implementación de hashing en este caso son la inserción y la búsqueda.
Como sucede con todas las tablas hash, el rendimiento se basa en el contenedor más grande. Aunque hay casos en los que los tamaños de los contenedores son grandes en función de los valores y las funciones hash utilizadas, esto es poco frecuente. Tener dos funciones hash y, por lo tanto, dos posibles ubicaciones para cualquier valor, hace que la posibilidad de contenedores grandes sea aún más improbable.
El tamaño de depósito esperado al utilizar el algoritmo hash de 2 opciones es: θ (log(log( n ))) . Esta mejora se debe al concepto aleatorio conocido como El poder de dos opciones.
El uso de dos funciones hash ofrece ventajas sustanciales en comparación con una sola función hash. Hay pocas mejoras (y ningún cambio en las estadísticas de orden esperadas) si se utilizan más de dos funciones hash: "Las funciones hash adicionales solo reducen el máximo en un factor constante". [2]
Algunas personas recomiendan un tipo de hash de 2 opciones llamado caché asociativo sesgado bidireccional en algunos cachés de CPU . [3]
El hash de 2 izquierdas (que utiliza dos tablas hash de igual tamaño n /2 y resuelve los empates de forma asimétrica colocando la clave en la tabla hash de la izquierda) tiene menos colisiones y, por lo tanto, un mejor rendimiento que el hash de 2 opciones con una tabla hash grande de tamaño n . [4] [ cita completa necesaria ]
2008. (consultado el 28 de julio de 2016).19 de diciembre de 2012. (consultado el 15 de septiembre de 2015). Este artículo incorpora material de dominio público de Paul E. Black. "Hash de 2 opciones". Diccionario de algoritmos y estructuras de datos . NIST .
