Hashing de 2 opciones

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]${\displaystyle O(2+(m-1)/n)}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \log _{2}\ln n+\theta (m/n)}$

El hash de 2 opciones utiliza dos funciones hash h ₁ ( x ) y h ₂ ( 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 ₁ ( x ) y h ₂ ( 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.

• Inserción: al insertar, se calculan los valores de ambas funciones hash para el objeto que se va a insertar. Luego, el objeto se coloca en el contenedor que contiene menos objetos. Si los contenedores tienen el mismo tamaño, la ubicación predeterminada es el valor h ₁ ( x ).
• Búsqueda: Las búsquedas efectivas se realizan buscando en ambos depósitos (las ubicaciones de los depósitos a los que se asignan h ₁ ( x ) y h ₂ ( x )) el valor deseado.

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 ]}

 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 .

• Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Upfal, Eli (23–25 de mayo de 1994), "Asignaciones equilibradas (resumen ampliado)" (PDF) , Actas del vigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '94 , Montreal: Association for Computing Machinery, págs. 593–602, CiteSeerX  10.1.1.38.5375 , doi :10.1145/195058.195412, ISBN 0897916638, S2CID1014349 ​
• Azar, Yossi; Broder, Andrei Z.; Karlin, Anna R.; Upfal, Eli (1999), "Asignaciones equilibradas" (PDF) , SIAM J. Comput. , 29 (1): 180–200, doi :10.1137/S0097539795288490