7.1 集合的框架体系（这两张图很重要）

图片.png
图片.png

7.2 Collection接口和常用方法

7.2.1 Collection接口实现类的特点

  1. Collection实现子类可以存放多个元素，每个元素可以是Object
  2. 部分Collection的实现类可以存放重复元素，部分不可以
  3. 部分Collection的实现类是有序的，部分无序
  4. Collection没有直接的实现类，而是通过它的子接口List和Set实现的

常用方法如下：

  1. - add: 添加单个元素
  2. - remove: 删除指定元素
  3. - contains: 查找元素是否存在
  4. - size: 获取元素个数
  5. - isEmpty: 判空
  6. - clear: 清空
  7. - addAll: 添加多个元素
  8. - containsAll: 查找多个元素是否都存在
  9. - removeAll: 删除多个元素

7.2.2 使用迭代器遍历Collection

Collection接口中有个方法iterator()，该方法返回一个Iterator接口对象，该对象称为迭代器。

迭代器仅用于遍历集合，并不存储实际数据。Iterator接口中存在两个方法，能很好的解释其执行原理：

  • hasNext()：判断是否存在下一个元素
  • next()：指针下移，并将下移后指向的对象返回

以下是使用迭代器对集合进行遍历的示例，其中list为被迭代对象：

  1. Iterator iterator = list.iterator();
  2. while (iterator.hasNext()) {  // 判空十分重要，必须要有，否则可能造成异常
  3.     Object obj = iterator.next();
  4.     System.out.println("dog=" + obj);
  5. }

7.2.3使用增强for循环遍历Collection

增强for相当于迭代器的简化版，之所以这么说是因为在断点调试时会发现，其底层还是走的迭代器的遍历方法。以下为使用增强for循环遍历集合的示例：

  1. for (Object obj : list) {
  2.     System.out.println("dog=" + obj);
  3. }

7.3 List接口和常用方法

7.3.1 List接口基本介绍

  1. List集合类中元素有序
  2. List集合支持索引访问
  3. 实现List接口的常用子类有：ArrayList、LinkedList、Vector

7.3.2 List接口的常用方法

  1. - void add(int index, Object ele): 在index位置插入ele元素
  2. - boolean addAll(int index, Collection eles): 从index位置开始将 eles 中的所有元素添加进来
  3. - Object get(int index): 获取指定 index 位置的元素
  4. - int indexOf(Object obj): 返回 obj 在集合中首次出现的位置
  5. - int lastIndexOf(Object obj): 返回 obj 在当前集合中末次出现的位置
  6. - Object remove(int index): 移除指定 index 位置的元素，并返回此元素
  7. - Object set(int index, Object ele): 设置指定 index 位置的元素为 ele , 相当于是替换
  8. - List subList(int fromIndex, int toIndex): 返回从 fromIndex 到 toIndex 位置的子集合

7.3.3 List的三种遍历方式

  • 迭代器遍历
  • 增强for循环
  • 普通for循环

7.4 ArrayList底层结构与源码分析

7.4.1 ArrayList注意事项

  • 允许加入所有元素，包括null
  • 底层使用数组进行存储
  • 和Vector很类似，但ArrayList是线程不安全的，也正因如此，执行效率高于Vector

7.4.2 ArrayList底层操作机制源码分析（重难点）

ArrayList中维护了一个Object类型的数组elementData

  • 创建ArrayList对象时，若使用无参构造器，则初始化elementData容量为0，第一次添加元素elementData扩容为10，如果需要再次扩容，则扩容为elementData的1.5倍
  • 创建ArrayList对象时，若使用有参构造器，则初始化elementData容量为给定参数值，若后续需要扩容，则扩容为elementData的1.5倍

图片.png图片.png

7.5 Vector底层结构与源码分析

7.5.1 Vector基本介绍

  • 底层也是对象数组
  • 是线程安全的，方法都带有synchronized
  • 如果开发过程中有多线程操作的场景，建议使用Vector

