Java 集合框架

lkj 4/8/2022 JavaSE

# 前言

对于 Java 集合的学习，个人觉得除了学习集合本身的知识点（常见的增、删、改、查操作）之外，更重要的是学习面向对象编程思想以及所使用到的数据结构与算法，如

面向对象编程四大特性
1. 封装
2. 继承
3. 多态
4. 抽象
基于接口而非实现编程
数据结构
1. 数组
2. 链表
  1. 单链表
  2. 双向链表
  3. 循环链表
3. 哈希
4. 红黑树

# 理解集合

集合，也被称作为容器，其实个人觉得称为容器可能更合适点，主要原因之一就是在集合中分为 Collection 和 Map 两大类，而其中的 Collection 中文意思又为集合，为了避免冲突，所以 Java 中的集合称为容器可能更合适点

集合的本质就是一个用于存储多个数据的容器

既然如此，数组不就是用于存储多个数据的吗？那为什么还会出现集合呢？直接使用数组不就够了吗？主要原因是数组有以下几点不足：

数组长度开始时必须指定，一旦指定，不能更改
数组中保存的元素必须是同一种数据类型
在数组中进行元素的增加、删除操作比较麻烦（涉及到扩容机制）

那集合相对于数组又有哪些优点呢：

可以动态保存任意多个对象，使用比较简单
提供一些列操作对象的方法：add、remove、set 等

# 集合体系结构

根据集合中存储的数据结构不同（单个元素对象和键值对元素对象）可分为两类：Collection 和 Map

Collection 中存储的元素为单个对象
Map 中存储的元素为键值对

# 迭代器

更多迭代器相关内容请参考：Java Iterator (opens new window)

建议从设计模式之迭代器模式的角度来理解迭代器

什么是迭代器
1. 一个拥有 hasNext() 和 next() 两个方法的类
迭代器原理是什么
Java 中的迭代器
1. 专门用于迭代 Java Collection 接口的一个工具类，采用迭代器模式实现
2. 你可以通过 List，Set 提供的 iterator() 方法来获取这个迭代器实例，但请注意 Iterator 并不属于 Collection API 的一部分

# 遍历Collection

Java 中的迭代器就是用来遍历 Collection 接口实现类的

Iterator（迭代器）方式

迭代器只能由于遍历 Collection API，看上面的继承关系图就明白了
增强 for
1. 增强 for 既可以遍历集合，也可以遍历数组
2. 增强 for 只是一个语法糖，底层使用的还是迭代器
普通 for
1. 该方式只能用于 List 接口实现类，因为它采用了 get(int index) API，而该 API 只有 List 接口中声明了

ArrayList<Dog> list = new ArrayList<>();
list.add(new Dog("xiaohong", 12));
list.add(new Dog("xiaoming", 19));
list.add(new Dog("xiaowang", 22));
// 遍历 Collection 的通用方式：使用迭代器

// 获取迭代器对象（原始方式）
Iterator<Dog> iterator = list.iterator();
while (iterator.hasNext()){
  Dog dog = iterator.next();
  System.out.println(dog);
}

// 增强 for
for(Dog dog: list){
  System.out.println(dog);
}

// 普通 for
for (int i = 0; i < list.size(); i++) {
  Dog dog = list.get(i);
  System.out.println(dog);
}

# List接口实现类

List 接口的特点

元素有序（添加和取出顺序有序），且可重复
每个元素都有其对应的索引，即支持索引
1. 支持 get(int index) 方法
2. 所以可以使用普通 for 循环来遍历 List 接口实现类

# ArrayList 底层机制

注意：JDK 版本的不同，其扩容机制也会有所差别，以下源码分析基于 JDK 1.8

ArrayList 中维护了一个 Object 类型的数组 elementData，也就是说 ArrayList 底层实现使用的是数组
ArrayList 有三个构造函数，分别为 ArrayList()、ArrayList(int initialCapacity)、ArrayList(Collection<? extends E> c)
1. 当使用第一个构造函数（无参构造函数）创建 ArrayList 对象时，初始 elementData 的容量为 0，第一次添加时，则扩容 elementData 为 10，如需再次扩容，则扩容为 elementData 的 1.5 倍
2. 如使用指定大小的构造器，则初始 elementData 容量为指定大小，如需要扩容，则直接扩容为 elementData 的 1.5 倍

ArrayList list = new ArrayList(); // debug 进行源码分析
for (int i = 0; i < 10; i++) {
  list.add(i);
}

for (int i = 10; i < 15; i++) {
  list.add(i);
}

