Производительность: создание ArrayList из HashMap.values ​​() - PullRequest
Новая
       8

Производительность: создание ArrayList из HashMap.values ​​()

19 голосов
/ 23 ноября 2010

Вопрос в том, сколько стоит создание ArrayList из коллекции HashMap.values ​​()?Или создание коллекции значений в одиночку?Предполагая, что Map.size ()> 100k.Объекты также могут храниться в ArrayList (вместо HashMap) все время, что влияет на другие части (модификации элементов, легко по ключу)ArrayList используется для итерации каждого n-го элемента.(Вот почему коллекцию значений нельзя использовать напрямую).Во время итерации никаких изменений не производится.

Ответы [ 5 ]

39 голосов
/ 23 ноября 2010

HashMap.values() не возвращает ArrayList значений, но Values Коллекция.

Источник: 

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

Values является AbstractCollection.Причина значений - просто ссылка на итератор HashMap.

Ваш вопрос:

Вопрос в том, сколько стоит создание ArrayList из коллекции HashMap.values ​​()?

Это линейная сложность (как сказал Божо), поскольку 

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

ArrayList, valuesList вызывает метод hashMap toArray() коллекции, который по существу выполняет цикл forот 0..N (размер) элемента в коллекции.

Надеюсь, это поможет.

8 голосов
/ 23 ноября 2010

HashMap внутренне сохраняет значения в коллекции values. Взгляните на исходный код из AbstractMap, родительский элемент HashMap.

Итак, HashMap.values() напрямую возвращает Collection. Здесь нет вычислений или копирования данных. Это так быстро, как только может.

Просто получите значения и выполните цикл 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
)
3 голосов
/ 23 ноября 2010

Чтобы уточнить решение @ Божо, вы можете просто сделать. 

int count = 0;
for(Value value: map.values())
   if(count++ % 5 == 0)
     // do something.
2 голосов
/ 23 ноября 2010

Вы можете использовать Iterator для пропуска элементов - просто звоните next() много раз.

Создание списка любой коллекции имеет линейную сложность.

0 голосов
/ 23 ноября 2010

Вы можете создать свой собственный HashMap, который содержит коллекцию значений Arraylist напрямую (я не верю, что HashMap делает это бесплатно, структура данных для него другая). Но это требует некоторого дополнительного кодирования с Вашей стороны.

...