7.5.2 源码分析

当使用无参构造器创建Vector对象时，其实相当于调用了参数为10的有参构造器。
截屏2021-06-09 上午11.17.42.png有参构造器的源码如下，实际调用了下图上方的构造方法，其中第一个参数为传入的参数，第二个参数如果不指定，则会默认传0，它代表的含义为每次增长的容量。

该构造器会创建一个容量大小为initialCapacity的Object类型的数组，并赋给当前Vector的elementData字段，此外对capacityIncrement进行赋值。
截屏2021-06-09 上午11.23.47.png为了了解其扩容机制，深入到add方法探查。和Arraylist大差不差，首先对操作次数进+1，之后的ensureCapacityHelper方法是重点，可以看出如果其顺利执行完，就会进行添加操作，大概率该方法的作用就是确保容量是满足使用要求的。其中的elementCount = elementData.length，获取当前集合的长度。
截屏2021-06-09 上午11.34.38.png所以得继续深入ensureCapacityHelper，继续看该方法的源码，这里的minCapacity参数为当前集合长度+1的值，很好理解，就是在当前集合再添加一个元素所需要的最小容量大小。如果所需要的最小容量大小比当前集合的长度还大，说明容量不符合使用要求了，接着进入grow方法进行实际扩容。
截屏2021-06-09 上午11.45.50.png扩容逻辑如下代码所示，新的容量大小在没有传capacityIncrement时，会被扩容为之前的两倍，之后会对新容量大小与所需的最小容量大小进行比较，如果新容量大小仍然不符合使用要求，则会将容量直接扩为所需的最小容量大小。接下来所做的处理与ArrayList无异，对原来的数组进行复制产生新数组，新数组的容量大小为扩容后的值。
截屏2021-06-09 上午11.45.58.png

7.6 LinkedList底层结构

7.6.1 LinkedList基本介绍

  • 底层实现了双向链表和双端队列的特点
  • 可以添加任意元素（可重复），包括null
  • 其添加和删除元素的效率比数组高
  • 线程不安全

7.6.2 LinkedList底层操作机制

  • 底层维护了一个双向链表
  • 底层维护了两个属性first和last，分别指向头尾节点
  • 每个节点（Node）内部维护了三个属性prev、item、next

