java集合框架

ArrayList简介

ArrayList是list接口的可变数组的实现。与一般数组不同的是，它的容量可以动态增长。

ArrayList继承了AbstractList抽象类，实现了List，RandomAccess, Cloneable, java.io.Serializable接口，根据实现的接口看，它支持随机访问，支持克隆，支持序列化。

Arraylist的特点：1）保证元素按照规定的顺序排列--元素的输出顺序和输入顺序一致；2）可快速随机访问；3）元素可以为null

插播一下

RandomAccess接口是一个标记接口（marker），它没有任何方法，被list的子类使用，如果list的子类实现了此接口，则代表它可以快速随机访问存储的元素.

他的意义在于当要实现某些算法时，会判断当前类是否实现了RandomAccess接口,会根据结果选择不同的算法.例如：

1public static void shuffle(List<?> var0, Random var1) {
2        int var2 = var0.size();
3        if (var2 >= 5 && !(var0 instanceof RandomAccess)) {
4            Object[] var6 = var0.toArray();
5
6            for(int var4 = var2; var4 > 1; --var4) {
7                swap(var6, var4 - 1, var1.nextInt(var4));
8            }
9
10            ListIterator var7 = var0.listIterator();
11
12            for(int var5 = 0; var5 < var6.length; ++var5) {
13                var7.next();
14                var7.set(var6[var5]);
15            }
16        } else {
17            for(int var3 = var2; var3 > 1; --var3) {
18                swap(var0, var3 - 1, var1.nextInt(var3));
19            }
20        }
21
22    }

View Code

jdk建议实现了RandomAccess接口的list遍历时使用loop去遍历，并未实现（例如LinkedList）的使用迭代器去遍历（因为效率原因，在最后我会测试完贴代码上来的）。

RandomAccess源码的注释里面都写了，啦啦啦：

1/*
2 * Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved.
3 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
4 *
5 *
6 *
7 *
8 *
9 *
10 *
11 *
12 *
13 *
14 *
15 *
16 *
17 *
18 *
19 *
20 *
21 *
22 *
23 *
24 */
25
26package java.util;
27
28/**
29 * Marker interface used by <tt>List</tt> implementations to indicate that
30 * they support fast (generally constant time) random access.  The primary
31 * purpose of this interface is to allow generic algorithms to alter their
32 * behavior to provide good performance when applied to either random or
33 * sequential access lists.
34 *
35 * <p>The best algorithms for manipulating random access lists (such as
36 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
37 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
38 * algorithms are encouraged to check whether the given list is an
39 * <tt>instanceof</tt> this interface before applying an algorithm that would
40 * provide poor performance if it were applied to a sequential access list,
41 * and to alter their behavior if necessary to guarantee acceptable
42 * performance.
43 *
44 * <p>It is recognized that the distinction between random and sequential
45 * access is often fuzzy.  For example, some <tt>List</tt> implementations
46 * provide asymptotically linear access times if they get huge, but constant
47 * access times in practice.  Such a <tt>List</tt> implementation
48 * should generally implement this interface.  As a rule of thumb, a
49 * <tt>List</tt> implementation should implement this interface if,
50 * for typical instances of the class, this loop:
51 * <pre>
52 *     for (int i=0, n=list.size(); i &lt; n; i++)
53 *         list.get(i);
54 * </pre>
55 * runs faster than this loop:
56 * <pre>
57 *     for (Iterator i=list.iterator(); i.hasNext(); )
58 *         i.next();
59 * </pre>
60 *
61 * <p>This interface is a member of the
62 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
63 * Java Collections Framework</a>.
64 *
65 * @since 1.4
66 */
67public interface RandomAccess {
68}

View Code

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。但是扩容这个操作不是同步的，所以不要在并发情况下使用ArrayList啊，如果多个线程都在改它的结构（数量发生变化，一会多了，一会少了）的话，那么恭喜你，你的代码要崩掉了。并发情况下可以用vector，CopyOnWriteArrayList（建议使用），或者你就想用ArrayList，这样也可以的：

List list = Collections.synchronizedList(new ArrayList(...));

ArrayList源码解析（jdk版本1.8.0_144）

1）几个比较不对很重要的初始化的值

1private static final int DEFAULT_CAPACITY = 10;//默认的大小
2
3    private static final Object[] EMPTY_ELEMENTDATA = {};//空数组
4
5
6    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};
7   //没有给定size的时候，构造方法就默认给这个啦，默认大小是10
8
9
10    transient Object[] elementData; // 数据就是在这个数组里面村的
11
12    private int size;//list的大小啦

