java - ordenar - Rendimiento: Crear un ArrayList desde HashMap.values()

order map key java

Question

La pregunta es cuánto cuesta crear un ArrayList a partir de una colección HashMap.values ​​(). ¿O crear la colección de valores sola? Suponiendo Map.size ()> 100k. Los objetos también se podrían mantener en ArrayList (en lugar de HashMap) todo el tiempo, lo que tiene implicaciones en otras partes (modificaciones de elementos, fáciles por clave). El ArrayList se usa para iterar sobre cada n-ésimo elemento. (Es por eso que la colección de valores no puede ser usada directamente). No se realizan modificaciones durante la iteración.

Answer 1

Para elaborar sobre la solución de @Bozho, simplemente puede hacerlo.

int count = 0;
for(Value value: map.values())
   if(count++ % 5 == 0)
     // do something.

Answer 2

Puede crear su propio HashMap, que contiene la colección de valores de Arraylist directamente (no creo que HashMap lo haga de forma gratuita, la estructura de datos es diferente). Pero esto requiere una codificación adicional de tu lado.

Answer 3

Puede usar un Iterator para omitir elementos; simplemente llame a next() muchas veces.

Crear una lista de cualquier colección tiene una complejidad lineal.

Answer 4

HashMap.values() no devuelve una ArrayList de valores sino una colección de Values .

Fuente:

 public Collection<V> values() {
        Collection<V> vs = values;
        return (vs != null ? vs : (values = new Values()));
    }

Values son una AbstractCollection . La razón de los valores es solo para hacer referencia al iterador de HashMap.

Tu pregunta:

La pregunta es cuánto cuesta crear un ArrayList a partir de una colección HashMap.values ​​().

Esa es una complejidad lineal (como dijo Bozho) desde

ArrayList<V> valuesList = new ArrayList<V>(hashMap.values());

En ArrayList, valuesList llama al método hashMap toArray() la colección, que esencialmente realiza un bucle for desde el elemento 0..N (tamaño) en la colección.

Espero que esto ayude.

Answer 5

HashMap almacena internamente los valores en los valores de una Colección. Eche un vistazo al código fuente de AbstractMap , el padre de HashMap .

Así que HashMap.values() devuelve directamente una Collection . No hay computación o copia de datos hecha. Es lo más rápido que puede ser.

Solo obtén los valores y luego haz un bucle for:

int n = 5;  // every 5th element
Object[] values = hashMap.values().toArray();
int size = values.length;
for (int i = 0; i < size; i += n){
   values[i];
   // do something
)