集合框架的概述

集合、数组都是对多个数据进行存储操作的结构,简称Java容器。 说明:此时的存储,主要指的是内存层面的存储,不涉及到持久化的存储(.txt .jpg等)。

以下描述引用于onJava 8:
集合(Collection) :一个独立元素的序列,这些元素都服从一条或多条规则。List 必须以插入的顺序保存元素, Set 不能包含重复元素, Queue 按照排队规则来确定对象产生的顺序(通常与它们被插入的顺序相同)

关于数组的概述

数组在存储多个数据方面的特点:
① 一旦初始化以后,其长度就确定了;
② 数组一旦定义好,其元素的类型也就确定了。我们也就只能操作指定类型的数据了。比如:String[] string;int[] int

数组在存储多个数据方面的缺点:
① 一旦初始化以后,其长度就不可修改。
② 数组中提供的方法非常有限,对于添加、删除、插入数据等操作,非常不便,同时效率不高。
③ 获取数组中实际元素的个数的需求,数组没有现成的属性或方法可用。
④ 数组存储数据的特点:有序、可重复。对于无序、不可重复的需求,不能满足。

集合涉及的接口、实现类

|—-Collection接口:单列集合,用来存储一个一个的对象
 |—-List接口:存储有序的、可重复的数据。
  |—-ArrayList、LinkedList、Vector
 |—-Set接口:存储无序的、不可重复的数据。
  |—-HashSet、LinkedHashSet、TreeSet

List是Collection的子接口,ArrayList、LinkedList、Vector是List接口的实现类;如下图:
Collection接口及其实现类

|—-Map接口:双列集合,用来存储一对(key - value)一对的数据。
 |—-HashMap、LinkedHashMap、TreeMap、Hashtable、Properties

HashMap、LinkedHashMap、TreeMap、Hashtable、Properties是Map接口的实现类。

Collection接口中常用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
增:add(Object obj)

删:remove(int index) / remove(Object obj)

改:set(int index, Object ele)

查:get(int index)

插:add(int index, Object obj)

长度:size() //默认情况下返回的是元素的个数,而不是数组本身的长度

遍历:

①Iterator迭代器方式

②增强for循环

③普通的循环

ArrayList 与 LinkedList 的区别

ArrayList

  • 优点:ArrayList 是实现了基于动态数组的数据结构,因为地址连续,一旦数据存储好了,查询操作效率会比较高(在内存里是连着放的)。
  • 缺点:因为地址连续,ArrayList 要移动数据,所以插入和删除操作效率比较低。

LinkedList

  • 优点:LinkedList 基于链表的数据结构,地址是任意的,所以在开辟内存空间的时候不需要等一个连续的地址。对于新增和删除操作 add 和 remove ,LinedList 比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。
  • 缺点:因为 LinkedList 要移动指针,所以查询操作性能比较低。

适用场景分析

  • 当需要对数据进行对随机访问的情况下,选用 ArrayList 。

  • 当需要对数据进行多次增加删除修改时,采用 LinkedList 。

    如果容量固定,并且只会添加到尾部,不会引起扩容,优先采用 ArrayList 。

  • 当然,绝大数业务的场景下,使用 ArrayList 就够了。主要是,注意好避免 ArrayList 的扩容,以及非顺序的插入。

ArrayList 与 Vector 区别?

ArrayList 和 Vector 都是用数组实现的,主要有这么三个区别:

  • 1、Vector 是多线程安全的,线程安全就是说多线程访问同一代码,不会产生不确定的结果,而 ArrayList 不是。这个可以从源码中看出,Vector 类中的方法很多有 synchronized 进行修饰,这样就导致了 Vector 在效率上无法与 ArrayList 相比。

    Vector 是一种老的动态数组,是线程同步的,效率很低,一般不赞成使用。

  • 2、两个都是采用的线性连续空间存储元素,但是当空间不足的时候,两个类的增加方式是不同。

  • 3、Vector 可以设置增长因子,而 ArrayList 不可以。

