Cuántas cubetas hash

Question

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

Digamos que tengo 100 cubos. ¿Debería reorganizarlo cuando hay 50 elementos en él? 500? 5000? ¿O debería buscar el cubo y la llave más completos sobre eso? Luego, cuando llegué a ese punto, ¿qué tan grande hago la nueva tabla hash?

En relación con esto, si sabe de antemano aproximadamente cuántos elementos entrarán, ¿hay alguna manera de calcular el número de segmentos 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 guildlines generales.

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

Answer 1

Una buena regla de oro (no siempre ideal, bueno, solo una regla del pulgar) es volver a hash si la tabla hash se llena hasta el 80%. Eso significa que si tiene 100 cubos y 80 elementos en el interior, independientemente de la cantidad de colisiones que haya tenido antes, se está ganando tiempo para aumentar la capacidad.

¿Cuánto debería aumentar? 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 sea muy grande y nunca llenes los 16 MB), elige un factor de crecimiento más pequeño. Se recomienda al menos 1/3 (creciendo de 100 a 133) Yo diría, tal vez dejar que crezca en un 50% cada vez como un compromiso.

Tenga en cuenta que todo esto también depende de cómo se manejan las colisiones. Una forma 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 tecla, todavía hay solo 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ápida. OTOH, puedes hacer algo más sofisticado y mantener estadísticas sobre el número de colisiones. Siempre y cuando apenas tengas colisiones (si tienes una función hash muy buena), no hay necesidad de volver a hash en absoluto, incluso si el 99% de su capacidad está en uso. También si manejas colisiones de una manera sofisticada (p.cada nodo es nuevamente una tabla ordenada y puede realizar una búsqueda binaria dentro de estos) su búsqueda aún puede ser lo suficientemente rápida si la tabla se carga al 200% (por lo que tiene el doble de elementos que la capacidad). En ese caso, podría mantener estadísticas de la magnitud de la tabla clasificada más grande y, cuando sea mayor que, digamos, 8 entradas, cree que esto es demasiado lento y luego volver a hash.

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

Answer 2

Generalmente, mirar hacia fuera para el factor de carga (informalmente, que ya se ha dicho que) que se define formalmente como α   =   n  /  N, es decir, la relación de utilizado para cubos totales. Para que una tabla hash para que funcione correctamente (o al menos a la razón sobre sus prestaciones en términos matemáticos), debe ser α   <   1.

Todo lo demás es realmente depende de pruebas empíricas: Si usted ve que su la tabla hash no funciona bien comenzando en α  >   0.5, luego asegúrese de mantenerse por debajo de ese valor. Este valor también depende de su técnica de resolución de colisión. Hashing con encadenamiento puede requerir otros factores de carga que hashing con direccionamiento abierto. Otro factor más es la localidad de caché. Si su mesa 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

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 de cubos), debe cambiar el tamaño de la matriz cuando la tabla esté llena o cuando haya alcanzado un conteo máximo de sonda (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 sondear espacios vacíos, por lo que cambiar el tamaño no es tan importante.

La clave con tablas hash es el algoritmo hash, no el número de cubetas. Lo ideal es que siempre desee como máximo un elemento en cada depósito, por lo que idealmente debería cambiar el tamaño cuando la cantidad de elementos en la tabla hash sea igual a la cantidad de depósitos. Si sus datos no están distribuidos uniformemente, es mejor con un mejor algoritmo hash que una mejor estrategia de cambio de tamaño.

Answer 4

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

En una tabla hash abierta, encuentra el cubo correcto basado en el hash y luego crea una lista de elementos que cuelgan de ese cubo.

En una tabla hash cerrada, se encuentra la cubeta inicial utilizando el valor hash, y si está ocupada, se busca el siguiente valor. En el caso simplista, puede hacer esto buscando el siguiente cubo libre, o puede crear un segundo valor hash de su elemento y paso por eso (aunque debe asegurarse de que este sea el módulo principal del tamaño de tablas hash, por lo que visitará todos los cubos).

Normalmente, una tabla hash abierta no cambia de tamaño. Establece el tamaño inicial para que sea lo que cree que es razonable para el problema. Como han señalado otros, podría cambiar el tamaño de una tabla hash abierta, pero el razonamiento sobre el rendimiento de esta estructura de datos ahora se vuelve muy difícil. Si cambias el tamaño cuando la longitud de un cubo dado es L, entonces podría cambiar el tamaño de solo L elementos en toda la tabla hash, lo cual es muy ineficiente.

Una tabla hash cerrada se cambia de tamaño cuando el factor de carga (número de elementos en la tabla hash/no de cubos) alcanza un 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 amortizado el costo de insertar un artículo es siempre O (1) (asumiendo una buena función hash). La inserción de un artículo en particular podría ser O (N) debido al costo de cambio de tamaño, pero eso se hace con poca frecuencia.

Answer 5

Si usa el algoritmo hashing lineal, la tabla se ocupa automáticamente del redimensionamiento, manteniendo un factor de carga constante.