Collection框架

骑猪看日落 2021-09-25 12:18 369阅读 0赞

### Collection框架 ###

*  1 Collection
 *   *   *  1. List
         *   *  1.1 ArrayList
             *  1.2 LinkedList
         *  1.2 Vector和Stack
         *  1.3. Queue按照排队规则来处理容器中的元素。
         *   *  PriorityQueue
 *  2 Map
 *   *   *  2.1 HashMap
         *   *  2.1.1 Java 8之前的HashMap
             *  2.1.2 Java 8提供的HashMap
         *  2.2 TreeMap
         *   *  2.2.1 Java 8之前的LinkedHashMap
             *  2.2.2 Java 8里的LinkedHashMap
         *  2.3 Hashtable
         *  2.4 WeakHashMap
 *  3 Set
 *   *   *  3.1 HashSet
         *  3.2 LinkedHashSet
         *  3.3 TreeSet

# 1 Collection #

![类图描述][65e4bd847ba14385b4a54c4b077c1a0f.png]  
用来存储独立的元素，其中包括List、Set和Queue。

### 1. List ###

List是按照插入的顺序保存元素，它是一种线性的列表结构，它继承自Collection接口，是一种有序集合，List中的元素可以根据索引进行检索、删除或者插入操作。

#### 1.1 ArrayList ####

ArrayList（java.util.ArrayList）是用数组来实现的List，是最常见的列表之一。

它与数组有着同样的特点：

1）随机访问（相对于顺序访问）效率高。  
2）读快写慢，由于写的过程中需要涉及元素的移动，因此写操作的效率比较低。

**数组存储**  
1）所有数据块的内存是连续的。  
2）所有数据块的长度是相同的。

ArrayList的实现原理：  
**（1）父类和接口**  
1）java.util.AbstractList。该抽象类是大部分List的共同父类，它提供了一些基本的方法封装，以及通用的迭代器实现。  
2）java.util.List。列表标准接口，列表是一个有序集合，又被称为序列。该接口对它内部的每一个元素的插入位置都有精确控制，用户可以使用整数索引（index）来查询。  
3）java.util.RandomAccess。这是一个标记性质的随机访问接口，它没有提供任何方法。  
4）java.lang.Cloneable。用于标记可克隆对象，是一个常见接口，没有实现该接口的对象在调用Object.clone()方法时会抛出异常。  
5）java.io.Serializable。序列化标记接口，是一个常见接口，被此接口标记的类可以实现Java序列化和反序列化。该接口没有任何内容，但是Java序列化里有一些默认成员变量和默认方法，会在序列化和反序列化的时候调用到。

**（2）成员变量和常量**  
1）成员变量  
①private transient Object\[\] elementData，elementData是该List的数据域，其中被transient修饰表示这个变量不会被序列化，它提供给Serializable接口使用。  
②private int size，size表示当前List的长度，elementData的length是必然大于或等于size的。  
③protected transient int modCount=0，该成员变量继承自java.util.AbstractList，记录了ArrayList结构性变化的次数。  
在ArrayList的所有涉及结构变化的方法中都会增加modCount的值，这些方法包括：add( )、remove()、addAll( )、removeRange( )及clear( )。  
2）常量  
①private static final long serialVersionUID=8683452581122892189L  
序列化版本UID，根据这个名字能判断出它是提供给序列化接口使用的，该UID是为了维持序列化版本一致性的。  
②private static final int MAX\_ARRAY\_SIZE=Integer.MAX\_VALUE-8  
数组长度的上限，这里设置的是最大整数-8。  
**（3）构造方法**  
①public ArrayList(int initialCapacity)  
initialCapacity表示初始化的elementData的长度  
②public ArrayList()  
elementData的长度默认为10  
③public ArrayList(Colloction < ? extends E > c)  
elementData的长度设置等同为集合的大小，然后再复制集合的所有元素到ArrayList的elementData中  
1）indexof/lastIndexof/contains方法实现。  
indexof方法用于查询指定对象的索引index，实现的方式是对数组顺序遍历，调用指定元素的equals方法来比对，如果查询不到，那么返回-1。  
lastIndexof则于indexof相反，是对数组倒序遍历。  
contains方法直接调用indexof方法，根据返回值是否为-1判断代查找的元素是否存在。  
2）set/add/addAll方法实现。  
set方法的实现很简单，即替换数组里的对应索引处的值。  
add和addAll方法的实现相对复杂一些。首先要检查当前elementData的长度，如果添加后的大小超出elementData的长度，那么需要对elementData的容量进行修正。  
扩展：elementData容量修正的逻辑。