list.add(100);
list.add(200);

# Vector底层结构与源码分析

Vector 底层也维护了一个 Object 类型的数组 elementData，也就是说 Vector 底层实现使用的也是数组
Vector 相比 ArrayList 是线程同步的，即线程安全
1. Vector 类的操作方法会带有 synchronized
2. 在开发中需要线程安全时，考虑使用 Vector

// Vector vector1 = new Vector(); // debug 进行源码分析
// Vector vector1 = new Vector(10);
Vector vector = new Vector(8, 2);
for (int i = 0; i < 10; i++) {
  vector.add(i);
}
vector.add(100);

Vector 与 ArrayList 的比较

	底层结构	版本	线程安全（同步）效率	扩容机制
`ArrayList`	可变数组：`Object[] elementData`	jdk1.2	不安全，效率高	1、如果是有参构造（指定初始容量），则第一次的容量为指定的初始容量，之后按自身容量大小的 1.5 倍进行扩容 2、如果是无参构造（未指定初始容量），则第一次的容量为 10 ，之后按自身容量大小的 1.5 倍进行扩容
`Vector`	可变数组：`Object[] elementData`	jdk1.0	安全，效率低	1、如果是无参构造（未指定初始容量），则第一次容量为 10，之后按自身容量大小的 2 倍进行扩容 2、如果指定初始容量不指定扩容大小，则第一次容量为指定的初始容量，之后按自身容量大小的 2 倍进行扩容 3、如果指定初始容量和扩容大小，则第一次容量为指定的初始容量，之后按指定的扩容大小进行扩容

# LinkedList底层结构与源码分析

LinkedList 底层维护了一个双向链表

LinkedList 中维护了两个属性：first、last，它们分别指向头节点和尾节点

每个节点（Node 对象）里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个节点，next 指向后一个节点、item 指向当前节点的数据

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

由于 LinkedList 底层是由链表实现而非数组，所以它的「添加」和「删除」操作的效率相比于 ArrayList 会更高

LinkedList linkedList = new LinkedList(); // debug 源码分析
for (int i = 0; i < 3; i++) {
  linkedList.add(i+1);
}
linkedList.remove();
linkedList.remove();
linkedList.remove();

ArrayList 与 LinkedList 的比较

	底层结构	增删的效率	改查效率
`ArrayList`	可变数组	较低，因为有数组扩容	较高
`LinkedList`	双向链表	较高，通过链表追加	较低

# Set接口实现类

Set 接口的特点

元素无序，即添加元素和取出元素的顺序不一致
没有索引，所以不能使用索引的方式进行遍历
不允许重复元素

# HashSet底层机制

本质是哈希函数+哈希碰撞的知识，可参考 21 | 哈希算法（上）：如何防止数据库中的用户信息被脱库？-极客时间 (opens new window)

哈希的定义

解决哈希碰撞的方式
开放寻址法

链表法

HashSet 的底层是 HashMap，可看如下源码

public HashSet() {
    // 本质使用的是 HashMap
    map = new HashMap<>();
}

// 添加的每个元素会被封装成 Node<K,V> 对象
// K 为你添加的那个元素，
// V 为一个固定值 PRESENT，
// hash 为根据 key（添加的那个元素）得到的一个哈希值，
// next 指向下一个 Node<K,V> 节点，因为可能产生哈希碰撞，这里采用链表法解决
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

# 数组扩容机制

第一次添加元素时 table 数组会扩容到 $16$ ，临界值为 $threshold = newCap * loadFactor = 16 * 0.75 = 12$

之后你继续添加元素，当你添加的元素个数达到临界值 $12$ （不是 table 数组容量哦），table 数组会继续扩容到 $16 * 2 = 32$ ，新的临界值变为 $32*0.75=24$ ，以此类推。

请注意：添加的元素既可以充当数组元素，也可以充当链表节点，也就是说，只要你添加元素成功时，当前元素个数都会加 $1$

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 调用 resize 函数进行扩容
final Node<K,V>[] resize() {
    newCap = DEFAULT_INITIAL_CAPACITY; // 第一次添加元素时 table 数组会扩容到 16
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 第一次添加元素时，临界值为 12
}

# 链表转换成红黑树机制

在 Java8 中如果一条链表的元素个数达到了 TREEIFY_THRESHOLD（默认值为 $8$ ），并且 table 的大小 >= MIN_IFY_CAPACITY（默认为 $64$ ），就会进行树化（红黑树），否则继续数组的扩容，直到数组元素个数达到 $64$ ，再对该链表进行树化

