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 utiliza sondeo lineal? ¿Una forma de hacer esto sería usar una bandera para indicar elementos eliminados? ¿Hay alguna forma mejor que esto?

Answer 1

Una técnica fácil es:

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

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

Answer 2

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 de desbordamiento más allá del elemento que se está eliminando, si tienen la clave hash del elemento eliminado o posiblemente alguna otra clave 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. O está desplegando la lista (que puede haber quedado vacía) o eliminando un miembro del medio o final de la lista vinculada. Esos son divertidos y no particularmente difíciles. Puede haber otras optimizaciones para evitar asignaciones excesivas de memoria y liberaciones para hacerlo aún más eficiente.

Para el sondeo lineal, Knuth sugiere que un enfoque simple es tener una manera de marcar un espacio como vacío, eliminado u ocupado. Marque una ranura de ocupante eliminada como eliminada para que el desbordamiento mediante sondeo lineal pase por alto, pero si se necesita una inserción, puede llenar la primera ranura eliminada que pasó sobre [El arte de la programación de computadoras, vol.3: Ordenar y buscar , sección 6.4 Hashing, pág. 533 (ed. 2)]. Esto supone que las eliminaciones son bastante raras.

Knuth da un refinamiento agradable como Algoritmo R6.4 [pp. 533-534] que en su lugar marca la celda como vacía en lugar de eliminarla, y luego encuentra formas de mover las entradas de la tabla más cerca de su ubicación de sonda inicial moviendo el agujero que se acaba de hacer hasta que termina al lado de otro agujero.

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

Answer 3

La implementación de la tabla hash de Python (discutible muy rápido) utiliza elementos ficticios para marcar eliminaciones. A medida que creces, te encoges o te pones en la mesa (suponiendo que no estés haciendo una mesa de tamaño fijo), puedes soltar los muñecos al mismo tiempo.

Si tiene acceso a una copia, consulte el artículo en Beautiful Code sobre la implementación.

Answer 4

Las mejores soluciones generales que se me ocurren incluyen:

• Si puede usar un iterador no constante (ala C ++ STL o Java), debería poder eliminarlos cuando los encuentre. Sin embargo, presumiblemente, no haría esta pregunta a menos que esté utilizando un iterador constante o un enumerador que se invalidaría si se modifica la colección subyacente.
• Como dijiste, podrías marcar una bandera eliminada dentro del objeto contenido. Sin embargo, esto no libera memoria ni reduce las colisiones en la tecla, 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 realmente allí. Si esto te molesta tanto como a mí, o si simplemente no puedes agregar una bandera al objeto almacenado (tal vez no controlas la clase), puedes almacenar estas banderas en una tabla hash separada. Esto requiere el uso de memoria a largo plazo.
• Presione las teclas de los elementos que se eliminarán en una lista de vectores o matrices mientras recorre la tabla hash. Después de liberar el enumerador, recorra esta lista secundaria y elimine las claves de la tabla hash. Si tiene que eliminar muchos elementos y / o las claves 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 coloque solo los artículos que va a conservar. Luego reemplace su referencia (s) a la antigua tabla hash con la nueva. Esto ahorra una iteración de lista secundaria, pero probablemente solo sea eficiente si la nueva tabla hash tendrá significativamente menos elementos que la original, y definitivamente solo funciona si puede 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 iterar a través de ellas 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 Remove () a la que puede pasar una expresión lambda o un puntero de función para identificar los elementos a eliminar.

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. De uso general en motores de búsqueda.

Answer 6

¿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 depósito al depósito 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 vinculada.