容量修正主要是两个方向：多余和不足。

方法： grow(int)， int参数指定了“本次扩容所允许的最小容量”。  
3）remove/removeAl/retainAll方法实现。  
remove方法有两种重载形式：remove(int)和remove(Object)。  
当形参为int时，表示移除位于指定index的数据，如果移除的不是最后一位，那么会调用System.arrayCopy方法把index之后的数据向前移动一位，该方法的返回值指向被删除的元素。该方法效率比较低。  
当形参为Object时，表示移除指定的对象，该方法会顺序遍历整个数组，找到第一个与之相等对象（使用该对象的equals方法来判断两个对象是否相等），并执行类似remove(int)的操作。该方法的返回值表示删除是否成功。  
removeAll方法用于移除指定集合里的所有元素。 等同 batchRemove(Collection,false)  
retainAll方法是会保留指定集合里存在的元素。等同 batcRemove(Collection,true)  
4）迭代器

使用索引遍历会比迭代器遍历效率更高，迭代器遍历使用java.util.Iterator来实现。  
标准写法：

Iterator<String> iterator=list.iterator();
    while(iterator.hasNext()){ 
        r = iterator.next();
    }

#### 1.2 LinkedList ####

特性: 顺序访问和写快读慢。

**（1）父类和接口**

1）java.util.AbstractSequentialList。该抽象类继承自java.util.AbstractList，提供了顺序访问存储结构，只要类似于LinkedList这样的顺序访问List，都可以继承该类。  
它提供了get\\set\\add\\addAll\\remove等方法的迭代器方式的实现，前提是必须提供对迭代器接口java.util.Iterator的实现。  
2）java.util.Deque。双向队列接口，继承自java.util.Queue。  
Queue的特性是“先进先出”，可以在尾部增加数据，头部获取数据。Deque则可以同时在头尾处完成读写操作。在此基础上，LinekdList还能操作头尾之间的任意结点，所以LinkedList在实现Deque的同时实现了java.util.List。  
3）java.lang.Cloneable、java.util.List和java.lang.Serialiable。  
**（2）成员变量和常量**  
1）transient int size=0; 用于标记序列的大小，因为链表由单个结点组成，除了统计结点个数以外并没有办法获取size，所以提供了一个标记量来做记录，来提高效率。  
2）transient Nodefirst; 链表的头结点。  
3）transient Node last; 链表的尾结点。同时提供头尾结点是为了实现java.util.Deque双向队列接口要求的功能。  
4）常量：private static final long serialVersionUID=876323262645176354L;这个常量提供给Serialiable序列化接口使用。  
**（3）构造方法**  
1）public LinkedList()。 链表无需初始化任何对象  
2）public LinkedList(Collection<? extends E>c)。

**（4）Deque双向队列的实现**

LinkedList是一个在双向队列基础上搭建的双向链表，双向链表的关键方法：  
1）addFirst(E)：在队头添加元素。  
2）addLast(E)：在队尾添加元素。  
3）E removeFirst()：删除队头元素。  
4）E removeLast()：删除队尾元素。  
这些方法通过操作成员变量first和last来实现的。first和last的类型是私有类Node。  
**（5）getFirst/getLast/get方法实现**  
getFirst：取出头  
getLast：取出尾的数据  
get(int)：LinkedList是顺序存储结构，要取到第i个数据，必须顺序遍历到i结点，所以这个方法的时间复杂度为O(n)。  
**（6）set/add/addAll的实现**  
add的本质是在尾部增加一个结点。addAll(Collection)等价于调用add(E)多次。  
set需要遍历查找到指定结点i，并替换之。  
**（7）removeFirst/removeLast/remove方法实现**  
removeFirst与removeLast方法用于移除头尾结点并返回数据，remove则是遍历到指定结点，然后移除它。  
**（8）迭代器**  
ListIteractorlistIterator()方法返回了一个内部类ListItr，该类即是LinkedList迭代器的实现。  
由于LinkedList本身就是顺序结构，该迭代器除了记录nextIndex之外没有做特殊处理。此外LinkedList的迭代器也具备fail-fast特性。

