¿Por qué ArrayList crece a una velocidad de 1.5, pero para Hashmap es 2?

Question

Según la implementación de Sun Java, durante la expansión, ArrayList crece a 3/2 su capacidad inicial mientras que para HashMap la tasa de expansión es doble. ¿Cuál es la razón detrás de esto?

Según la implementación, para HashMap, la capacidad siempre debe estar en poder de dos. Esa puede ser una razón para el comportamiento de HashMap. Pero en ese caso, la pregunta es, ¿para HashMap por qué la capacidad siempre debe estar en poder de dos?

Answer 1

La parte costosa para aumentar la capacidad de una ArrayList es copiar el contenido de la matriz de respaldo en uno nuevo (más grande).

Para HashMap, está creando una nueva matriz de respaldo y poniendo todas las entradas de mapa en la nueva matriz. Y, cuanto mayor sea la capacidad, menor será el riesgo de colisiones. Esto es más caro y explica por qué el factor de expansión es mayor. La razón de 1.5 vs. 2.0? Considero que esto es una "buena práctica" o una "buena compensación".

Answer 2

Hashing aprovecha la distribución de datos de manera uniforme en los segmentos. El algoritmo intenta evitar entradas múltiples en los depósitos ("colisiones hash"), ya que disminuirán el rendimiento.

Ahora cuando se alcanza la capacidad de un HashMap, el tamaño se amplía y los datos existentes se vuelven a distribuir con los nuevos depósitos. Si el aumento de tamaño fuera demasiado pequeño, esta reasignación de espacio y redistribución ocurriría con demasiada frecuencia.

Answer 3

que no se puede dar una razón por la que esto es así (que tendría que preguntar a los desarrolladores de Sun), pero a ver cómo esto ocurre echar un vistazo a la fuente:

1. HashMap: Tomar una ver cómo cambia de tamaño para HashMap nuevo tamaño (source línea 799)

    resize(2 * table.length); 
   

2. ArrayList: source, la línea 183:

   int newCapacity = (oldCapacity * 3)/2 + 1; 
   

Actualización: I erróneamente vinculado a las fuentes de Apache Harmony JDK - lo cambió a Sun's JDK.

Answer 4

La forma en que HashMap está diseñado/implementado su número subyacente de cubos debe ser una potencia de 2 (incluso si le da un tamaño diferente, lo convierte en una potencia de 2), crece en un factor de dos cada uno hora. Un ArrayList puede ser de cualquier tamaño y puede ser más conservador en su crecimiento.

Answer 5

Una regla general para evitar colisiones en Maps es mantener el factor de carga máximo en alrededor de 0.75 Para disminuir la posibilidad de colisiones y evitar costosos procesos de copia, HashMap crece a un ritmo mayor.

También como dice @Peter, debe ser una potencia de 2.

Answer 6

para HashMap por qué la capacidad siempre debe estar en poder de dos?

Puedo pensar en dos razones.

1. Puede determinar rápidamente el depósito al que va un hashcode.Solo necesita un módulo bit a bit Y no caro. int bucket = hashcode & (size-1);

2. Digamos que tenemos un factor de crecimiento de 1.7. Si comenzamos con un tamaño 11, el siguiente tamaño sería 18, luego 31. No hay problema. ¿Derecha? Pero los códigos hash de Strings en Java se calculan con un factor primo de 31. El cubo al que entra una cadena, hashcode%31, se determina únicamente por el último carácter de la Cadena. Adiós O(1) si almacena carpetas que terminan en /. Si usa un tamaño de, por ejemplo, 3^n, , la distribución no empeorará si aumenta n. Pasando del tamaño 3 al 9, cada elemento en el cubo 2, ahora irá al cubo 2, 5 o 7, dependiendo del dígito más alto. Es como dividir cada cubo en tres pedazos. Por lo tanto, se preferiría un tamaño de factor de crecimiento entero. (Off supuesto, todo esto depende de cómo se calcule hashcodes, pero un factor de crecimiento arbitraria no se siente 'estable'.)