View Code

其中最最重要的两个对象：

elementData 是"Object[] 类型的数组"，它保存了添加到ArrayList中的元素。实际上，elementData是个动态数组，我们能通过构造函数 ArrayList(int initialCapacity)来执行它的初始容量为initialCapacity；如果通过不含参数的构造函数ArrayList()来创建 ArrayList，则elementData的容量默认是10。elementData数组的大小会根据ArrayList容量的增长而动态的增长。

size 则是动态数组的实际大小

2）构造方法

ArrayList提供了三种构造器：

1public ArrayList(int initialCapacity) {
2        if (initialCapacity > 0) {
3            this.elementData = new Object[initialCapacity];
4        } else if (initialCapacity == 0) {
5            this.elementData = EMPTY_ELEMENTDATA;
6        } else {
7            throw new IllegalArgumentException("Illegal Capacity: "+
8                                               initialCapacity);
9        }
10    }
11
12    /**
13     * Constructs an empty list with an initial capacity of ten.
14     */
15    public ArrayList() {
16        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
17    }
18
19    /**
20     * Constructs a list containing the elements of the specified
21     * collection, in the order they are returned by the collection's
22     * iterator.
23     *
24     * @param c the collection whose elements are to be placed into this list
25     * @throws NullPointerException if the specified collection is null
26     */
27    public ArrayList(Collection<? extends E> c) {
28        elementData = c.toArray();
29        if ((size = elementData.length) != 0) {
30            // c.toArray might (incorrectly) not return Object[] (see 6260652)
31            if (elementData.getClass() != Object[].class)
32                elementData = Arrays.copyOf(elementData, size, Object[].class);
33        } else {
34            // replace with empty array.
35            this.elementData = EMPTY_ELEMENTDATA;
36        }
37    }

1）自己指定大小

2）不指定大小，默认给一个，默认值为10（第一次添加元素的时候，设置的size为默认大小10）

3）构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表

ArrayList时怎么构造一个默认初始容量为10的空列表：

初始情况：elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}； size = 0;
当向数组中添加第一个元素时，通过add(E e)方法中调用的ensureCapacityInternal(size + 1)方法，即ensureCapacityInternal(1)；
在ensureCapacityInternal(int minCapacity)方法中，可得的minCapacity=DEFAULT_CAPACITY=10，然后再调用ensureExplicitCapacity(minCapacity)方法，即ensureExplicitCapacity(10)；
在ensureExplicitCapacity(minCapacity)方法中调用grow(minCapacity)方法，即grow(10)，此处为真正具体的数组扩容的算法，在此方法中，通过**elementData = Arrays.copyOf(elementData, 10)**设置了默认的初始大小10.

所以如果你没有定义arrayList的大小的话，他在第一次添加元素的时候，调用了给list调整大小的方法grow()，给list设置了默认大小10.具体还是不太明白为啥的，再本地debug仔细看下最好了，我也是debug看的。

3）扩展容量

我们经常说数据和arrayList有啥区别，会说数组的容量时固定的，不可变的；arrayList可以动态调整大小。

那arrayList时如何调整大小呢？

请看源码：

1public boolean add(E e) {
2        ensureCapacityInternal(size + 1);  // Increments modCount!!
3        elementData[size++] = e;
4        return true;
5    }
6 private void ensureCapacityInternal(int minCapacity) {
7        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
8            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
9        }
10
11        ensureExplicitCapacity(minCapacity);
12    }
13  private void ensureExplicitCapacity(int minCapacity) {
14        modCount++;
15
16        // overflow-conscious code
17        if (minCapacity - elementData.length > 0)
18            grow(minCapacity);
19    }
20  private void grow(int minCapacity) {
21        // overflow-conscious code
22        int oldCapacity = elementData.length;
23        int newCapacity = oldCapacity + (oldCapacity >> 1);
24        if (newCapacity - minCapacity < 0)
25            newCapacity = minCapacity;
26        if (newCapacity - MAX_ARRAY_SIZE > 0)
27            newCapacity = hugeCapacity(minCapacity);
28        // minCapacity is usually close to size, so this is a win:
29        elementData = Arrays.copyOf(elementData, newCapacity);
30    }

用add()方法举个栗子哈，addAll()同理。