# 总结

HashSet 的底层是 HashMap，HashMap 的底层是数组+链表+红黑树

// HashSet 构造器内部调用的是 HashMap 构造器
public HashSet() {
    map = new HashMap<>();
}

添加一个元素时，会通过一个算法先得到该元素的 hash 值，再将 hash 值转换成索引值

// 根据 key 得到 hash 值的函数代码
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 根据 hash 值得到 table 索引值代码
n = table.length;
i = (n - 1) & hash

// 根据索引值拿到 table 数组中的元素
p = table[i]

找到存储数据表 table（就是一个数组啦），看这个索引值对应的位置是否已经存在元素

如果索引位置没有元素，直接加入

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

如果索引位置有元素，先判断该元素是树节点还是链表节点
1. 若是树节点，进行树相关的操作
```
else if (p instanceof TreeNode)
  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
```

若是链表节点，则以该元素作为链表的头节点进行遍历，每遍历到一个节点，与要添加的元素进行比较判断是否相同

如果相同，放弃添加；
如果不同，继续遍历下一个节点，直到所有节点遍历完了后都没有相同的，则添加到链表的尾部

// 判断元素是否相同的代码
e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))

for (int binCount = 0; ; ++binCount) { // p 刚开始指向链表的头节点
  if ((e = p.next) == null) { // 已达链表尾部，直接添加
      p.next = newNode(hash, key, value, null);
      // 添加到链表尾部之后判断链表节点个数是否已经达到 8 个了
      // 如果达到了，则进行树化，否则直接退出
      // 实际上，在 treeifyBin 函数内部还会判断数组大小是否超过了 64，只有超过了 64 才会进行真正的树化
      if (binCount >= TREEIFY_THRESHOLD - 1) 
          treeifyBin(tab, hash);
      break;
  }
  // 判断要添加的元素与当前节点是否相同
  // 若相同直接退出，不同则进入下一个节点的判断
  if (e.hash == hash &&
      ((k = e.key) == key || (key != null && key.equals(k))))
      break;
  p = e;
}

在 Java8 中，如果一条链表的元素个数超过 TREEIFY_THRESHOLD（默认值为 $8$ ），并且 table 的大小 >= MIN_IFY_CAPACITY（默认为 $64$ ），就会进行树化（转成红黑树）

// debug 源码
HashSet<Object> hashSet = new HashSet<>(); // 这里打断点可查看 HashSet 的底层是 HashMap
hashSet.add("java"); // 这里打断点可查看索引值的生成
hashSet.add("php");
hashSet.add("java"); // 这里打断点可查看产生哈希碰撞之后采用的是链表法

HashSet hashSet = new HashSet();
Person person1 = new Person(1001, "AA");
Person person2 = new Person(1002, "BB");
hashSet.add(person1);
hashSet.add(person2);

person1.name = "CC";
hashSet.remove(person1);
System.out.println(hashSet);// 输出结果？

hashSet.add(new Person(1001, "CC"));
System.out.println(hashSet);// 输出结果？
hashSet.add(new Person(1001, "AA"));
System.out.println(hashSet);// 输出结果？

class Person {
    public int id;
    public String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return id == person.id && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

# LinkedHashSet底层机制

LinkedHashSet 是 HashSet 的子类，底层维护了一个数组+双向链表
LinkedHashSet 底层是 LinkedHashMap，而 LinkedHashMap 又是 HashMap 的子类
链表的每个节点都有一个 before 和 after 属性，这样可以形成双向链表
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表来维护元素的次序（图），这使得元素看起来是以插入顺序保存的（表现形式上：插入的顺序和遍历的顺序一致）
LinkedHashSet 不允许添加重复元素，毕竟是实现了 Set 接口的

LinkedHashSet<Object> hashSet = new LinkedHashSet<>(); // debug 源码分析

hashSet.add("hello");
hashSet.add("world");
hashSet.add(new Dog("jack"));
hashSet.add(new Dog("jack"));
hashSet.add("mary");

class Dog{
  private String name;

  public Dog(String name) {
    this.name = name;
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }


