# 第六章集合

# 6.1 集合的基本介绍

前面我们保存多个数据使用的是数组，那么数组有哪些不足的地方：

长度开始时必须指定，而且一旦指定，不能更改
保存的必须为同一类型的元素
使用数组进行增加和删除元素的操作表麻烦

那么集合相较于数组来说有哪些好处：

集合可以动态保存任意多个对象，使用方便
集合提供了一系列方便的操作对象的方法，比如 add、remove、set、get 等
使用集合增加和删除元素很简单

# 6.1.1 集合体系图

Java 的集合类很多，主要分为两大类，如图：

其中的单列集合用于存放单个对象，双列集合用于存放键值对

public class Main {
	public static void main(String[] args) {
		//单列集合
		ArrayList arrayList = new ArrayList();
		arrayList.add("jack");
		arrayList.add("tom");
		
		//双列集合
		HashMap hashMap = new HashMap();
		hashMap.put("key1", "value1");
		hashMap.put("key2", "value2");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 6.2 Collection 接口

# 6.2.1 Collection 接口的实现类的特点

实现 Collection 接口的子类可以存放多个元素，每个元素的类型可以是 Object
有些 Collection 的实现类可以存放重复的元素，有些不可以
有些 Collection 的实现类存放的元素是有序的【List】，有些不是有序的【Set】
Collection 接口没有直接的实现的子类，子类都是通过 Collection 接口的子接口 Set 接口和 List 接口来实现的

# 6.2.2 Collection 接口的常用方法

这里以子类 ArrayList 演示：

add 方法：添加单个元素
remove 方法：删除指定元素
contains 方法：查找元素是否存在
size 方法：获取元素个数
isEmpty 方法：判断是否为空
clear 方法：清空
addAll 方法：添加多个元素
containsAll 方法：查找多个元素是否都存在
removeAll 方法：删除多个元素

public class Main {
	public static void main(String[] args) {
		List list = new ArrayList();
		//添加单个元素
		list.add("jack");
		list.add(1);
		list.add(true);
		System.out.println("list = " + list); //list = [jack, 1, true]

		//删除指定元素
		//删除第一个元素
		list.remove(0);
		//删除指定某个元素
		list.remove(true);
		System.out.println("list = " + list); //list = [1]
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 6.2.3 Collection 接口遍历元素的方式

# 6.2.3.1 使用 Iterator 迭代器遍历

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素
所有实现了 Collection 接口的集合类都有一个 iterator 方法，用于返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器
Iterator 仅用于遍历集合，Iterator 本身并不存放对象
迭代器的执行原理图

Iterator iterator = collection.iterator(); //得到一个集合的迭代器

//hasNext() 用于判断是否还有下一个元素
while(iterator.hasNext()) {
    //iterator.next() 下移，并把下移以后的集合位置上的元素返回
    System.out.println(iterator.next());
}

//退出 while 循环后，此时 iterator 已经指向了最后的元素，如果希望重新遍历，需要重置迭代器
iterator = collection.iterator();

//再次遍历
...

1
2
3
4
5
6
7
8
9
10
11
12
13

# 6.2.3.2 使用增强 for 循环遍历

增强 for 循环可以代替 iterator 迭代器，本质一样，只能用于遍历集合或数组
基本语法

for (元素类型 元素名 : 集合名或数组名) {
    访问元素
}

1
2
3

public class Main {
	public static void main(String[] args) {
		Collection collection = new ArrayList();
		collection.add(1);
		collection.add(2);
		collection.add(3);

		//使用增强 for 循环遍历集合
		for (Object col : collection) {
			System.out.print(col + " ");
		}

		System.out.println();
		
		//也可以遍历数组
		Integer[] nums = {4,5,6};

		for (Integer num : nums) {
			System.out.print(num + " ");
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 6.3 List 接口

# 6.3.1 基本介绍

List 接口是 Collection 接口的子接口
List 集合类中元素有序【即添加顺序和取出顺序一致】，并且可以重复
List 集合中的每个元素都有其对应的顺序索引
List 容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素
List 接口的常用的实现类有：ArrayList、LinkedList、Vector

# 6.3.2 List 接口的常用方法

List 集合里添加了一些根据索引来操作集合元素的方法

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

# 6.3.3 List 接口的遍历方式

方式一：使用 Iterator

方式二：使用增强 for 循环

方式三：使用普通的 for 循环

# 6.3.4 ArrayList

# 6.3.4.1 ArrayList 基本介绍

ArrayList 可以加入 null，并且可以加入多个
ArrayList 是由数组来实现数据存储的
ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全的，没有 synchronized【但是执行效率高】，在多线程情况下不建议使用 ArrayList

# 6.3.4.2 ArrayList 底层源码分析

ArrayList 中维护了一个 Object 类型的数组 elementData，所有元素是存在这个数组里的，transient Object[] elementData; transient 关键字表示该属性不会被序列化
当创建 ArrayList 对象时，如果使用的是无参构造器，则会把 elementData 的容量初始化为 0，当第一次添加元素时，会把 elementData 的容量扩容为 10，当把这 10 个容量加满后，会把容量扩容成原来的 1.5 倍，即容量为 15，以后都是以 1.5 倍扩容
如果使用的是指定大小的构造器，则初始 elementData 的容量就为指定的大小，如果满了需要扩容，则直接会把容量扩容成原来的 1.5 倍
先看无参构造器的源码分析：

有如下代码：

public class Main {
	public static void main(String[] args) {
		ArrayList list = new ArrayList();
		
		for (int i = 1; i <= 10; i++) {
			list.add(i);
		}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（1）DEBUG 步入 ArrayList 类，ArrayList 类的无参构造器先初始化 elementData 为空数组

public ArrayList() {
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为空数组 {}
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

1
2
3
4

（2）步出 ArrayList 类，进入 for 循环中的 list.add() 方法

public boolean add(E e) {
    ensureCapacityInternal(size + 1); //先判断是否要扩容
    elementData[size++] = e; //执行赋值
    return true;
}

1
2
3
4
5

（3）步入 ensureCapacityInternal(size + 1);

private void ensureCapacityInternal(int minCapacity) { //此时的 minCapacity = size + 1 = 1
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

1
2
3

（4）步入 calculateCapacity(elementData, minCapacity) 方法：

private static int calculateCapacity(Object[] elementData, int minCapacity) { //此时 elementData 为 {}, minCapacity = 1
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为 {}
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //先判断 elementData 是否为空，如果为空就返回 DEFAULT_CAPACITY = 10 和 minCapacity = 1 两者中大的值，这里很明显返回 10
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //如果不为空返回 minCapacity
    return minCapacity;
}

1
2
3
4
5
6
7
8

（5）此时回到 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 方法，即 ensureExplicitCapacity(10);，进入该方法

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //用于记录集合被修改的次数

    if (minCapacity - elementData.length > 0) //这里判断如果规定的容量 - 数组实际的容量 > 0,即数组实际的容量比规定的容量小，则需要扩容
        grow(minCapacity);
}

1
2
3
4
5
6

（6）进入 grow(minCapacity); 方法

private void grow(int minCapacity) { //此时的 minCapacity = 10
    // overflow-conscious code
    int oldCapacity = elementData.length; //oldCapacity = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1); //这个意思就是 newCapacity 的大小 = oldCapacity 的 1.5 倍，因为 1.5 x oldCapacity = oldCapacity + oldCapacity / 2，因为此时是第一次扩容，所以这里的 newCapacity = 0
    if (newCapacity - minCapacity < 0) //判断，如果新容量比规定容量小，则意味着此时是第一次扩容，就直接让新容量 = 规定容量 = 10
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    //这里就把数组扩容到 newCapacity 大小的数组了，不了解 Arrays 类的 copyOf 方法可以回去看
    elementData = Arrays.copyOf(elementData, newCapacity);
}

1
2
3
4
5
6
7
8
9
10
11
12

（7）此时的 elementData

（8）扩容成功后就一直返回直到 add 方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1); //这一步就执行完了
    elementData[size++] = e; //然后把值赋给 elementData[size]，然后 size++，准备为下一个位置赋值
    return true;
}

1
2
3
4
5

至此，扩容成功，赋值成功

# 6.3.5 Vector

# 6.3.5.1 基本介绍

Vector 底层也是一个对象数组，即 protected Object[] elementData;
Vector 是线程同步的，即线程安全，Vector 类的方法带有 synchronized 关键字
在开发中，需要线程同步安全时，考虑使用 Vector
Vector 扩容机制：如果调用无参构造器，无参构造器就会调用有参构造器把容量设置为 10，之后满了以后按 2 倍进行扩容；如果调用有参构造器，则每次都是按 2 倍扩容

# 6.3.6 LinkedList

# 6.3.6.1 基本介绍

LinkedList 底层实现了双向链表和双端队列的特点
可以添加任意元素【元素可以重复】，包括 null
线程不安全，没有实现同步
LinkedList 底层维护了一个双向链表
LinkedList 中维护了两个属性 first 和 last 分别指向首节点和尾节点
每个节点【Node 对象】，里面又维护了 prev、next、item 三个属性，其中通过 prev 指向前一个，通过 next 指向后一个节点，最终实现双向链表
所以 LinkedList 的元素的添加和删除，不是通过数组完成的，相对来说效率较高

# 6.3.7 ArrayList 和 LinkedList 比较

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

如何选择 ArrayList 和 LinkedList：

如果我们改查的操作多，选择 ArrayList
如果我们增删的操作多，选择 LinkedList
一般来说，在程序中，查询的操作多，所以大部分情况下会选择 ArrayList
建议在单线程下使用二者

# 6.4 Set 接口

# 6.4.1 基本介绍

Set 是无序的，即添加和取出的顺序不一致，但是每次取出的顺序是一致的
不允许有重复的元素，所以最多只能有一个 null
JDK 中 Set 接口的实现类有很多，这里主要学习 HashSet 和 TreeSet
Set 集合没有索引

# 6.4.2 Set 接口的常用方法

和 List 接口一样，Set 接口也是 Collection 的子接口，因此常用方法和 Collection 接口一样

# 6.4.3 Set 接口的遍历方式

可以使用迭代器
可以使用增强 for 循环
不能使用索引的方式

# 6.4.4 HashSet

# 6.4.4.1 基本介绍

HashSet 实现了 Set 接口
HashSet 实际上是 HashMap
可以存放 null 值，但是只能有一个 null
HashSet 不保证元素是有序的
不能有重复元素/对象

public class Main {
	public static void main(String[] args) {
		HashSet set = new HashSet();
		
		//这两个 "jack" 是同一个字符串常量对象，所以 set 只能添加一个
		set.add("jack");
		set.add("jack");
		
		//这两个 Dog 对象 不是同一个对象，所以 set 都能添加
		set.add(new Dog("tom"));
		set.add(new Dog("tom"));

		System.out.println("set = " + set); //set = [Dog{name='tom'}, Dog{name='tom'}, jack]
	}
}

class Dog {
	public String name;

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

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

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

# 6.4.4.2 底层机制

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

# 6.4.4.2.1 简单实现数组 + 链表的结构

# 6.4.4.2.2 分析 HashSet 的添加元素的方法的底层实现结论

HashSet 底层是 HashMap
添加一个元素时，会先得到该元素的 hash 值，然后会把 hash 值转成索引值
根据索引值找到存储数据表 table，看这个索引位置是否已经存放了元素，如果该索引位置没有元素则直接加入，如果有元素存在则调用 equals 方法进行比较，如果相同就放弃添加；如果不相同的话就以链表的方式添加，就把该元素添加到该索引位置的链表的最后
在 Java8 中，如果一条链表的元素个数大于等于 TREEIFY_THRESHOLD【默认是 8】，并且 table 的大小大于等于 MIN_TREEIFY_CAPACITY【默认是 64】，就会进行树化【红黑树】

# 6.4.4.2.3 源码分析

有代码：

public class Main {
	public static void main(String[] args) {

		HashSet hashSet = new HashSet();
		hashSet.add("java");
		hashSet.add("python");
		hashSet.add("java");
		System.out.println("set = " + hashSet);

	}
}

1
2
3
4
5
6
7
8
9
10
11

首先 DEBUG 进入 HashSet 的无参构造器，HashSet 的无参构造器就是 new 了一个 HashMap，所以说 HashSet 的底层就是 HashMap

public HashSet() {
    map = new HashMap<>();
}

1
2
3

步出 HashSet 的无参构造器，进入 HashSet 的 add 方法

public boolean add(E e) { // e = "java"
    return map.put(e, PRESENT)==null; // PRESENT = private static final Object PRESENT = new Object(); 这里的 PRESENT 是 static 的是共享的
}

1
2
3

步入 put 方法

public V put(K key, V value) { // key = "java" value = PRESENT
    return putVal(hash(key), key, value, false, true);
}

1
2
3

步入 hash(key) 方法

static final int hash(Object key) { //key = "java"
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //解释如下
}

1
2
3
4

（1）代码结构

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

三元运算符 ? : 如果 key 为 null，直接返回 0；否则，计算 key.hashCode() 并进一步处理。
赋值与位运算 (h = key.hashCode()) ^ (h >>> 16)
- 这段代码的作用就是通过混合高低位计算出 key 的哈希值
- h = key.hashCode()：获取 key 的原始哈希值并赋值给 h
- h >>> 16：将 h 的二进制值无符号右移 16 位（高位补零）
- ^：将原始哈希值 h 与右移后的值进行异或运算。

示例：

假设 key.hashCode() 返回 0x12345678（32 位二进制）：

1）原始哈希值 h： 0001 0010 0011 0100 0101 0110 0111 1000

2）右移 16 位 h >>> 16： 0000 0000 0000 0000 0001 0010 0011 0100

3）异或结果 h ^ (h >>> 16)：

0001 0010 0011 0100 0101 0110 0111 1000  // h
^ 
0000 0000 0000 0000 0001 0010 0011 0100  // h >>> 16
------------------------------------------
0001 0010 0011 0100 0100 0100 0100 1100  // 最终哈希值

1
2
3
4
5

高位信息（0x1234）被混合到低位（0x5678），减少冲突概率。

（2）为什么这样设计？

1）处理 null 键

若 key == null，返回 0，这是对 null 键的特殊处理，避免调用 null.hashCode() 导致空指针异常。

2）优化哈希分布

问题：直接使用 key.hashCode() 可能导致哈希冲突。例如，若哈希表大小为 16，索引通过 (n-1) & hash 计算（仅依赖哈希的低 4 位），此时哈希值的高位变化不会影响索引，容易引发冲突。
解决方案：通过 h ^ (h >>> 16) 将哈希值的高 16 位与低 16 位混合，使高位的变化也能影响低位。
- 右移 16 位：将高 16 位移动到低位。
- 异或运算：将高 16 位与低 16 位结合，确保哈希值的高位信息被保留到低位。

3）性能与均匀性的平衡

异或运算：比加减乘除更快，且能均匀混合高低位信息。
右移 16 位：对于 32 位整数（如 Java 的 int），右移 16 位后，高 16 位变为低 16 位，原低 16 位被丢弃。

得到 key 的哈希值后，步出 hash(key) 方法，步入 putVal(hash(key), key, value, false, true) 方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //hash = 上面计算出的哈希值，key = "java"，value = PRESENT
    Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了一些辅助变量
    //这里的 table 是 HashMap 的一个属性，类型是 Node[]
    //这里的 if 就是判断当前 table 是否为空或者容量为 0，如果为空或者容量为 0，就进行第一次扩容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; //看 resize 方法【下面】，执行完 resize 方法后 tab 就变成 16 个容量的数组，进而 table 就变成 16 个容量的数组了，这样就完成了第一次扩容，n 此时 = 16，resize 方法就是用于扩容的方法
    
    //p = tab[i = (n - 1) & hash] 关于这个赋值操作的解释看下面
    //这里先根据 key 得到 hash 去计算该 key 应该存放到 table 表的哪个索引位置并把这个位置的元素赋值给 p
    //然后判断 p 是否为 null
    //1.如果 p 为 null，表示该索引位置还没有存放元素，就创建一个 Node(hash, key="java", value=PRESENT, null) 的链表节点对象，并把该节点对象放到该索引位置
    
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    else { //如果已经添加过一次 key = "java",假设 (n - 1) & hash = 3，当第二次添加 key = "java"，那么 (n - 1) & hash 也一定会等于 3，这时 tab[i = (n - 1) & hash] 就不为空，就会进入这个 else 语句
        //那么何时会进入这个 else 语句：当本来这个索引已经有元素了，但是又有一个元素的 hash 值通过计算后得到的索引值与本来这个索引值相同，那么就会进入到这个 else 语句
        Node<K,V> e; K k;
        
        //p.hash == hash:判断当前索引位置对应的链表的第一个元素(对象)的 key 的 hash 值和准备添加的 key 的 hash 值是否一样
        //((k = p.key) == key || (key != null && key.equals(k))):其中的 (k = p.key) == key 表示判断 p 这个 Node 节点对象的 key 属性所存放的对象和准备添加的 key 所存放的对象是否相等，(key != null && key.equals(k)) 表示判断准备添加的 key 是否存放对象，即是否为空，并且判断准备添加的 key 存放的对象的值是否和链表的第一个元素的 key 所存放的对象的值相同
        //总的来说就是判断 (两者节点对象的 key 所存放的对象的 hash 值相等) 并且 (两者节点对象的 key 所存放的对象相等 或者 准备添加的 key 里不为空并且两者 key 存放的对象里的值相同)
        //条件一：两者节点对象的 key 所存放的对象的 hash 值相等
        //条件二：(两者节点对象的 key 所存放的对象相等) 或者 (准备添加的 key 里不为空并且两者 key 存放的对象里的值相同)，这个简单理解就是对象相同或者值相同
        //条件一和条件二全满足，这个 if 条件才成立
        //这里的 key.equals(k) 的 equals 方法是判断地址相同还是判断值是否相同取决于 key 的类型，因为前面学了，equals 方法默认是判断地址是否相等，但是 Object 的子类比如 String、Integer 重写了该方法使其判断值是否相同，所以这里的 key 如果存放的是 String 类型的对象比如字符串 "java"，那么这里就是判断值是否相同，但是如果这里的 key 存放的是自己写的类然后并没有重写 equals 方法，那么这里就是判断地址是否相同
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //如果上面的 if 条件不满足，就看 else if 里的条件是否成立
        //p instanceof TreeNode 表示判断 p 这个 Node 链表的类型是否是红黑树
        //如果是红黑树就调用 putTreeVal 进行添加元素
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //如果以上条件都不满足，则会走 else 的语句
        //举例：向上面的例子，如果是在 john 后面添加 jack 并且该 john 所在的链表还没有变成红黑树就走这个 else 语句
        else {
            //这里开始遍历 p 这个索引位置所存放的链表
            //整个循环的流程就是让要添加的元素与该链表的第一个节点以后的所有节点进行比较，因为前面已经和第一个节点比较过后不相同才会进到这个 else 语句，所有不用再比第一个节点了，如果待添加的元素和所有的节点都不一样，就会在该链表的末尾加上该元素；如果待添加的元素有和这些节点一样的，则会 break 退出循环，进而退出 else 语句
            //在把新的元素添加成功后就会判断当前这个链表的长度是否已经大于等于 8，如果已经大于等于 8 就会调用 treeifyBin(tab, hash) 方法将该链表树化，但是在 treeifyBin(tab, hash) 方法中还会判断该 table 的容量是否大于等于 64，如果不大于等于 64 的话不会树化，只会调用 resize() 方法对 table 进行扩容；如果大于等于 64，那么该链表将会被树化
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount; //表示修改的次数
    //这个 size 不管你是把元素加到了 table 里还是加到了链表后面都会 ++
    if (++size > threshold) //这里判断当前数组的大小是否达到临界值，如果达到了就要进行扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

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

resize 方法用于扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length; //这里的 Cap 是 Capacity，指容量
    int oldThr = threshold; //临界值
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; //这里的 DEFAULT_INITIAL_CAPACITY 默认是 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); //这里的 DEFAULT_LOAD_FACTOR 是加载因子默认是 0.75，这里 newThr 是临界值，作用：原本的数组的容量默认是 16，理论上是容量为 16 了再进行扩容，但是实际上是到达这个临界值 12 后就开始扩容了，防止当多个线程进来时导致阻塞，相当于做了一个缓冲层
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //这里就创建了一个类型是 Node 的容量为 16 的数组
    table = newTab; //这里把数组赋给 table 变量
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

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
73

p = tab[i = (n - 1) & hash] 的作用就是通过哈希值快速定位到数组中的某个位置

（1）代码拆解：

i = (n - 1) & hash 这是索引计算的核心逻辑：
- n 是数组 tab 的长度，且通常是 2 的幂（如 16, 32 等）。
- n - 1 会得到一个二进制全为 1 的数（例如，n = 16 时，n-1 = 15，二进制为 1111）。
- 按位与操作 & 的作用是截取 hash 的低位。例如，若 n = 16，则 hash & 15 的结果在 0~15 之间，正好是数组的有效索引范围。
p = tab[i] 将数组 tab 中索引为 i 的元素赋值给变量 p。

（2）示例

假设哈希表长度 n = 16，某个键的哈希值 hash = 12345（二进制 11000000111001）：

n - 1 = 15（二进制 1111）。
(n - 1) & hash 取 hash 的最低 4 位：
11000000111001 & 1111 = 1001（十进制 9）。
最终 p = tab[9]，即访问哈希表的第 9 个桶。

（3）为什么用 (n - 1) & hash

替代取模运算 当 n 是 2 的幂时，(n - 1) & hash 等价于 hash % n，但位运算比取模运算快得多。例如：hash % 16 等价于 hash & 15。
均匀分布哈希冲突 这种设计能保证哈希值的高位和低位均参与索引计算（尤其在哈希函数设计合理时），减少冲突概率。

（4）典型应用场景

哈希表的桶定位 在类似 HashMap 的实现中，此操作用于确定键值对应存储的桶（数组位置）。例如 Java 的 HashMap 就使用了这种计算方式。
链表或红黑树操作 如果 tab[i] 是链表或红黑树的头节点，p 可能用于后续遍历或插入操作（如处理哈希冲突）。

（5）总结

这段代码通过位运算快速将哈希值映射到数组索引，是哈希表实现中的经典操作，兼顾高效性和均匀分布性。其核心前提是数组长度必须为 2 的幂，确保 n-1 的二进制形式为全 1

# 6.4.5 LinkedHashSet

# 6.4.5.1 基本介绍

LinkedHashSet 是 HashSet 的子类
LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个数组 + 双向链表
LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
LinkedHashSet 不允许添加重复元素

# 6.4.5.2 底层机制

Set set = new LinkedHashSet();
set.add(new String("AA"));
set.add(456);
set.add(456);
set.add(new Customer("刘", 1001));
set.add("zhishu");

1
2
3
4
5
6

LinkedHashSet 底层维护的是一个 LinkedHashMap，LinkedHashMap 维护了一个 hash 表【数组 table】和双向链表，其中 LinkedHashMap 有 head 和 tail 属性，用于指向链表节点的头和尾；有 table 属性，用于存放元素
每一个节点有 pre 和 next 属性，这样可以形成双向链表
添加第一次时，直接将数组 table 扩容到 16，存放的节点类型是 LinkedHashMap$Entry，数组是 HashMap$Node[] 类型，存放的元素是 LinkedHashMap$Entry 类型

static class Entry<K,V> extends HashMap.Node<K,V>{
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

1
2
3
4
5
6

在添加一个元素时，先求 hash 值，再求索引，确定该元素在 table 的位置然后将添加的元素加入到双向链表，如果已经存在，则不添加
这样的话，遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致

# 6.4.6 TreeSet

当使用无参构造器创建 TreeSet 时，仍然是无序的
如果希望添加的元素按照字符串大小来排序可以使用 TreeSet 提供的一个构造器，可以传入一个比较器并指定排序规则

# 6.5 Map 接口

# 6.5.1 Map 接口的实现类的特点

Map 与 Collection 并列存在，用于保存具有映射关系的数据：key-value
Map 中的 key 和 value 可以是任何引用类型的数据，会封装到 HashMap$Node 对象中
Map 中的 key 不允许重复，原因和 HashSet 一样，但是有一点区别是 Map 存放相同的 key 时是把原来那个相同 key 的 value 替换成现在这个 key 的 value，相当于替换
Map 中的 value 可以重复
Map 的 key 可以为 null，value 也可以为 null，注意 key 为 null 只能有一个，value 为空可以有多个
常用 String 类型作为 Map 的 key
key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到对应的 value
Map 中一对 k-v 是放在一个 Node 节点中的，又因为 Node 实现了 Entry 接口，也说一对 k-v 就是一个 Entry

# 6.5.2 源码分析

public class Main {
	public static void main(String[] args) {

		Map map = new HashMap();
		map.put("no1", "java");
		map.put("no2", "python");

		Set set = map.entrySet();
		for (Object obj : set) {
			Map.Entry entry = (Map.Entry) obj;
			System.out.print(entry.getKey() + " - " + entry.getValue() + " ");
		}

		System.out.println();
		Set keySet = map.keySet();
		System.out.print("所有的 key：");
		for (Object key : keySet) {
			System.out.print(key + " ");
		}

		System.out.println();
		Collection values = map.values();
		System.out.print("所有的 value：");
		for (Object value : values) {
			System.out.print(value + " ");
		}
        
        输出：
        no2 - python no1 - java 
        所有的 key：no2 no1 
        所有的 value：python java
	}
}

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

Key-Value 是存放在 HashMap$Node 中的
Key-Value 为了方便遍历，还会创建 EntrySet 集合，该集合存放的元素类型是 Entry，Entry 的类型是 Map， Entry 对象就有 Key-Value 的属性，Entry 对象的 Key-Value 就会指向 Node 对象的 Key-Value，然后把 Entry 对象放到 EntrySet 集合中

transient Set<Map.Entry<K,V>> entrySet;

entrySet 中存放的类型是 Map.Entry，但是实际上存放的还是 HashMap$Node，因为 Node 实现了 Entry 接口

static class Node<K,V> implements Map.Entry<K,V>

当把 HashMap$Node 对象存放到 entrySet 后就方便遍历，因为 Map.Entry 提供了方法：

K getKey();
V getValue();

1
2

简单来说就是会把 Node 节点对象转成 Entry 对象然后放到 EntrySet 集合中

也可以调用 keySet 方法把所有的 key 放到一个集合中，可以调用 values 把所有的 value 放到一个集合中

# 6.5.3 常用方法

put：添加
remove：根据键删除映射关系
get：根据键获取值
size：获取元素个数
isEmpty：判断个数是否为 0
clear：清除
containsKey：查找键是否存在

# 6.5.4 HashMap

# 6.5.4.1 基本介绍

HashMap 是 Map 接口使用频率最高的实现类
HashMap 是以 key-value 的方式来存储数据的
key 不能重复，但是值可以重复，允许使用 null 键和 null 值
如果添加相同的 key 则会覆盖原来的 key-value，等同于修改
与 HashSet 一样，不保证映射的顺序，因为底层是以 hash 表的方式来存储的
HashMap 没有实现同步，因此是线程不安全的

# 6.5.4.2 源码分析

HashMap 底层维护了 Node 类型的数组 table，默认为 null
当创建对象时，将加载因子【loadfactor】初始化为 0.75
当添加 key-value 时，通过 key 的哈希值得到在 table 的索引，然后判断该索引处是否有元素，如果没有元素直接添加，如果该索引处有元素，继续判断该元素的 key 和准备加入的 key 是否相等，如果相等，则直接替换 value，如果不相等需要判断是树结构还是链表结构，做出相应处理，如果添加时发现容量不够则需要扩容
第一次添加，则需要扩容 table 的容量为 16，临界值 Threshold 为 12，以后再次扩容，则需要扩容 table 容量为原来的 2 倍，临界值为原来的 2 倍，即 24，以此类推
在 Java8 中，如果一条链表的元素个数大于等于 TREEIFY_THRESHOLD【默认是 8】，并且 table 的大小大于等于 MIN_TREEIFY_CAPACITY【默认 64】，就会进行树化

public class Main {
	public static void main(String[] args) {
		HashMap map = new HashMap();
		map.put("java", 10);
		map.put("php", 10);
		map.put("java", 20);
	}
}

1
2
3
4
5
6
7
8

（1）执行构造器 new HashMap()，初始化加载因子

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

1
2
3

（2）执行 put 方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

1
2
3

（3）执行 hash(key) 方法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

1
2
3
4

（4）步过继续执行 putVal 方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value; //替换
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

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

（5）resize 方法

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

# 6.5.5 Hashtable

# 6.5.5.1 基本介绍

存放的元素是键值对
hashtable 的键和值都不能为 null，否则会抛出 NullPointerException
hashtable 使用方法基本上和 HashMap 一样
hashTable 是线程安全的，hashMap 是线程不安全的

# 6.5.5.2 源码分析

底层有数组 Hashtable$Entry[] 初始化大小为 11
临界值 threshold = 8 = 11 x 0.75
扩容机制：Hashtable 的扩容是调用 rehash 方法进行扩容，不再是 resize 方法，扩容是扩容成原来的 2 倍再加 1

# 6.5.6 Properties

# 6.5.6.1 基本介绍

Properties 类继承自 Hashtable 类并且实现了 Map 接口，也是使用一种键值对的形式来保存数据，键值对不能为空
特点和 Hashtable 类似
Properties 还可以用于从 xxx.properties 文件中加载数据到 Properties 类对象并进行读取和修改

# 6.6 集合选型规则

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，分析如下：

先判断存储的类型，看存储的类型是一组对象还是一组键值对
一组对象：使用 Collection 接口

允许重复：List
- 增删多：LinkedList【底层维护了一个双向链表】
- 改查多：ArrayList【底层维护 Object 类型的可变数组】
不允许重复：Set
- 无序：HashSet【底层是 HashMap，维护了一个哈希表】
- 排序：TreeSet
- 插入和取出顺序一致：LinkedHashSet，维护数组 + 双向链表

一组键值对：Map

键无序：HashMap
键排序：TreeMap
键插入和取出顺序一致：LinkedHashMap
读取文件：Properties

# 6.7 Collections 工具类

# 6.7.1 Collections 工具类介绍

Collections 是一个操作 Set、List 和 Map 等集合的工具类
Collections 中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作

# 6.7.2 排序操作

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List, Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List, int, int)：将指定 List 集合中的 i 处元素和 j 处元素进行交换

# 6.7.3 查找、替换操作

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection, Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection, Comparator)
int frequency(Collection, Object)：返回指定集合中指定元素的出现次数
void copy(List dest, List src)：将 src 中的内容复制到 dest 中
boolean replaceAll(List list, Object oldVal, Object newVal)：使用新值替换 List 对象的所有旧值

# 第六章 集合

# 6.1 集合的基本介绍

# 6.1.1 集合体系图

# 6.2 Collection 接口

# 6.2.1 Collection 接口的实现类的特点

# 6.2.2 Collection 接口的常用方法

# 6.2.3 Collection 接口遍历元素的方式

# 6.2.3.1 使用 Iterator 迭代器遍历

# 6.2.3.2 使用增强 for 循环遍历

# 6.3 List 接口

# 6.3.1 基本介绍

# 6.3.2 List 接口的常用方法

# 6.3.3 List 接口的遍历方式

# 6.3.4 ArrayList

# 6.3.4.1 ArrayList 基本介绍

# 6.3.4.2 ArrayList 底层源码分析

# 6.3.5 Vector

# 6.3.5.1 基本介绍

# 6.3.6 LinkedList

# 6.3.6.1 基本介绍

# 6.3.7 ArrayList 和 LinkedList 比较

# 6.4 Set 接口

# 6.4.1 基本介绍

# 6.4.2 Set 接口的常用方法

# 6.4.3 Set 接口的遍历方式

# 6.4.4 HashSet

# 6.4.4.1 基本介绍

# 6.4.4.2 底层机制

# 6.4.4.2.1 简单实现数组 + 链表的结构

# 6.4.4.2.2 分析 HashSet 的添加元素的方法的底层实现结论

# 6.4.4.2.3 源码分析

# 6.4.5 LinkedHashSet

# 6.4.5.1 基本介绍

# 6.4.5.2 底层机制

# 6.4.6 TreeSet

# 6.5 Map 接口

# 6.5.1 Map 接口的实现类的特点

# 6.5.2 源码分析

# 6.5.3 常用方法

# 6.5.4 HashMap

# 6.5.4.1 基本介绍

# 6.5.4.2 源码分析

# 6.5.5 Hashtable

# 6.5.5.1 基本介绍

# 6.5.5.2 源码分析

# 6.5.6 Properties

# 6.5.6.1 基本介绍

# 6.6 集合选型规则

# 6.7 Collections 工具类

# 6.7.1 Collections 工具类介绍

# 6.7.2 排序操作

# 6.7.3 查找、替换操作

# 第六章集合