### 1.2 Vector和Stack ###

Stack是栈，Vector是矢量  
**（1）Vector**  
Vector的实现与ArrayList基本一致，底层使用的也是数组，其迭代也具备fail-fast特性，但它和ArrayList还有一些区别，主要体现在以下特性：  
1）Vector是线程安全的，ArrayList不是。这体现在Vector的所有public方法都使用了synchronized关键字。  
2）Vector多了一个成员变量capacityIncrement，用于标明扩容的增量，与ArrayList每次固定扩容50%相比，Vector根据capacityIncrement的数值来扩容，capacityIncrement大于0时，增加等同于capacityIncrement的容量，否则增加一倍容量。capacityIncrement由构造方法Vector(int,int)的第二个形参决定。  
**（2）Stack**  
Stack是Vector的子类，所以它的实现和Vector是一致的，与Vector相比，它多提供了以下方法以表达栈的含义。  
1）E push(E)，入栈，等同在Vector最末位置增加一个元素  
2）E pop()，出栈，移除Vector最末位置元素，并返回。  
3）E peek()，查看栈顶，返回Vector最末位置元素。  
4）empty()，检查栈是否为空。  
5）search(E)，查找元素的栈深，注意，栈顶元素的深度为1，当找不到指定元素时，返回-1。算法为size()-lastIndexof(E)。

### 1.3. Queue按照排队规则来处理容器中的元素。 ###

Queue：一种先入先出（FIFO）的模型

Queue类图  
![队列][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70]

#### PriorityQueue ####

PriorityQueue并不遵循FIFO（先入先出）原则，它会根据队列元素的优先级来调整顺序，优先级最高的元素最先出。

**（1）成员变量**  
PriorityQueue的主要成员变量有：  
transient Object\[\] queue; //存值数组  
private int size = 0; //元素数量  
private final Comparator<? super E> comparator; // 比较器，可以为null，当为null是，E必须实现Comparable  
**（2）heapify方法和最小堆**  
最小堆是一种经过排序的完全二叉树，其中任一非终端结点数值均不大于其左孩子和右孩子结点的值。  
**（3）siftDown(k,x)方法(沉降方法)**  
siftDown方法用于沉降，根据comparator成员变量是否为null，它的执行方式略有不同。  
如果comparator不为null，那么调用comparator进行比较；反之，则把元素视为Comparable进行比较。  
如果元素没有实现Comparable接口，那么会抛出ClassCastException。  
**（4）offer(e)方法**  
PriorityQueue的offer方法用于把数据入队。  
**特性：**  
1）不能存放null数据。  
2）与ArrayList留有扩容余量不同，当size达到数组长度极限时，才执行扩容（grow方法）。  
3）当队列中有数据时，会执行结点上浮（siftUp），把优先级更高的数据放置在队头。

**（5）grow(minCapacity)方法**  
grow方法用于对PriorityQueue进行扩容。  
**功能：**  
①扩容。扩容策略是，如果旧容量小于64，那么增加一倍+2，否则增加50%。  
②溢出校验。如果小于0，那么认为溢出，容量最大能支持到最大正整数。  
**（6）siftUp(k,x)方法**

siftUp方法用于上浮结点。新加入的结点一定在数列末位，为了让数列满足最小堆性质，需要对该结点进行上浮操作。  
**（7）poll()方法**  
poll方法用来检索并移除此队列的头。

# 2 Map #

