Cuantos cubos hash

Question

Si noto que una tabla hash (o cualquier otra estructura de datos construida sobre una tabla hash) se está llenando, en qué punto debe construir una nueva tabla con más depósitos. Y dado n elementos en la tabla hasta ahora, ¿cómo calcula cuántos cubos usar en el nuevo?

Entonces digamos que tengo 100 cubos. ¿Debo reorganizarlo cuando hay 50 elementos en él? 500? 5000? ¿O debería buscar el cubo más lleno y la clave en eso? Entonces, cuando llego a ese punto, ¿qué tan grande hago la nueva tabla hash?

Relacionado con esto, si sabe de antemano aproximadamente cuántos elementos entrarán, ¿hay alguna manera de calcular la cantidad de cubos para obtener un buen rendimiento promedio?

Sé que la respuesta real depende de muchas otras consideraciones, como la importancia de la velocidad frente al tamaño en un ejemplo específico, pero estoy buscando líneas generales de gremio.

También sé que no debería optimizar este tipo de cosas a menos que un buen perfil haya indicado que se trata de un cuello de botella. Solo estoy pensando en un proyecto que usaría muchas tablas hash y me preguntaba cómo abordar esto.

Answer 1

Una buena regla general (no siempre es ideal, bueno, solo una regla general) es volver a hacer hash si la tabla hash se llena hasta un 80%. Eso significa que si tiene 100 cubos y 80 artículos dentro, independientemente de la colisión que haya tenido antes, tendrá tiempo para aumentar la capacidad.

¿Cuánto debería aumentarlo? Bueno, tampoco hay un valor perfecto. La solución más simple es duplicar la capacidad en cada aumento. Entonces va a 200, 400, 800, y así sucesivamente. Si crees que esto es demasiado (después de todo, saltará de 8 MB de memoria a 16 MB cuando la tabla hash se vuelva muy grande y nunca puedas llenar los 16 MB), elige un factor de crecimiento más pequeño. Se recomienda al menos 1/3 (aumentarlo de 100 a 133). Diría que tal vez permita que crezca un 50% cada vez como compromiso.

Tenga en cuenta que todo esto también depende de cómo se manejen las colisiones. Una manera simple de manejarlos (mi favorito personal) es almacenar los artículos en una lista vinculada cuando hay una colisión. Si se colocan 3 elementos en la misma clave, solo hay hasta 3 comparaciones para encontrarlo. Dado que la lista vinculada es muy ineficaz para la búsqueda, es posible que desee aumentar la capacidad antes, p. si se usa un 60% de capacidad para mantener la tabla hash rápidamente. OTOH, puedes hacer algo más sofisticado y mantener estadísticas sobre el número de colisiones. Mientras apenas tenga colisiones (si tiene una función hash muy buena) no hay necesidad de volver a hacer hash, incluso si el 99% de su capacidad está en uso. Además, si maneja las colisiones de una manera sofisticada (por ejemplo, cada nodo es nuevamente una tabla ordenada y puede realizar una búsqueda binaria dentro de ellas), su búsqueda podría ser lo suficientemente rápida si la tabla se carga al 200% (por lo que tiene el doble de elementos como capacidad). En ese caso, podría mantener estadísticas de cuán grande es la tabla ordenada más grande y cuando se hace más grande que, digamos, 8 entradas, cree que esto se está volviendo demasiado lento y luego vuelve a hacer hash.

El nuevo hash es muy lento, por lo que debe evitarse con la mayor frecuencia posible. Por lo tanto, si necesita volver a hacer hash, no solo aumente la capacidad demasiado poco, de lo contrario, tendrá que volver a hacer hash nuevamente muy pronto al agregar más elementos. Entonces, cuando necesite volver a hacer hash, haga que la capacidad sea significativamente mayor que la cantidad de elementos actualmente en la tabla, todo lo demás es muy poca capacidad.

Answer 2

Generalmente, busca el factor de carga (informalmente, ya lo dijo) que se define formalmente como & # 945; & nbsp; = & nbsp; n & nbsp; / & nbsp; N , es decir, la relación entre los depósitos utilizados y los totales. Para que una tabla hash funcione correctamente (o al menos para razonar sobre su rendimiento en términos matemáticos), debe ser & # 945; & Nbsp; & Lt; & Nbsp; 1.

Todo lo demás depende realmente de las pruebas empíricas: si ve que su tabla hash no funciona bien a partir de & # 945; & nbsp; > & nbsp; 0.5, entonces asegúrese de mantenerse por debajo de ese valor. Este valor también depende de su técnica de resolución de colisión. El hashing con encadenamiento puede requerir otros factores de carga que el hashing con direccionamiento abierto. Otro factor más es la localidad de caché. Si su tabla se vuelve demasiado grande, no cabe en la memoria principal. Dado que su acceso a la matriz es aleatorio, la carga desde la memoria caché puede convertirse en un cuello de botella.

Answer 3

Normalmente hay dos tipos de tablas hash: abiertas y cerradas.

En una tabla hash abierta, encuentra el depósito correcto según el hash y luego crea una lista de elementos que cuelgan de ese depósito.

En una tabla hash cerrada, encuentra el depósito inicial utilizando el valor hash, y si está ocupado, busca el siguiente valor. En el caso simplista, puede hacer esto buscando el siguiente depósito gratuito, o puede crear un segundo valor de hash a partir de su artículo y seguirlo (aunque debe asegurarse de que este sea el módulo principal del tamaño de las tablas de hash, por lo que visitará todos los cubos).

Una tabla hash abierta normalmente no cambia de tamaño. Establece el tamaño inicial para que sea lo que considere razonable para el problema. Como otros han señalado, puede cambiar el tamaño de una tabla hash abierta, pero ahora es muy difícil razonar sobre el rendimiento de esta estructura de datos. Si cambia el tamaño cuando la longitud de un segmento dado es L, entonces podría terminar cambiando el tamaño de solo L elementos en toda la tabla hash, lo cual es muy ineficiente.

Una tabla hash cerrada cambia de tamaño cuando el factor de carga (no. de elementos en la tabla hash / no. de cubos) alcanza algún valor predefinido. Tiendo a usar el 80%, pero es poco probable que el valor exacto sea demasiado crítico.

El beneficio de una tabla hash cerrada es que el costo amortizado de insertar un artículo siempre es O (1) (asumiendo una buena función hash). Insertar un elemento en particular puede ser O (N) debido al costo de cambiar el tamaño, pero eso se hace con poca frecuencia.

Answer 4

Depende del tipo de tabla hash que esté creando. Si está utilizando una tabla hash basada en una matriz fija (a diferencia de las listas vinculadas para los cubos), debe cambiar el tamaño de la matriz cuando la tabla esté llena o cuando haya alcanzado un recuento máximo de sondas (dependiendo de si le importa más la velocidad o memoria). Si está utilizando listas vinculadas, la memoria no es tan preocupante desde entonces y no tiene que buscar espacios vacíos, por lo que cambiar el tamaño no es tan importante.

La clave con las tablas hash es el algoritmo hash, no el número de cubos. Idealmente, siempre desea a lo sumo un elemento en cada depósito, por lo que idealmente debería cambiar el tamaño cuando el número de elementos en la tabla hash = el número de depósitos. Si sus datos no se distribuyen de manera uniforme, es mejor que tenga un mejor algoritmo hash que una mejor estrategia de cambio de tamaño.

Answer 5

Si usa Hashing lineal, la tabla misma se encarga automáticamente de cambiar el tamaño, manteniendo un factor de carga constante.