La mejor manera de eliminar una entrada de una tabla hash

Question

¿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?

Answer 1

Una técnica sencilla es:

1. Encontrar y eliminar el elemento deseado
2. Ir a la siguiente cubeta
3. Si el cubo está vacío, dejar de fumar
4. Si el cubo está llena, elimine el elemento en ese cubo y volver 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.
5. Repita el paso 2.

Esta técnica mantiene su mesa ordenada a expensas de deleciones ligeramente más lento.

Answer 2

La implementación de la tabla hash de Python (muy discutible) utiliza 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.

Answer 3

Las mejores soluciones generales que se me ocurren son:

• Si eres puede utilizar un iterador no constante (al estilo de C++ STL o Java), que debe ser capaz de eliminarlos medida que las 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.
• Empuje las teclas de los elementos que se eliminarán en una lista vectorial o de matriz al atravesar 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 los que está dejando allí, puede ser mejor crear una nueva tabla hash y, a medida que atraviesa la original, agregue al nuevo hash tabla solo los artículos 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 recopilació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.

Answer 4

Depende de la forma de manejar el desbordamiento y si (1) el elemento que se está eliminado se encuentra en una ranura de desbordamiento o no, y (2) si hay elementos de desbordamiento más allá del elemento que se está eliminado, si tienen el hash la clave del elemento que se está eliminando 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 sondeos lineales, 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 le da un buen refinamiento como Algorithm R6.4 [pp. 533-534] que en su lugar marca la celda como vacía en lugar de eliminada, y luego encuentra formas 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 ranura ocupadas existentes existentes y no es una buena idea si los punteros a las ranuras se mantienen fuera de la tabla de almohadilla. [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.]

Answer 5

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.

Answer 6

¿Qué hay de la mejora de 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 está almacenado 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 de enlaces.