![类图][8973806d6b599e1cf1b01ad9ef1bdfc0.png]  
用来存储<键，值>对，这个容器允许通过键来查找值。Map是一种由多组key-value（键值对）集合在一起的结构，其中，key值是不能重复的，而value值则无此限定。

其基本接口为java.util.Map，该接口提供了Map结构的关键方法，比如常见的put和get。

### 2.1 HashMap ###

HashMap是最常用的Map结构，Map的本质是键值对。它使用数组来存放这些键值对，键值对与数组下标的对应关系由key值的hashCode来决定，这种类型的数据结构可以称之为哈希桶。

哈希桶能存储\[0,2的31次方-1\]区间的哈希值

#### 2.1.1 Java 8之前的HashMap ####

HashMap的底层实现是数组和链表  
**（1）成员变量**  
transient Entry<K,V> table; //存储数据的核心成员变量  
transient int size; //HashMap键值对数量  
final float loadFactor; //加载因子，用于决定table的扩容量  
table是HashMap的核心成员变量。该数组用于记录HashMap的所有数据，它的每一个下标都对应一条链表。所有哈希冲突的数据，都会被存放到同一条链表中。

Entry<K,V>则是该链表的结点元素。Entry<K,V>包含以下成员变量：

final K key; //存放键值对中的关键字  
V value; //存放键值对中的值  
Entry<K,V> next; //指向下一个结点的引用  
int hash; //key所对应的hashcode  
HashMap的核心实现是一个单向链表数组（Entry<K,V>\[\]table），HashMap的所有方法都是通过操作该数组来完成，HashMap规定了该数组的两个特性：  
1）会在特定的时刻，根据需要来扩容。  
2）其长度始终保持为2的幂次方。

在HashMap中，数据都是以键值对的形式存在的，其键值所对应的hashCode将会作为其在数组里的下标。  
尽可能使键值的hashcode分散，这样可以提高HashMap的查询效率。

**（2）常量**

static final int DEFAULT\_INTIAL\_CAPACITY=16; //默认的初始化容量，必须为2的幂次方  
static final int MAXMUM\_CAPACITY=1<<30; //最大容量，在构造函数指定HashMap容量的时候，用于做比较  
static final int DEFAULT\_LOAD\_FACTOR=0.75f; //默认的加载因子，如果没有构造方法指定，那么loadFactor成员变量就会使用该常量

**（3）put(K,V)方法，用于向HashMap中添加元素**  
执行流程  
![执行流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70 1]  
1）indexFor(int,int)方法，作用是根据hashCode和table长度来计算下标。  
2）hash(Object k)方法，用于计算键值k的hashCode。  
3）存储数据。对应put方法中for循环之后的部分。  
4）addEntry(int,K,V,int)和createEntry(int,K,V,int)，添加键值对。  
该方法参数分别为hash值、键值、值以及下标。由于HashMap的核心数据结构是一个数组，所以一定会涉及数组的扩容。  
5）resize(int)，用于给HashMap扩充容量。  
resize主要完成以下工作：  
①根据新的容量，确定新的扩容阈值（threshold）大小。  
②确定是否要哈希重构（rehash），判断依据是原有的useAltHashing（是否使用替代哈希算法标识）和新产生的这个值，是否一致。不一致时，需要哈希重构。  
③使用新容量来构造新的Entry<K,V>table数组，调用transfer(newTable,rehash)来重新计算当前所有结点转移到新table数组后的下标。  
6）transfer(Entry\[\], boolean)，重新计算转移到新table数组后的Entry下标。

**（4）get方法**  
get方法执行流程  
![执行流程][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70 2]  
**（5）性能优化**  
1）HashMap执行写操作（put）的时候，比较消耗资源的是遍历链表，扩容数组操作。  
2）HashMap执行读操作（get）的时候，比较消耗资源的是遍历链表。

提高HashMap的使用效率：  
1）根据实际的业务需求，测试出合理的loadFactor，否则会始终使用Java建议的0.75。  
2）合理的重写键值对象的hashCode和equals方法。

#### 2.1.2 Java 8提供的HashMap ####

