性能：从 HashMap.values() 创建 ArrayList

Question

问题是从 HashMap.values() 集合创建 ArrayList 需要多少钱？还是单独创造价值集合？ 假设 Map.size() > 10万。 对象也可以一直保存在 ArrayList（而不是 HashMap）中，这对其他部分有影响（元素的修改，通过键很容易）。 ArrayList 用于迭代每个第 n 个元素。 （这就是为什么不能直接使用值集合的原因）。迭代期间不进行任何修改。

Answer 1

HashMap.values() 不返回值的 ArrayList 而是返回 Values 集合。

来源：

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

Values 是一个 AbstractCollection。 value 的原因只是为了引用 HashMap 的迭代器。

你的问题：

问题是要花多少钱
从 a 创建一个 ArrayList
HashMap.values() 集合？

这是一个线性复杂度（正如 Bozho 所说），因为

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

ArrayList、valuesList 调用集合 hashMap toArray() 方法，该方法本质上执行一个 for 从集合中的 0..N（大小）元素循环。

希望这有帮助。

Answer 2

HashMap 在内部将值存储在 Collection 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
)

Answer 3

要详细说明@Bozho 的解决方案，您可以这样做。

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

Answer 4

您可以使用Iterator来跳过元素 - 只需多次调用next()即可。

创建任何集合的列表都具有线性复杂度。

Answer 5

您可以创建自己的 HashMap，它直接保存值的 Arraylist 集合（我不相信 HashMap 是免费的，它的数据结构是不同的）。但这需要您进行一些额外的编码。