「Java 」ArrayList、LinkedList、Vector区别

[StrayCamel247]

java常用的

三个类的继承关系图

• public class ArrayList_<E>_

• public class LinkedList_<E>_

• public class Vector_<E>_

ArrayList

• 数组对象
• 从构造源码可知初始的capacity会默认给个10，初始化给定足够的capacity在新增元素时相比为给定初始化capacity再在每次新增时扩容时间开销会更少

Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

• size和capacity可以随元素新增动态变化
• for遍历更快
• 执行时非同步等
• 容量上最大是按照Integer._MAX_VALUE来设计；但是尝试分配最大值时肯跟会导致vm限制和_Java heap space限制的报错

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
// 获取容量时会进行比较，最大值定为Integer.MAX_VALUE
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
...

• 增长因子，每次为容量的一半或者1

/**
 * @author straycamel
 * @date 2021/6/23
 */
public class demo {
    public static void main(String[] args) throws Exception {
        ArrayList<Integer> list = new ArrayList<Integer>(10);
        for (int i = 0; i < 17; i++) {
            list.add(i);
            System.out.format("ArrayList Size: %2d, Capacity: %2d%n",
                              list.size(), getCapacity(list));
        }
    }
    /**
     * 获取ArrayList的容量
     * @author straycamel
     * @date 2021/6/23
     */
    static int getCapacity(ArrayList<?> l) throws Exception {
        Field dataField = ArrayList.class.getDeclaredField("elementData");
        dataField.setAccessible(true);
        return ((Object[]) dataField.get(l)).length;
    }
}
/*结果
ArrayList Size:  3, Capacity: 10
ArrayList Size:  4, Capacity: 10
ArrayList Size:  5, Capacity: 10
ArrayList Size:  6, Capacity: 10
ArrayList Size:  7, Capacity: 10
ArrayList Size:  8, Capacity: 10
ArrayList Size:  9, Capacity: 10
ArrayList Size: 10, Capacity: 10
ArrayList Size: 11, Capacity: 15
ArrayList Size: 12, Capacity: 15
ArrayList Size: 13, Capacity: 15
ArrayList Size: 14, Capacity: 15
ArrayList Size: 15, Capacity: 15
ArrayList Size: 16, Capacity: 22
ArrayList Size: 17, Capacity: 22
*/

LinkedList

• LinkedList是一个链表，相对于ArrayList更快的新增删除，但是查询比较慢。
• Iterator遍历更快
• 链表每个元素都会存储前后的位置，内存上总量相比ArrayList更大

Vector

• 增长因子可自定义
• 通过维护capacity和capacityIncrement增量来优化存储管理
• 同步功能，但是有性能损失
• 初始length是10 超过length时 以100%比率增长，相比于ArrayList更多消耗内存
• Vector 把集合的每个操作（增删改查）都加上了锁，而这锁从来都不是必须的
• Vector会在你不需要进行线程安全的时候，强制给你加锁，导致了额外开销，所以慢慢被弃用了

Vector<Integer> t=new Vector<Integer>();
for (int i = 0; i < 17; i++) {
    t.add(i);
    System.out.format("ArrayList Size: %2d,%2d\n",
                        t.size(),t.capacity());
}
System.out.println(t);
/*
ArrayList Size:  1,10
ArrayList Size:  2,10
ArrayList Size:  3,10
ArrayList Size:  4,10
ArrayList Size:  5,10
ArrayList Size:  6,10
ArrayList Size:  7,10
ArrayList Size:  8,10
ArrayList Size:  9,10
ArrayList Size: 10,10
ArrayList Size: 11,20
ArrayList Size: 12,20
ArrayList Size: 13,20
ArrayList Size: 14,20
ArrayList Size: 15,20
ArrayList Size: 16,20
ArrayList Size: 17,20
*/

引伸思考的问题

java新手，欢迎交流

运行中的java如何查看每个变量，的内存开销？

• jmap结果的每个class name是指的什么？

straycamel@B-P0PMMD6R-2147 Leetcode % jmap -histo 35861

 num     #instances         #bytes  class name
----------------------------------------------
   1:           965        4894672  [I
   2:          1823        1604616  [B
   3:          8868         916808  [C
   4:          6901         165624  java.lang.String
   5:           762          87088  java.lang.Class
   6:          1708          77336  [Ljava.lang.Object;
   7:           871          27872  java.util.HashMap$Node
   8:          ...................

java运行内存开销是否可以实时查看？

参考文献

https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html
https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
https://zhuanlan.zhihu.com/p/34828859