代表链表结点的Entry<K,V>换成了Node<K,V>，Node本身具备链表结点的特性，同时，它还有一个子类TreeNode<K,V>。Java 8里的HashMap使用的是数组+树+链表的结构。  
**（1）put(K,V)方法详解**  
主体流程：  
1）获取key值的hashCode。  
2）调用putVal方法进行存值。  
3）resize方法。resize方法用于重新规划table长度和阈值，如果table长度发生了变化，那么部分数据结点也需要重新进行排列。  
**（2）红黑树**  
1）二叉查找树。  
2）平衡二叉树（AVL树）。  
3）红黑树（R-B树）。  
红黑树也是一种自平衡二叉树，它的实现原理和平衡二叉树类似，但在统计上，它的性能要优于平衡二叉树。

五个特性：  
①结点是红色或者黑色。  
②根结点是黑色。  
③每个叶子结点（NIL结点）为黑色。  
④每个红色结点的两个子结点都是黑色  
⑤从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。‘’  
推论：从根到叶子的最长路径，不超过最短路径的两倍。  
**（3）红黑树在HashMap中的体现**  
1）treeifyBin方法。  
当table容量小于最小建树容量（64）时，则调整table大小（resize）。由于resize的过程可以分解链表，所以无需转化链表为树。  
2）putTreeVal方法用于保存树结点。  
该方法执行二叉树查找，每一次都比较当前结点和待插入结点的大小，如果待插入结点较小，那么在当前结点左子树查找，否则在右子树查找。  
3）balanceInsertion平衡插入方法。  
4）rotateLeft和rotateRight方法。

### 2.2 TreeMap ###

与HashMap组合了数组、链表、红黑树不同，TreeMap是完全由红黑树实现的。  
**（1）成员变量**  
private final Comparator<? super K> comparator; //比较器，决定了结点在树中的分布  
private transient Entry<K,V> root; //树的根节点  
private transient int size = 0; //树中包含的实体数目  
**（2）构造方法**  
TreeMap有四个构造方法：  
1）public TreeMap()。无参构造，初始化comparator=null。  
2）public TreeMap(Comparator<? super K>comparator)。比较器构造，使用外部传入的比较器。  
3）public TreeMap(Map<? extends K, ? extends V>m)。使用传入的Map初始化TreeMap的内容。  
4）public TreeMap(SortedMap<K, ? extends V>m)。使用SortedMap初始化TreeMap内容，同时使用SortedMap的比较器来初始化TreeMap比较器。  
**（3）put方法**  
put的实现  
1）如果TreeMap是空的，那么使用指定数据作为根结点。  
2）反之，如果comparetor不为空，那么使用comparetor来决定插入位置；如果comparetor为空，那么认为key值实现了Comparable，直接调用compareTo方法来决定插入位置；如果key没有实现Comparable，那么抛出ClassCastException。  
3）插入完成后，修复红黑树。

#### 2.2.1 Java 8之前的LinkedHashMap ####

**（1）成员变量**  
private transient Entry<K,V> header; //双向链表的表头  
private final boolean accessOrder; //访问顺序，true为顺序访问，false为逆序  
**（2）createEntry(hash,key,value,index)方法**  
LinkedHashMap的createEntry除了完成HashMap的功能外，还把该链表结点的引用插入到了header环形链表里。

#### 2.2.2 Java 8里的LinkedHashMap ####

**（1）成员变量**  
transient LinkdHashMap.Entry<K,V> head; //双向链表表头，最旧的结点  
transient LinkdHashMap.Entry<K,V> tail; //双向链表表尾，最新的结点  
private final boolean accessOrder; //访问顺序，true为顺序访问，false为逆序  
**（2）linkNodeLast方法**  
**（3）transferLinks方法**

### 2.3 Hashtable ###

Hashtable的put过程：  
1）计算key值的hashCode。  
2）根据hashCode计算下标。  
3）如果存在hashCode和key值完全相等的value，那么替换它并返回。  
4）反之，如果总数据数超出了扩容阈值，那么对数组扩容，并重新计算所有的数据结点的下标。  
5）为新数据创建新结点。  
Hashtable是线程安全的，而HashMap是线程不安全的；此外Hashtable不能存放null作为key值，HashMap会把null key存在下标0位置。

