Java基础——集合

丰收书屋 2017-07-04

展开全文

1.集合类库

通常，程序总是根据运行时才知道的某些条件去创建新对象，在此之前，不会知道所需对象的数量，甚至不知道确切的类型。为了解决这个普遍的编程问题，需要在任意时刻和任意位置创建任意数量的对象。java实用类库提供了一套相当完整的集合类来解决这个问题。其中基本类型是List、Set、Queue和Map，这些对象被称为集合类。

这里给出一个经常引用的一个类库关系图：

集合的继承类关系图

从图中可以看出，Java集合分为Collection和Map两大种。下面就两大类型进行分别说明：

2. Collection

查看jdk源码看到Collection接口定义了集合分支的基础方法，有查询方法，修改集合方法，批量操作方法和比较与hash方法，这些都是集合的基础方法。其继承接口可以分为以下几类：

List:有序集合，值允许有重复
Set:无需集合，值不允许有重复
Queue:保持先进先出顺序

2.1 List集合: ArrayList&LinkedList

ArrayList底层通过数组实现，数组因为可以通过下标访问成为一个随机访问第n个数效率很高的数据结构，随机访问查询的时间复杂度是O(1)，而删除/增加新的元素到某个位置时，需要一个一个的移动数组中的元素直至适合的位置，所以时间复杂度是O(n)；

LinkedList底层由双向链表实现，在链表中插入元素时，只需要改变插入位置前后结点的结点指向和添加新元素的结点指向即可，时间复杂度是O(1)，在访问元素的时候，无论是随机方位第几位的元素还是查询某个定值时，链表的时间复杂度均为O(n)。

所以，ArrayList适用于随机访问的场景，而LinkedList则适用于频繁随机位置删除和插入的场景。

如果你想学习Java可以来这个群，首先是二二零，中间是一四二，最后是九零六，里面有大量的学习资料可以下载。

2.2 Set集合: HashSet&TreeSet

HashSet：封装了一个 HashMap对象来存储所有的集合元素，所有放入 HashSet中的集合元素实际上由 HashMap的 key来保存，而 HashMap的 value则存储了一个 PRESENT，它是一个静态的 Object对象。 HashSet的绝大部分方法都是通过调用 HashMap的方法来实现的，具体原理在HashMap分析。

TreeSet：TreeSet是基于TreeMap实现的。TreeSet中的元素支持2种排序方式：自然排序或者根据创建TreeSet时提供的 Comparator进行排序。这取决于使用的构造方法，具体原理在TreeMap分析。

2.3 Queue: PriorityQueue

优先级队列，元素可以按照任意的顺序插入，但总是按照排序的顺序进行检索，内部实现的数据结构是堆。堆是一个可以自我调整的二叉树，对树执行添加和删除的时候，可以让最小的元素移动到根，而不用花费时间对元素进行排序。使用的典型实例是任务调度场景。

3. Map

表示键值对，键必须是唯一的，不能对同一个键存放两个值。

3.1 HashMap

HashMap底层实现上是一个“链表散列”的数据结构，即数组和链表的结合体。具体如下图所示：

链表散列

从上图我们可以看出HashMap底层实现还是数组，只是数组的每一项都是一条链。其中数组和链表在jdk源码中体现：

/**The table, resized as necessary.

3.1.1如何插入一个值

HashMap插入一个值包括以下几个步骤：

调用hash计算key的hash值
根据hash值推算出放在数组的位置
找到具体数组某个位置，遍历该位置的Entry链表，比较key值如果相等则直接替换value，如果不同则插入链表的尾部。

可以看出，如果hashCode和hash足够好，尽可能的减少冲突，那么对HashMap的访问等价于对数组的随机方位，如果不够好有大量冲突存在，则退化为对链表的随机方位。

3.1.2再散列rehash

当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

rehash

3.1.3容量参数

可以看出整个再散列过程是比较耗时的，需要将所有老数据重新计算后放到新的散列表中。HashMap维护一个threshold变量，它始终被定义为当前数组总容量和负载因子的乘积，他表示的是HashMap的阈值，当超过该值，HashMap便会扩容。

关于负载因子定义首先看一下HashMap的constructor如下：

public HashMap(int initalCapacity);

其中initalCapacity表示初始化容量，loadFactor表示负载因子一般是介于0和1之间，它决定了HashMap扩容之前，其内部数组的填充度。默认情况下，初始量为16，负载因子为0.75。

负载因子 =元素个数/内部数组总大小

可以看出如果负载因子大于1，一定会存在冲突，元素个数大于数组的容量。

3.1.4如何取一个值

查看jdk源码可以看出从HashMap中获取一个值分为两种情况当key为null的时候单独处理，非null的时候一套处理逻辑。这里也提醒我们HashMap可以存放key为null的键值对。

获取值get

查看获取非null的key的值的具体实现

查找key对应Entry对象

分析查找一个非null的键流程：

调用hash计算key的hash值
根据hash值推算出放在数组的位置
遍历对应位置上的链表找到key相同的Entry对象返回即可，找不到则返回为null

3.2 TreeMap

HashMap和LinkedHashMap底层存储容器都是选择了数组，内容为内部类Entry。但是TreeMap底层通过一颗红黑树来维护，初始化的时候有个root根节点，同时TreeMap不允许key为null。TreeMap本质上就是一棵“红黑树”，而 TreeMap的每个 Entry就是该红黑树的一个节点。

3.2.1红黑树

排序二叉树要么是一棵空二叉树，要么是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
它的左、右子树也分别为排序二叉树。

排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表。

红黑树在原有的排序二叉树增加了如下几个要求：

性质 1：每个节点要么是红色，要么是黑色。
性质 2：根节点永远是黑色的。
性质 3：所有的叶节点都是空节点（即 null），并且是黑色的。
性质 4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点）
性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

上面的性质 3中指定红黑树的每个叶子节点都是空节点，而且并叶子节点都是黑色。但 Java实现的红黑树将使用 null来代表空节点，因此遍历红黑树时将看不到黑色的叶子节点，反而看到每个叶子节点都是红色的。

4. 迭代器（Iterator）

迭代器是一种设计模式，在java里它是一个对象，可以遍历并选择序列中的对象，而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象，因为创建它的代价小。迭代器接口Iterable是Collection类的父接口。它只有一个方法: iterator，方法返回一个代表当前集合对象的泛型<T>迭代器，用于之后的遍历操作。所有的Collection集合对象都实现这个Iterable接口，允许使用foreach进行遍历。

常用Iterator遍历方式

List<Integer> lstint = new ArrayList<Integer>;// Iterator遍历一Iterator<Integer> iterator = lstint.iterator;while (iterator.hasNext){

5. Fail-Fast机制

前面叙述的集合类均不是线程安全的，所以java集合(Collection)规定在使用迭代器的过程中有其他线程修改了同一个集合类，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

注意点：迭代器的快速失败行为无法得到保证，迭代器的快速失败行为应该仅用于检测 bug。