  @Override
  public int hashCode() {
    return Objects.hash(name);
  }
}

# TreeSet 底层机制

核心点：排序

底层源码使用的还是 TreeMap，类似于 Set 底层源码用的是 Map

关于排序内容，必须掌握 Comparator 接口，该接口中有一个 compare 方法，根据实际情况来实现该方法进而定制自己的排序规则（字符串长度、年龄大小等）

TreeSet treeSet = new TreeSet();
treeSet.add(new Person());// 抛出 ClassCastException 异常

class Person(){}

分析上述代码抛出 ClassCastException 异常的原因：

在 TreeSet 添加元素时会先进行 compare 比较，compare 方法内部会将添加的元素向上转型为 Comparable 接口类型，Comparable 接口中有一个 compareTo 方法，由于你添加的元素 new Person() 并未实现 Comparable 接口，所以抛出该错误。compare 方法如下，第一次添加时 k1 == k2 == new Person()

final int compare(Object k1, Object k2) {
  	// (Comparable<? super K>)k1 由于此时的 k1 为 new Person(),而 Person 并未实现 Comparable 接口，所以会抛出错误
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

# Map 接口实现类

Map 接口的特点

其实 Set 接口实现类中底层存储的也是 key-value 类型的键值对数据，只不过 key 是你添加的数据，value 却是一个固定的 PRESENT = new Object();

Map 接口和 Collection 接口并列存在。用于保存具有映射关系的数据：key-value
Map 中的 key 和 value 可以是任何引用类型的数据，但在实际开发中常用 String 类型作为 Map 中的 key
当添加具有相同 key 的 key-value 键值对数据时，根据添加的顺序进行覆盖
Map 中的 key 不允许重复，原因和 HashSet 一样，前面分析过源码，但是 value 可以重复。即，不同的 key 可以有相同的 value
底层源码中会根据你传入的 key 计算一个 hash 值，根据这个 hash 值进行数据的添加与搜索。而计算 hash 值的过程中会应用到 key 的 hashCode，所以，我们可以重写 key 的 hashCode 来对「重复元素」进行深刻的理解。

// 具体的 hash 计算源代码
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

理解 entrySet

在 HashMap 源码中有这样一个变量 entrySet，其定义为 transient Set<Map.Entry<K,V>> entrySet;。该变量是一个 Set 集合，集合中存储的每一个元素类型是 Entry
entrySet 的出现主要是为了方便对元素的遍历，因为当你转为 Set 类型就可以使用迭代器进行遍历了。
添加进 Map 的每一个元素都会变成一个 Node 数据类型（也就是 HashMap$Node 类型）。由于 static class Node<K,V> implements Map.Entry<K,V> 的定义，Node 实现了 Entry，所以 entrySet 集合中每一个数据类型为 Entry 的元素就是 Node 元素。

三个遍历的常用方法

keySet()
values()
entrySet()

# HashMap 底层机制

参考 HashSet 底层机制

# Hashtable 底层机制

和 HashMap 的底层基本一致，但有些许的不同

底层会有一个 Hashtable$Entry[] 数组
其中元素类型为 Entry，private static class Entry<K,V> implements Map.Entry<K,V>，Entry 类型实现了 Map.Entry 接口
数组扩容机制
1. 初始化大小为 $11$ ，临界值为 $11*0.75 = 8$ 。
2. 当数组元素个数达到临界值时会进行扩容，扩容机制为：int newCapacity = (oldCapacity << 1) + 1;，即 当前数组容量乘2加1 作为新的数组容量，新的临界值为：新的数组容量乘以 0.75

HashTable 的特点

存放的元素也是键值对，但是键和值都不能为 null，否则会抛出 NullPointerException
HashTable 的使用方法基本和 HashMap 一样
HashTable 是线程安全的（synchronized），HashMap 是线程不安全的

# TreeMap 底层机制

核心点：按键排序

参考 TreeSet 底层机制

# Properties

Properties 类继承自 HashTable 类，并且实现了 Map 接口，也是使用一种键值对的形式来保存数据的。
它的使用特点和 HashTable 类似
1. Properties 还可用于从 xxx.properties 文件中加载数据到 Properties 类对象中进行读取和修改
实际开发中，xxx.propeties 文件通常为配置文件

# 源码总结

从数据结构与算法的角度看

ArrayList

底层是数组
LinkedList

底层是 双向链表
HashSet 与 HashMap 源码一致

底层是 数组+链表+红黑树
TreeSet 与 TreeMap 源码一致

底层维护了一个 EntrySet，用于存储每一个 Entry（K,V）
LinkedHashSet 与 LinkedHashMap 源码一致

底层是 数组+双向链表

# Collections工具类

Collections 是一个操作 List、Map、Set 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序（sort）、翻转（reverse）、求最值（max、min）等操作

# 参考资料

Java 类与接口异常

LKJ's blog

Choose mode