### 2.4 WeakHashMap ###

WeakHashMap是一种种弱引用的HashMap，弱引用指的是WeakHashMap中的key值如果没有外部强引用，那么在垃圾回收的时候，WeakHashMap的对应内容也会被移除掉。

**（1）Java的引用类型**  
Java中与引用的相关的类：  
ReferenceQueue，引用队列  
与某个引用类绑定，当引用死亡后，会进入这个队列。  
**HardReference，强引用**  
任何以类似String str=new String()建立起来的引用，都是强引用。在str指向另一个对象或者null之前，该String对象都不会被GC（Garbage Collector垃圾回收器）回收。  
**WeakReference，弱引用**  
可以通过java.lang.ref.WeakReference来建立弱引用，当GC要求回收对象时，它不会阻止对象被回收，也就是说即使有弱引用存在，该对象也会立刻被回收。（弱引用的对象，如果没有被强引用，那么在垃圾回收后，引用对象会不可达。）  
**SoftReference，软引用**  
可以通过java.lang.ref.SoftReference来建立，与弱引用类似，当GC要求回收时，它不会阻止对象被回收，但不同的是该回收过程会被延迟，必须要等到JVM heap内存不够用，接近产生OutOfMemory错误时，才会被回收。  
**PhantomReference，虚引用**  
可以通过java.lang.ref.PhantomPeference来建立，这种类型的引用很特别，在大多数时间里，无法通过它拿到其引用的对象，但是，当这个对象死亡的时候，该引用还是会进入ReferenceQueue队列。（虚引用非常弱，以至于它自己也找不到自己的引用内容。）  
**（2）WeakHashMap的实现方式**  
WeakHashMap利用了ReferenceQueue和WeakReference来实现它的核心功能：当key值没有强引用的时候，会从WeakHashMap里移除。

# 3 Set #

![类图][ff52775d4e079c1b889e90c4078eeffc.png]  
Set是一个接口，这个接口约定了在其中的数据是不能重复的，它有许多不同的实现类。

### 3.1 HashSet ###

①HashSet中不会有重复的元素。  
②HashSet中最多只允许有一个null。

特性：  
①HashSet不是线程安全的，如果想使用线程安全的Set，那么可以使用CopyOnWrite ArraySet、Collections.synchronizedSet(Set set)、ConcurrentSkipListSet和Collections.newSetFromMap(NewConcurrentHashMap)。  
②HashSet不会维护数据插入的顺序，如果想维护插入顺序，那么可以使用LinkedHashSet。  
③HashSet也不会对数据进行排序，如果想对数据进行排序，那么可以使用TreeSet。

### 3.2 LinkedHashSet ###

LinkedHashSet是HashSet的扩展，HashSet并不维护数据的顺序，而LinkedHashSet维护了数据插入的顺序。HashSet在内部是使用HashMap来实现的，而LinkedHashSet内部通过LinkedHashMap来实现。

### 3.3 TreeSet ###

TreeSet中的数据是有序的，它默认使用的是数据的自然顺序，当然在创建TreeSet的时候也可以指定Comparator来对数据进行排序。

[65e4bd847ba14385b4a54c4b077c1a0f.png]: /images/20210923/011f9611a96b4938955a2be7d0182a38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70]: /images/20210923/2a68728e120a4b5494cfb87c9430018f.png
[8973806d6b599e1cf1b01ad9ef1bdfc0.png]: /images/20210923/108f0aee35c5473183dac7e302ff7492.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70 1]: /images/20210923/9061b4bd602c434baf0c4e5fc61babc0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x4dzk4MzUyMA_size_16_color_FFFFFF_t_70 2]: /images/20210923/534e6a45ef5f47c38c6d33fe4c23c084.png
[ff52775d4e079c1b889e90c4078eeffc.png]: /images/20210923/7b4a249398a74f53b7021469227a832b.png