适用场景分析:

  • 1、Vector 是线程同步的,所以它也是线程安全的,而 ArrayList 是线程无需同步的,是不安全的。如果不考虑到线程的安全因素,一般用 ArrayList 效率比较高。

    实际场景下,如果需要多线程访问安全的数组,使用 CopyOnWriteArrayList 。

  • 2、如果集合中的元素的数目大于目前集合数组的长度时,在集合中使用数据量比较大的数据,用 Vector 有一定的优势。

    这种情况下,使用 LinkedList 更合适。

ArrayList初始化解析

ArrayList源码分析之jdk 7:
ArrayList list = new ArrayList();
执行该语句时,底层就会直接创建一个长度是10的Object[]数组elementData;

list.add(123);相当于elementData[0] = new Integer(123);

ArrayList源码分析之jdk 8:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
transient Object[] elementData;

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

上图为jdk 8中的ArrayList部分源码,在执行语句:ArrayList list = new ArrayList();时;源码中并没用直接创建长度为10的数组,而是先将数组初始化为空:Object[] elementData;在第一次调用list.add(123)方法时,ArrayList才会去创建对应长度内的数组(若第一次add的数据的长度大于默认长度,那么数组的长度会定义为该数据的长度;若小于,则创建长度为10的数组),并将数据123添加到elementData数组中。

小结:jdk 7 中的ArrayList的对象的数组创建类似于单例的饿汉式(提前造好);而jdk 8中的ArrayList的对象
的数组创建类似于单例的懒汉式(需要时才初始化),延迟了数组的创建,节省内存。

ArrayList扩容解析

先附上jdk 8中ArrayList的有关扩容部分的源码,主要是grow()方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

根据源码知道,ArrayList扩容最主要的在grow()方法,以下是该方法的一些解释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private void grow(int minCapacity) {
// 形参minCapacity = size + 1;可以理解为需要的数组长度
// 获取当前数组的长度
int oldCapacity = elementData.length;
// 通过位移运算(计算机底层中位移运算更快),将新的数组长度定义为原来的1.5倍
//为什么扩容的是1.5倍而不是其他倍?后面会解释
//此处若溢出,newCapacity将为负值,不影响后续条件的判断
int newCapacity = oldCapacity + (oldCapacity >> 1);
//比较新长度与需要的长度
if (newCapacity - minCapacity < 0)
//如果扩容1.5倍后的长度仍比需要的长度小,则把newCapacity定义为需要的长度
newCapacity = minCapacity;

//此条件是为了处理溢出的情况
//比较计算出的新长度与MAX_ARRAY_SIZE:ArrayList允许的最大长度
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果扩容后的长度大于允许的最大长度,调用hugeCapacity方法
//根据hugeCapacity方法源码可知,当minCapacity > MAX_ARRAY_SIZE时,将返回Integer.MAX_VALUE赋给新长度
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//调用Arrays.copyOf方法,传入旧的数组、扩容后的长度;返回一个拥有新的长度的数组(原有值不变)
elementData = Arrays.copyOf(elementData, newCapacity);
}

为什么扩容的是1.5倍而不是其他倍?
(1)因为一次性扩容太大(例如2.5倍)可能会浪费更多的内存(1.5倍最多浪费33%,而2.5被最多会浪费60%,3.5倍则会浪费71%……)。
(2)但是一次性扩容太小,需要多次对数组重新分配内存,对性能消耗比较严重。
(3)所以1.5倍是个经验值,它既能满足性能需求,也不会造成很大的内存消耗。
(4)所以扩容扩多少,是JDK开发人员在时间、空间上做的一个权衡,提供出来的一个比较合理的数值。

总结:
创建集合的时候,如果能知道总长度是多少,最好定义集合的长度,避免因扩容带来的资源浪费和内存消耗。

