En informática , la eliminación diferida se refiere a un método para eliminar elementos de una tabla hash que utiliza direccionamiento abierto . En este método, las eliminaciones se realizan marcando un elemento como eliminado, en lugar de borrarlo por completo. Las ubicaciones eliminadas se tratan como vacías al insertarlas y como ocupadas durante una búsqueda.
El problema con este esquema es que a medida que aumenta el número de operaciones de eliminación / inserción, aumenta el costo de una búsqueda exitosa. Para mejorar esto, cuando se busca un elemento y se encuentra en la tabla, el elemento se reubica en la primera ubicación marcada para su eliminación que se probó durante la búsqueda. En lugar de encontrar un elemento para reubicar cuando se produce la eliminación, la reubicación se produce de forma perezosa durante la siguiente búsqueda. [1] [2]
Referencias
- ^ Celis, Pedro ; Franco, John (1995), The Analysis of Hashing with Lazy Deletions , Departamento de Ciencias de la Computación, Universidad de Indiana, CiteSeerX 10.1.1.39.9637 , Informe técnico CS-86-14
- ^ Celis, Pedro; Franco, John (1992), "The analysis of hashing with lazy deletions", Information Sciences , 62 (1-2): 13-26, CiteSeerX 10.1.1.39.9637 , doi : 10.1016 / 0020-0255 (92) 90022- Z