以下代码可模拟一个简单的双向链表并对链表进行遍历：

  1. public class LinkedList_ {
  3.     @SuppressWarnings({"all"})
  4.     public static void main(String[] args) {
  5.         Node jack = new Node("jack");
  6.         Node tom = new Node("tom");
  7.         Node hsp = new Node("hsp");
  9.         // jack -> tom -> hsp
  10.         jack.next = tom;
  11.         tom.next = hsp;
  12.         // hsp -> tom -> jack
  13.         hsp.prev = tom;
  14.         tom.prev = jack;
  16.         Node first = jack;  // 头指针，指向链表头
  17.         Node last = hsp;  // 尾指针，指向链表尾
  19.         // 遍历LinkedList
  20.         System.out.println("从头到尾进行遍历:");
  21.         while (true) {
  22.             if (first == null) {
  23.                 break;
  24.             }
  25.             System.out.println(first);
  26.             first = first.next;
  27.         }
  29.         System.out.println(("从尾到头进行遍历:"));
  30.         while (true) {
  31.             if (last == null) {
  32.                 break;
  33.             }
  34.             System.out.println(last);
  35.             last = last.prev;
  36.         }
  37.     }
  39. class Node {
  41.     public Object item;
  42.     public Node next;
  43.     public Node prev;
  45.     public Node(Object name) {
  46.         this.item = name;
  47.     }
  49.     @Override
  50.     public String toString() {
  51.         return "Node name=" + item;
  52.     }
  53. }

在链表中插入一个元素是很容易实现且高效的，比如在tom和hsp间插入一个节点smith：

Node smith = new Node("smith");
smith.next = hsp;
smith.prev = tom;
hsp.prev = smith;
tom.next = smith;

7.6.3 源码分析

LinkedList提供了无参和有参两种构造器，无参构造器什么也没做，first和last将初始化为null。有参构造器需要传入一个Collection对象，构造器中调用了addAll，将传入集合的元素全部加入链表中。截屏2021-06-09 下午5.23.38.png插入元素使用add方法，add方法中又调用了linkLast，源码如下：截屏2021-06-09 下午5.26.14.png很容易理解，如果是首次插入元素，此时first和last都是null，则会将first指向新节点；否则就让链表中的最后一个节点指向新节点，新节点的prev指向之前链表中的最后一个节点。

删除元素使用remove方法，该方法的参数为索引值（只支持索引删除），所以该方法首先会判断传入的索引值是否存在，如果存在就去解除该索引节点与链表的关系。源码如下（图太大了直接粘出来…）：

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 如果要删除的是首节点，则让first指向它的下一个节点；否则让它的前一个节点指向它的后一个节点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果要删除的是最后一个节点，则让last指向它的前一个节点；否则让它的后一个节点指向它的前一个节点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

7.6.4 List实现子类间的选择

  • 如果改查操作多，使用ArrayList
  • 如果增删操作多，选择LinkedList
  • 使用数组还是链表结构则取决于业务需求

7.7 Set接口

7.7.1 Set接口基本介绍

  • Set不包含重复的元素，最多只能存放一个null值
  • 无序的
  • 它和数学意义上的集合是一样的
  • 重要实现类包括
    • HashSet
    • TreeSet
    • LinkedHashSet

7.7.2 Set接口的常用方法

- boolean add(E e): 如果set中尚未包含指定元素，则添加指定元素。
- void clear(): 从此set中移除所有的元素
- boolean contains(Object o): 如果此 set包含指定元素 ，则返回true
- boolean remove(Object o): 如果指定元素存在于此set中，则将其移除
- int size(): 返回此set中的元素的数量（set的容量）

对Set实现类进行遍历有两种方式：

  • 迭代器
  • 增强for循环

不能使用普通for循环遍历，因为Set实现类的底层不是数组，并不支持索引访问。

7.7.3 HashSet的扩容机制

HashSet的底层是HashMap，而HashMap是数组+链表+红黑树的结构。下面先给出HashSet添加元素的步骤：

  1. 计算元素的hashcode，并根据该code值转化为数组的索引值
  2. 找到存储数据表table，看第一步计算出的索引位置是否有元素
    1. 如果没有元素，则直接插入
    2. 如果存在其他元素，则调用equals与其他元素进行比较，如果返回true，则放弃插入；如果都不一样，则插在最后

在Java 8中，如果一条链表的元素个数达到TREEIFY_THRESHOLD（默认为8），且table的大小≥MIN_TREEIFY_CAPACITY，则会将链表转化为红黑树（树化）。

7.7.4 HashSet源码分析

由于该集合源码比较复杂，不在这里做整理了，移步查看HashSet源码分析。

HashSet的扩容和树化机制详解步骤：

  1. 第一次添加时，table数组扩容到16，临界值（threshold）为16*0.75（加载因子）
  2. 如果table到了临界值12，就会扩容为原来的2倍即32，新的临界值也会随之而变
  3. 在Java 8中，如果一条链表的元素个数达到8，且table.size≥64时，才会进行树化，否则先扩容table

7.7.5 LinkedHashSet基本介绍

  1. LinkedHashSet是HashSet的子类
  2. 其底层是一个LinkedHashMap，维护了一个数组+双向链表
  3. 能够保证插入顺序和读取顺序相同
  4. 不允许插入相同的元素

7.7.6 TreeSet介绍

TreeSet实现了Set接口，它和HashSet的区别在于其可以对加入的元素进行排序。实现排序时，需要向构造器提供一个Comparator对象。

之所以能够排序是因为TreeSet的底层为TreeMap，其数据结构为红黑树。

7.8 Map接口

7.8.1 Map接口实现类的特点

  1. Map用来保存具有映射关系的数据：key-value
  2. Map中的key和value可以是任何引用类型的数据，会封装到HashMap$Node对象中
  3. Map中的key不能重复，value可以重复
  4. Map中的key和value均可以为null，但是key为null只允许出现一次
  5. 常用String类作为Map的key

因为类Node实现了接口Entry，所以说key-value存放在Node节点或者Entry节点都是ok的。

截屏2021-06-14 上午1.15.25.png

7.8.2 Map接口的常用方法

- V put: 存放key-value对
    当重复put相同key值得元素时，后面的put方法中的value值会替换前面相同key的value
- V remove: 根据key删除元素
- V get: 根据key获取元素
- int size
- boolean isEmpty
- boolean containsKey
- void clear

7.8.3 Map接口遍历方法

  • 通过keySet()进行遍历 ```java Set keySet = map.keySet(); // set有两种遍历方式 // 1. 增强for循环 for (Object key : keySet) { System.out.println(map.get(key)); } System.out.println(“————————“);

// 2. 迭代器 Iterator iterator = keySet.iterator(); while (iterator.hasNext()) { Object key = iterator.next(); System.out.println(map.get(key)); }


- 通过`values()`进行遍历
```java
Collection values = map.values();
// 有两种遍历方式(增强for、迭代器)
for (Object value : values) {
    System.out.println(value);
}
System.out.println("-----------------");
Iterator iterator1 = values.iterator();
while(iterator1.hasNext()) {
    Object value = iterator1.next();
    System.out.println(value);
}
  • 通过entrySet()进行遍历
    Set entrySet = map.entrySet();
for (Object entry : entrySet) {
  Map.Entry m = (Map.Entry) entry;
  System.out.println(m.getKey() + "-" + m.getValue());
}
System.out.println("-----------------");
Iterator iterator2 = entrySet.iterator();
while (iterator2.hasNext()) {
  Object entry = iterator2.next();
  Map.Entry m = (Map.Entry) entry;
  System.out.println(m.getKey() + "-" + m.getValue());
}

7.8.4 HashMap特性总结

图片.png

7.8.5 HashMap底层机制（见HashSet）

图片.png

7.8.6 Hashtable基本介绍

  1. Hashtable存储的也是key-value对，底层也是一个Entry数组
  2. 键和值均不能为null
  3. 相比起HashMap来说，是线程安全的
  4. 方法和HashMap基本相同

Hashtable的扩容机制和HashMap不同，核心代码如下。当使用无参构造器实例化Hashmap时，初始化其大小为11，可以看出当元素个数超过阈值后，会扩容会原来容量的2倍 + 1。（追源码发现并未进行树化，即底层仅为数组+链表的结构，未涉及到红黑树）。

int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
    if (oldCapacity == MAX_ARRAY_SIZE)
        // Keep running with MAX_ARRAY_SIZE buckets
        return;
    newCapacity = MAX_ARRAY_SIZE;
}

7.8.7 Hashtable与HashMap的对比

图片.png

7.8.8 Properties

  1. Properties是Hashtable的子类，并且实现了Map接口
  2. 使用特点与Hashtable类似
  3. 它还可以用于读取xxx.properties配置文件 （见io章节）

其基本方法如下：

- put: 增加与修改
- get: 获取元素
- remove: 删除元素

7.9 如何选择集合类型

图片.png

7.10 Collections工具类

7.10.1 工具类的介绍

提供了一系列处理Set、List、Map等集合的静态方法。

7.10.2 常用方法介绍

- reverse(List)
- shuffle(List)
- sort(List)
- sort(List, Comparator)
- swap(List, int, int)
- Object max(Collection)
- Object max(Collection, Comparator)
- Object min(Collection)
- Object min(Collection, Comparator)
- int frequency(Collection, Object)
- void copy(List dest, List src)
- boolean replaceAll(List list, Object oldVal, Object newVal)