Las tablas hash dinámicas perfectas y las tablas hash cuco son dos estructuras de datos diferentes que admiten las búsquedas de O (1) en el peor de los casos y las inserciones y eliminaciones esperadas de O (1). Ambos requieren espacio auxiliar O (n) y acceso a familias de funciones hash para sus operaciones.
Creo que ambas estructuras de datos son hermosas y brillantes por derecho propio, pero no estoy seguro de ver cómo y cuándo una de estas sería preferible a la otra.
¿Existen contextos específicos en los que una de estas estructuras de datos tiene una clara ventaja sobre la otra? ¿O son mayormente intercambiables?
data-structures
hash-tables
templatetypedef
fuente
fuente
Respuestas:
El hashing dinámico perfecto en el sentido de Dietzfelbinger et al. solo necesita 2 hash independientes . Si bien hay algunos resultados sobre el hashing simple para tablas de hash de cuco, como el hashing de tabulación retorcido y "Bastante explícito y eficiente de familias de hash para hash de cuco con un alijo", el hashing perfecto dinámico original es más robusto en cierto sentido.
fuente
En el hash de cuco, las búsquedas se pueden realizar en paralelo, mientras que en el esquema de hash perfecto dinámico original de Dietzfelbinger et al., Las búsquedas requieren dos accesos de memoria encadenados, en los que el segundo acceso usa información recuperada del primero.
fuente
Es relativamente fácil aumentar la eficiencia de espacio del hash cuckoo al permitir que cada ranura contenga más de un elemento. Para ranuras de tamaño 4, la eficiencia del espacio es algo así como 95%. Es decir, los elementos se pueden insertar hasta que el 95% del espacio en la tabla se utiliza para contener elementos, no solo los lugares donde los elementos pueden ir.
Por otro lado, los límites en Dietzfelbinger et al. el documento sobre hashing dinámico perfecto solo prueba que las operaciones de inserción pueden continuar siempre que la tabla no esté llena más del 3%.
fuente
fuente