He implementado mis propias funciones de tablas hash en C, pero actualmente no admite el cambio de tamaño. Me preguntaba qué algoritmos existen, aparte de la fuerza bruta de crear una nueva tabla hash vacía y mover todo allí.¿Qué algoritmos están disponibles para cambiar el tamaño de una tabla hash?
Hay un cambio de tamaño incremental.
De Wikipedia:
incremental cambiar el tamaño
Algunas implementaciones de la tabla de hash, sobre todo en sistemas de tiempo real, puede no pagar el precio de la ampliación de la tabla hash todos a la vez, porque puede interrumpe las operaciones de tiempo crítico. Si uno no puede evitar el cambio de tamaño dinámico, una solución es llevar a cabo el cambio de tamaño gradualmente :
Durante el cambio de tamaño, asignar la nueva tabla de hash , pero mantener la mesa de edad sin cambios. En cada operación de búsqueda o eliminación, compruebe ambas tablas. Realice las operaciones de inserción solo en la nueva tabla. En cada inserción, mueva también r elementos de la tabla anterior a la nueva tabla . Cuando todos los elementos se eliminan de la tabla anterior, desasíguelo.
Para garantizar que la mesa de edad será completamente copiado antes de la nueva tabla en sí necesita ser ampliada, que es necesario aumentar el tamaño de la mesa por un factor de al menos (r + 1)/r durante el cambio de tamaño.
Así que esta no es una forma inteligente de mover todos los elementos de la vieja tabla a la nueva (y si hay uno, no lo he visto); más bien, alivia la carga de redimensionamiento al permitir que la migración ocurra gradualmente.
Wikipedia tiene algunos words of wisdom sobre el tema.
Además, no es una solución, pero podría ser parte de una: si está en Windows, puede usar la familia de funciones VirtualAlloc que le permiten reservar espacio de direcciones sin comprometer las páginas de memoria. Es decir, en términos simples, harías algo así como un "malloc" y le dirías que "reserve 1000MB, pero solo haz que los primeros 10 estén disponibles". Entonces, si escribes más allá de los 10MB, obtendrás el colapso habitual. Pero cuando llega el momento de expandirse, solo dices "OK, dame otros 10MB después de los primeros". Y los siguientes 10MB están disponibles en la dirección directamente después de los primeros 10MB. Es como cambiar el tamaño de una matriz. La RAM real en uso será solo la cantidad que necesite, pero las direcciones de memoria se reservarán por adelantado para que otras operaciones de asignación de memoria no las utilicen.
El colapso habitual es dejar que el código del cliente adivine el mejor número de cubos en el frente. Eso es útil, el cliente generalmente tiene una suposición razonable sobre cuántos elementos terminarán en la mesa. Si desea hacerlo automáticamente, primero debe declarar una matriz de primos para los tamaños de cubo. Cuando vea que el factor de carga de una cubeta aumenta demasiado, elija la siguiente flor en la matriz, recree la lista de cubos y mueva los elementos de los cubos antiguos a la nueva tabla.
Esa es una forma bastante inteligente de cambiar el tamaño de una matriz; si tiene espacio de direcciones para grabar (x64), pero no funcionará para las tablas hash, igual tendría que volver a configurar todo (y es más complejo hacerlo en lugar.) – Eloff
@Eloff - Bueno, como dije, no es una solución en sí, solo una parte de uno. Y no tiene que reservar ese espacio de direcciones mucho más. Solo una cantidad razonable. No es una bala de plata, solo hace que la operación de cambio de tamaño sea más rápida. –
Veo hacia dónde te diriges con esto ahora, pero es dudoso que realmente haga que el cambio de tamaño sea más rápido. El mayor gasto aquí no es la asignación de memoria, que apenas cuenta. Todo el tiempo entra en fallas de páginas blandas para traer la nueva memoria al espacio de direcciones de proceso (generalmente ocurre en el asignador de memoria cuando pone a cero la memoria) y en el costo requerido para volver a hash y reinsertar todos los elementos en la tabla hash. . Pero para las matrices dinámicas, no es necesario copiar nada, y puede pagar las fallas de página suave de a una por vez (crecer una página a la vez) ¡ahora eso es excelente! – Eloff