data structures - tablas - La mejor forma de eliminar una entrada de una tabla hash

tablas hash estructura de datos (6)

Depende de cómo maneje el desbordamiento y si (1) el elemento que se está eliminando está en una ranura de desbordamiento o no, y (2) si hay elementos desbordados más allá del elemento que se va a eliminar, si tienen la clave hash del artículo eliminado o posiblemente alguna otra tecla hash. [Pasar por alto esa doble condición es una fuente común de errores en las implementaciones de eliminación].

Si las colisiones se desbordan en una lista vinculada, es bastante fácil. Aparecerá la lista (que puede haberse quedado vacía) o eliminará un miembro de la mitad o al final de la lista vinculada. Esos son divertidos y no particularmente difíciles. Puede haber otras optimizaciones para evitar asignaciones y liberaciones de memoria excesivas para que esto sea aún más eficiente.

Para una prueba lineal, Knuth sugiere que un enfoque simple es tener una forma de marcar una ranura como vacía, eliminada u ocupada. Marque una ranura de ocupante eliminado como eliminada para que el desbordamiento por sondeo lineal se salte, pero si se necesita una inserción, puede llenar la primera ranura eliminada que pasó por alto [El arte de la programación de computadoras, vol.3: Clasificación y búsqueda , sección 6.4 Hashing, p. 533 (ed.2)]. Esto supone que las eliminaciones son bastante raras.

Knuth da una refinación agradable como Algorithm R6.4 [pp. 533-534] que en su lugar marca la celda como vacía en lugar de eliminada, y luego encuentra maneras de mover las entradas de la tabla más cerca de su ubicación de sonda inicial moviendo el orificio que acaba de hacer hasta que termina al lado de otro orificio.

Knuth advierte que esto moverá las entradas de slots que todavía están ocupadas y no es una buena idea si los punteros a las ranuras se mantienen fuera de la tabla de hash. [Si tiene recogidas de basura u otras referencias administradas en las ranuras, está bien mover la ranura, ya que es la referencia que se usa fuera de la tabla y no importa dónde está la ranura que hace referencia el mismo objeto está en la tabla.]

¿Cuál es la mejor manera de eliminar una entrada de una tabla hash que usa sondeos lineales? ¿Una forma de hacer esto sería usar una bandera para indicar elementos eliminados? ¿Hay alguna manera mejor que esto?

La implementación de la tabla hash de Python (muy discutible) usa elementos ficticios para marcar eliminaciones. A medida que crece, se encoge o mesa (suponiendo que no esté haciendo una tabla de tamaño fijo), puede soltar los maniquíes al mismo tiempo.

Si tiene acceso a una copia, eche un vistazo al artículo en Beautiful Code sobre la implementación.

Las mejores soluciones generales que puedo pensar incluyen:

Si puede usar un iterador no const (ala C ++ STL o Java), debería poder eliminarlos a medida que los encuentre. Presumiblemente, sin embargo, no harías esta pregunta a menos que estés usando un iterador de const o un enumerador que se invalidaría si se modifica la colección subyacente.
Como dijiste, puedes marcar una bandera eliminada dentro del objeto contenido. Sin embargo, esto no libera memoria ni reduce las colisiones en la clave, por lo que no es la mejor solución. También requiere la adición de una propiedad en la clase que probablemente no pertenezca allí. Si esto te molesta tanto como a mí, o si simplemente no puedes agregar un indicador al objeto almacenado (quizás no controlas la clase), puedes almacenar estos indicadores en una tabla hash separada. Esto requiere el uso de memoria a más largo plazo.
Presione las teclas de los elementos que se eliminarán en una lista de vector o matriz mientras atraviesa la tabla hash. Después de liberar el enumerador, recorra esta lista secundaria y elimine las claves de la tabla hash. Si tiene muchos elementos para eliminar y / o las teclas son grandes (que no deberían ser), esta puede no ser la mejor solución.
Si va a terminar eliminando más elementos de la tabla hash de la que está dejando ahí, puede ser mejor crear una nueva tabla hash y, a medida que atraviesa la original, agregue a la nueva tabla hash solo el elementos que vas a mantener. Luego reemplace su (s) referencia (s) a la vieja tabla hash con la nueva. Esto ahorra una iteración de la lista secundaria, pero probablemente solo sea eficiente si la nueva tabla hash tendrá significativamente menos elementos que la original, y definitivamente solo funciona si puedes cambiar todas las referencias a la tabla hash original, por supuesto.
Si su tabla hash le da acceso a su colección de claves, puede recorrerlas y eliminar elementos de la tabla hash en una sola pasada.
Si su tabla hash o algún ayudante en su biblioteca le proporciona modificadores de colección basados en predicados, puede tener una función Eliminar () a la que puede pasar una expresión lambda o un puntero a función para identificar los elementos a eliminar.

Una técnica común cuando el tiempo es un factor es tener una segunda tabla de elementos eliminados, y limpiar la tabla principal cuando tenga tiempo. Comúnmente utilizado en los motores de búsqueda.

Una técnica fácil es:

Encuentra y elimina el elemento deseado
Ir al siguiente cubo
Si el cubo está vacío, salga
Si el depósito está lleno, elimine el elemento en ese cubo y vuelva a agregarlo a la tabla hash utilizando los medios normales. El artículo debe eliminarse antes de volver a agregarlo, ya que es probable que el artículo se pueda volver a agregar a su lugar original.
Repita el paso 2.

Esta técnica mantiene su tabla ordenada a expensas de eliminaciones ligeramente más lentas.

¿Qué hay de mejorar la tabla hash para contener punteros como una lista vinculada? Cuando inserte, si el depósito está lleno, cree un puntero desde este cubo al cubo donde se almacena el nuevo campo.

Al eliminar algo de la tabla hash, la solución será equivalente a cómo se escribe una función para eliminar un nodo de la lista enlazada.