从以上源码可以看出，每当向数组中添加元素时，都要去检查添加元素后的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容实质上是通过私有的方法ensureCapacityInternal(int minCapacity) -> ensureExplicitCapacity(int minCapacity) -> grow(int minCapacity)来实现的。看代码也可以看出来，扩容了1.5倍啦。

Vector

Vector就不多说了，因为它其实就跟arrayList差不多啦，就时一个同步的arrayList，可以再并发情况下使用，来看看源码：

1public synchronized boolean add(E e) {
2        modCount++;
3        ensureCapacityHelper(elementCount + 1);
4        elementData[elementCount++] = e;
5        return true;
6    }

用add()方法举个栗子，其实很多方法都加入了synchronized同步语句，来保证线程安全。但是我很少见到有人使用vector的，因为再并发下，效率确实不怎么高。如果有并发的需求，可以用之前提到CopyOnWriteArrayList。

LinkedList简介

LinkedList基于链表（双端链表）实现，删除和插入操作速度快于arrayList，但也是因为基于链表，所以不支持随机访问，查询速度比arrayList慢。

LinkedList继承AbstractSequentialList类，实现了List，Deque，Cloneable, java.io.Seriaizable接口。

LinkedList源码解析（jdk版本1.8.0_144）

1transient int size = 0;
2  transient Node<E> first;
3  transient Node<E> last;

size代表的时链表的长度，也就是list的大小了；两个变量，first指向链表头部，last指向链表尾部。

再看一下Node的定义：

1private static class Node<E> {
2        E item;
3        Node<E> next;
4        Node<E> prev;
5
6        Node(Node<E> prev, E element, Node<E> next) {
7            this.item = element;
8            this.next = next;
9            this.prev = prev;
10        }
11    }

很明显可以看出来这是一个双端链表了，分别保存了对上一个节点及下一个节点的引用。

再看几个常用的方法：

1，添加操作。

1public boolean add(E e) {
2        linkLast(e);
3        return true;
4    }
5
6void linkLast(E e) {
7        final Node<E> l = last;//指向链表尾部
8        final Node<E> newNode = new Node<>(l, e, null);//以当前的尾部节点为新节点的pre，创建新节点。
9        last = newNode;//将链表尾部指向新节点
10        if (l == null)//如果链表为空，那么新节点是头节点也是尾节点
11            first = newNode;
12        else//链表不为空，那么将该结点作为原链表尾部的next
13            l.next = newNode;
14        size++;
15        modCount++;
16    }

2，在指定位置添加元素

1public void add(int index, E element) {
2        checkPositionIndex(index);//检查index时否合法
3
4        if (index == size)//如果index等于size，那就添加到尾部
5            linkLast(element);
6        else
7            linkBefore(element, node(index));//否则就往中间插入啦
8    }
9
10 void linkBefore(E e, Node<E> succ) {
11        // assert succ != null;
12        final Node<E> pred = succ.prev;
13        final Node<E> newNode = new Node<>(pred, e, succ);
14        succ.prev = newNode;
15        if (pred == null)
16            first = newNode;
17        else
18            pred.next = newNode;
19        size++;
20        modCount++;
21    }
22
23  Node<E> node(int index) {
24        // assert isElementIndex(index);
25
26//如果index位置在链表前半部分，从头开始遍历，否则，从尾部开始遍历
27
28        if (index < (size >> 1)) {
29            Node<E> x = first;
30            for (int i = 0; i < index; i++)
31                x = x.next;
32            return x;
33        } else {
34            Node<E> x = last;
35            for (int i = size - 1; i > index; i--)
36                x = x.prev;
37            return x;
38        }
39    }

3，获取指定索引的数据

1public E get(int index) {
2        checkElementIndex(index);//检查索引是否合法
3        return node(index).item;//查找数据
4    }

这就是为啥说linkedList查找数据慢了，它是用链表实现的，不像数组有索引标识，所以当然慢啊。

好了就这么多吧，举几个栗子就行，我这一篇都写了好久了，快懒死我了，写完我好写别的啊。

我不是大神啊，如果有人不小心看到我的文章，觉得我说得不对，大家就提出来啊，别骂我啊。

ArrayList简介

插播一下

ArrayList源码解析（jdk版本1.8.0_144）

1）几个比较不对很重要的初始化的值

2）构造方法

3）扩展容量

Vector

LinkedList简介

LinkedList源码解析（jdk版本1.8.0_144）

再看几个常用的方法：

评论区

相关推荐