ArrayList遍历方式解析

ArrayList遍历总的有三种:
1、通过普通for循环的方式;
2、foreach的方式;
3、Iterator迭代器的方式。

这三种方式相信大家都知道,所以就不写相关的代码了,但是对于ArrayList来说哪种方式效率更高,更快呢?
ArrayList实现了RandomAccess接口,其中RandomAccess接口又这么一段描述:

1
2
3
4
5
6
7
8
9
10
* for typical instances of the class, this loop:
*
* for (int i=0, n=list.size(); i &lt; n; i++)
* list.get(i);
*
* runs faster than this loop:
*
* for (Iterator i=list.iterator(); i.hasNext(); )
* i.next();
*

从描述中,可以看出实现RandomAccess接口的集合类,使用for循环的效率会比Iterator高。
RandomAccess接口为ArrayList带来的好处:
1、可以快速随机访问集合。
2、使用快速随机访问(for循环)效率可以高于Iterator。

注意:ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的:在创建迭代器之后,除非通过迭代器自身的remove或add方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测bug。

ArrayList之多线程

ArrayList本身不是线程安全的,在需要多线程操作集合时,需要使用:
List list1 = Collections.synchronizedList(list);
该方法可使将指定集合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全问题;以下附上synchronizedList()方法的源码,可以看到,返回的list对象里,大部分方法内部都使用了synchronized关键字保证同步,锁mutex是对象本身。
但是注意,关于迭代器的方法并没有加上synchronized同步锁,所以在多线程使用迭代器的场景下,需要在外部加上synchronized同步锁保证线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}

static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;

final List<E> list;

SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}

public boolean equals(Object o) {
if (this == o)
return true;
synchronized (mutex) {return list.equals(o);}
}
public int hashCode() {
synchronized (mutex) {return list.hashCode();}
}

public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}

public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}

public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}

public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}

public ListIterator<E> listIterator(int index) {
return list.listIterator(index); // Must be manually synched by user
}

public List<E> subList(int fromIndex, int toIndex) {
synchronized (mutex) {
return new SynchronizedList<>(list.subList(fromIndex, toIndex),
mutex);
}
}
}

ArrayList相关面试题

什么情况下你会使用ArrayList?什么时候你会选择LinkedList?

多数情况下,遇到访问元素比插入或者是删除元素更加频繁的时候,应该使用ArrayList。
另外一方面,当你在某个特别的索引中,插入或者是删除元素更加频繁,或者你压根就不需要访问元素的时候,你会选择LinkedList。
这里的主要原因是,在ArrayList中访问元素的最糟糕的时间复杂度是O(1),而在LinkedList中可能就是O(n)了。在ArrayList中增加或者删除某个元素,通常会调用System.arraycopy方法,这是一种极为消耗资源的操作,因此,在频繁的插入或者是删除元素的情况下,LinkedList的性能会更加好一点。

如何复制某个ArrayList到另一个ArrayList中去?

一般情况下,我们都是用浅拷贝来实现,即通过构造函数或者clone方法:

使用clone()方法,比如ArrayList newArray = oldArray.clone();
使用ArrayList构造方法,比如:ArrayList myObject = new ArrayList(myTempObject);

在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?

在ArrayList中增加或者是删除元素,要调用System.arraycopy这种效率很低的操作,如果遇到了需要频繁插入或者是删除的时候,你可以选择其他的Java集合,比如LinkedList。看一下下面的代码:

在ArrayList的某个索引i处添加元素:

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index);

ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

删除ArrayList的某个索引i处的元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

可以看到,添加和删除的代码中都使用到了System.arraycopy这种效率低的操作,在大量的添加和删除过程中并不占优势;但是LinkedList不一样,LinkedList底层维护的是链表,本身就记录的每个节点的前后信息,插入和删除的时候最多只需要修改两个节点的信息,而ArrayList就需要移动修改处往后的元素个数。