java - implementar - Parámetros de inicialización de HashMap(carga/capacidad inicial)

recorrer hashmap java foreach

Question

¿Qué valores debería pasar para crear estructuras basadas en HashMap / HashMap eficientes para N elementos?

En una ArrayList , el número eficiente es N (N ya supone crecimiento futuro). ¿Cuáles deberían ser los parámetros para un HashMap ? ((int) (N * 0.75d), 0.75d)? ¿Más? ¿Menos? ¿Cuál es el efecto de cambiar el factor de carga?

Answer 1

En la mayoría de los casos, la inicialización de List y Map es segura para hacer la List o Map con los siguientes parámetros de tamaño.

List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));

esto sigue la regla .75 y ahorra un poco sobre la operación * 2 descrita arriba.

Answer 2

En una ArrayList, el número eficiente es N (N ya supone crecimiento futuro).

Erm, no, no, a menos que malinterprete lo que dices aquí. Cuando pasa un entero al constructor de Arraylist, creará una matriz subyacente de exactamente ese tamaño. Si resulta que necesita incluso un único elemento adicional, ArrayList tendrá que cambiar el tamaño de la matriz subyacente la próxima vez que llame a add (), haciendo que esta llamada tarde mucho más de lo normal.

Si, por otro lado, está hablando de su valor de N teniendo en cuenta el crecimiento, entonces sí, si puede garantizar que el valor nunca superará esto, entonces es apropiado llamar a dicho constructor Arraylist. Y en este caso, como lo señaló Hank, el constructor análogo para un mapa sería N y 1.0f. Esto debería funcionar razonablemente incluso si superas N (aunque si esperas que esto ocurra de manera regular, es posible que desees pasar un número mayor para el tamaño inicial).

El factor de carga, en caso de que no lo supiera, es el punto en el que el mapa tendrá su capacidad aumentada, como una fracción de la capacidad total.

Editar : Yuval probablemente tenga razón en que es una mejor idea dejar el factor de carga alrededor de 0,75 para un mapa de propósito general. Un factor de carga de 1.0 funcionaría de manera brillante si sus claves tuvieran códigos hash secuenciales (como las claves de enteros secuenciales), pero para cualquier otra cosa probablemente se toparán con cubos hash, lo que significa que las búsquedas tardan más en algunos elementos. Crear más cubos de lo estrictamente necesario reducirá esta posibilidad de colisión, lo que significa que hay más posibilidades de que los elementos estén en sus propios cubos y, por lo tanto, se puedan recuperar en el menor tiempo posible. Como dicen los doctores, esta es una compensación de tiempo vs. espacio. Si alguno de ellos es particularmente importante para usted (como lo muestra un generador de perfiles en lugar de optimizarlo prematuramente), puede enfatizar eso; de lo contrario, mantente con el valor predeterminado.

Answer 3

En cuanto al factor de carga, simplemente citaré el javadoc de HashMap :

Como regla general, el factor de carga predeterminado (.75) ofrece una buena compensación entre los costos de tiempo y espacio. Los valores más altos disminuyen la sobrecarga de espacio, pero aumentan el costo de búsqueda (que se refleja en la mayoría de las operaciones de la clase HashMap, incluidos get y put). El número esperado de entradas en el mapa y su factor de carga se deben tener en cuenta al establecer su capacidad inicial, a fin de minimizar el número de operaciones de repetición. Si la capacidad inicial es mayor que la cantidad máxima de entradas dividida por el factor de carga, nunca se producirán operaciones de repetición.

Es decir, el factor de carga no debe cambiarse de .75 , a menos que tenga una optimización específica que va a hacer. La capacidad inicial es lo único que desea cambiar y configurarlo de acuerdo con su valor N , es decir, (N / 0.75) + 1 , o algo en esa área. Esto asegurará que la tabla siempre será lo suficientemente grande y no se producirá ningún cambio de imagen.

Answer 4

También es notable que tener un HashMap en el lado pequeño hace que las colisiones hash sean más probables, lo que puede ralentizar la búsqueda. Por lo tanto, si realmente te preocupas por la velocidad del mapa, y menos por su tamaño, podría valer la pena hacerlo demasiado grande para los datos que necesita contener. Dado que la memoria es barata, normalmente inicializo HashMaps para una cantidad conocida de artículos con

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

No dude en estar en desacuerdo, de hecho me gustaría tener esta idea verificada o descartada.

Answer 5

Hacer referencia al código fuente de HashMap ayudará.

Si el número de entradas alcanza el umbral (capacidad * factor de carga), el reajuste se realiza automáticamente. Eso significa que un factor de carga demasiado pequeño puede provocar un reafilado frecuente a medida que aumentan las entradas.

Answer 6

Para HashMaps muy grandes en sistemas críticos, donde obtener la capacidad inicial incorrecta puede ser muy problemático, puede necesitar información empírica para determinar la mejor manera de inicializar su Mapa.

CollectionSpy ( collectionspy.com ) es un nuevo generador de perfiles de Java que le permite ver en un abrir y cerrar de ojos que los HashMaps están a punto de necesitar un reajuste, cuántas veces han sido repetidos en el pasado, y más. Una herramienta ideal para determinar argumentos seguros de capacidad inicial para constructores de contenedores basados ​​en capacidad.

Answer 7

La respuesta que dio Yuval es correcta solo para Hashtable. HashMap utiliza cubos de potencia de dos, por lo que para HashMap, Zarkonnen es realmente correcto. Puede verificar esto desde el código fuente:

  // Find a power of 2 >= initialCapacity
  int capacity = 1;
  while (capacity < initialCapacity)
  capacity <<= 1;

Entonces, aunque el factor de carga de 0.75f ​​sigue siendo el mismo entre Hashtable y HashMap, debe usar una capacidad inicial n * 2 donde n es la cantidad de elementos que planea almacenar en HashMap. Esto asegurará las velocidades de obtención / lanzamiento más rápidas.

Answer 8

Ejecuté algunas pruebas unitarias para ver si estas respuestas eran correctas y resultó que usar:

(int) Math.ceil(requiredCapacity / loadFactor);

ya que la capacidad inicial brinda lo que usted desea para un HashMap o un Hashtable . Con "lo que quieres" me refiero a que agregar elementos requiredCapacity Capas al mapa no hará que la matriz que está envolviendo cambie de tamaño y la matriz no será más grande que la requerida. Dado que la capacidad de carga predeterminada es 0.75, la inicialización de un HashMap funciona de esta manera:

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity / 0.75));

Dado que un HashSet es solo una envoltura para HashMap, la misma lógica también se aplica allí, es decir, puede construir un HashSet de manera eficiente así:

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity / 0.75));

La respuesta de @Yuval Adam es correcta para todos los casos excepto donde (requiredCapacity / 0.75) es una potencia de 2, en cuyo caso asigna demasiada memoria.
La respuesta de @EntEdible utiliza demasiada memoria en muchos casos, ya que el propio constructor de HashMap se ocupa de los problemas que quiere que la matriz de mapas tenga un tamaño que es una potencia de 2.

Answer 9

En las bibliotecas de guayaba de Google hay una función que crea un HashMap optimizado para un número esperado de elementos: newHashMapWithExpectedSize

de los documentos:

Crea una instancia de HashMap, con una "capacidad inicial" lo suficientemente alta como para contener los elementos expectedSize sin crecimiento ...