深浅模式
集合
字数: 0 字 时长: 0 分钟
6.1 集合的基本介绍
前面我们保存多个数据使用的是数组，那么数组有哪些不足的地方：
- 长度开始时必须指定，而且一旦指定，不能更改
- 保存的必须为同一类型的元素
- 使用数组进行增加和删除元素的操作表麻烦
那么集合相较于数组来说有哪些好处：
- 集合可以动态保存任意多个对象，使用方便
- 集合提供了一系列方便的操作对象的方法，比如 add、remove、set、get 等
- 使用集合增加和删除元素很简单
6.1.1 集合体系图
Java 的集合类很多，主要分为两大类，如图：
其中的单列集合用于存放单个对象，双列集合用于存放键值对
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");
}
}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 方法：删除多个元素
java
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]
}
}6.2.3 Collection 接口遍历元素的方式
6.2.3.1 使用 Iterator 迭代器遍历
- Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素
- 所有实现了 Collection 接口的集合类都有一个 iterator 方法，用于返回一个实现了 Iterator 接口的对象，即可以返回一个迭代器
- Iterator 仅用于遍历集合，Iterator 本身并不存放对象
- 迭代器的执行原理图
java
Iterator iterator = collection.iterator(); //得到一个集合的迭代器
//hasNext() 用于判断是否还有下一个元素
while(iterator.hasNext()) {
//iterator.next() 下移，并把下移以后的集合位置上的元素返回
System.out.println(iterator.next());
}
//退出 while 循环后，此时 iterator 已经指向了最后的元素，如果希望重新遍历，需要重置迭代器
iterator = collection.iterator();
//再次遍历
...6.2.3.2 使用增强 for 循环遍历
- 增强 for 循环可以代替 iterator 迭代器，本质一样，只能用于遍历集合或数组
- 基本语法
java
for (元素类型 元素名 : 集合名或数组名) {
访问元素
}java
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 + " ");
}
}
}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 倍
先看无参构造器的源码分析：
有如下代码：
java
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）DEBUG 步入 ArrayList 类，ArrayList 类的无参构造器先初始化 elementData 为空数组
java
public ArrayList() {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为空数组 {}
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}（2）步出 ArrayList 类，进入 for 循环中的 list.add() 方法
java
public boolean add(E e) {
ensureCapacityInternal(size + 1); //先判断是否要扩容
elementData[size++] = e; //执行赋值
return true;
}（3）步入 ensureCapacityInternal(size + 1);
java
private void ensureCapacityInternal(int minCapacity) { //此时的 minCapacity = size + 1 = 1
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}（4）步入 calculateCapacity(elementData, minCapacity) 方法：
java
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;
}（5）此时回到 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 方法，即 ensureExplicitCapacity(10);，进入该方法
java
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //用于记录集合被修改的次数
if (minCapacity - elementData.length > 0) //这里判断如果规定的容量 - 数组实际的容量 > 0,即数组实际的容量比规定的容量小，则需要扩容
grow(minCapacity);
}（6）进入 grow(minCapacity); 方法
java
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);
}（7）此时的 elementData
（8）扩容成功后就一直返回直到 add 方法：
java
public boolean add(E e) {
ensureCapacityInternal(size + 1); //这一步就执行完了
elementData[size++] = e; //然后把值赋给 elementData[size]，然后 size++，准备为下一个位置赋值
return true;
}至此，扩容成功，赋值成功
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.3.8 ArrayList、LinkedList 和 Vector 三者比较
| 对比维度 | ArrayList | LinkedList | Vector |
|---|---|---|---|
| 底层数据结构 | 动态数组 | 双向链表 | 动态数组 |
| 线程安全 | 非线程安全 | 非线程安全 | 线程安全（方法级 synchronized） |
| 扩容机制 | 默认扩容 1.5 倍（如 10 → 15 → 22 ...） | 无需扩容（链表动态增减节点） | 默认扩容 2 倍（如 10 → 20 → 40 ...） |
| 随机访问性能 | O(1)（直接通过索引） | O(n)（需遍历链表） | O(1)（同 ArrayList） |
| 头部插入/删除性能 | O(n)（需移动后续元素） | O(1)（调整头节点指针） | O(n)（同 ArrayList） |
| 尾部插入/删除性能 | O(1)（均摊时间，无需移动元素） | O(1)（调整尾节点指针） | O(1)（同 ArrayList） |
| 中间插入/删除性能 | O(n)（需移动元素） | O(n)（需遍历到位置） + O(1)（调整指针） | O(n)（同 ArrayList） |
| 内存占用 | 较低（连续内存存储元素） | 较高（每个节点需存储前后指针） | 同 ArrayList |
| 允许 null 值 | 是 | 是 | 是 |
| 重复元素 | 允许 | 允许 | 允许 |
| 迭代器 | 支持快速失败（Fail-Fast） | 同 ArrayList | 同 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 不保证元素是有序的
- 不能有重复元素/对象
java
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 + '\'' +
'}';
}
}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 源码分析
有代码：
java
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);
}
}- 首先 debug 进入 HashSet 的无参构造器，HashSet 的无参构造器就是 new 了一个 HashMap，所以说 HashSet 的底层就是 HashMap
java
public HashSet() {
map = new HashMap<>();
}- 步出 HashSet 的无参构造器，进入 HashSet 的 add 方法
java
public boolean add(E e) { // e = "java"
return map.put(e, PRESENT)==null; // PRESENT = private static final Object PRESENT = new Object(); 这里的 PRESENT 是 static 的是共享的
}- 步入 put 方法
java
public V put(K key, V value) { // key = "java" value = PRESENT
return putVal(hash(key), key, value, false, true);
}- 步入
hash(key)方法
java
static final int hash(Object key) { //key = "java"
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); //解释如下
}（1）代码结构
java
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);- 三元运算符
? :如果 key 为 null，直接返回 0；否则，计算key.hashCode()并进一步处理。 - 赋值与位运算
(h = key.hashCode()) ^ (h >>> 16)- 这段代码的作用就是通过混合高低位计算出 key 的哈希值
h = key.hashCode()：获取 key 的原始哈希值并赋值给 hh >>> 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 // 最终哈希值高位信息（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)方法
java
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;
}resize 方法用于扩容
java
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;
}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
如果两个对象根据 equals(Object)方法是相等的，那么调用这两个对象的 hashCode 方法1必须产生相同的整数结果
6.4.5 LinkedHashSet
6.4.5.1 基本介绍
- LinkedHashSet 是 HashSet 的子类
- LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个数组 + 双向链表
- LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
- LinkedHashSet 不允许添加重复元素
6.4.5.2 底层机制
java
Set set = new LinkedHashSet();
set.add(new String("AA"));
set.add(456);
set.add(456);
set.add(new Customer("刘", 1001));
set.add("zhishu");
- LinkedHashSet 底层维护的是一个 LinkedHashMap，LinkedHashMap 维护了一个 hash 表【数组 table】和双向链表，其中 LinkedHashMap 有 head 和 tail 属性，用于指向链表节点的头和尾；有 table 属性，用于存放元素
- 每一个节点有 pre 和 next 属性，这样可以形成双向链表
- 添加第一次时，直接将数组 table 扩容到 16，存放的节点类型是
LinkedHashMap$Entry，数组是HashMap$Node[]类型，存放的元素是LinkedHashMap$Entry类型
java
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);
}
}在添加一个元素时，先求 hash 值，再求索引，确定该元素在 table 的位置然后将添加的元素加入到双向链表，如果已经存在，则不添加
这样的话，遍历 LinkedHashSet 也能确保插入顺序和遍历顺序一致
6.4.6 TreeSet
- 当使用无参构造器创建 TreeSet 时，仍然是无序的
- 如果希望添加的元素按照字符串大小来排序可以使用 TreeSet 提供的一个构造器，可以传入一个比较器并指定排序规则
6.4.7 HashSet、LinkedHashSet 和 TreeSet 三者比较
| 对比维度 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层数据结构 | 哈希表（基于 HashMap 实现） | 哈希表 + 双向链表 | 红黑树（自平衡二叉搜索树） |
| 线程安全 | 非线程安全 | 非线程安全 | 非线程安全 |
| 元素唯一性 | 通过 equals() 和 hashCode() 保证唯一性 | 同 HashSet | 通过 compareTo() 或 Comparator 保证唯一性 |
| 元素顺序 | 无序（不保证插入或访问顺序） | 插入顺序（按元素添加顺序遍历） | 自然排序 或 自定义排序（通过 Comparator） |
| 允许 null 值 | 是 | 是 | 否（无法与排序规则兼容） |
| 性能（增删查） | O(1)（平均情况，哈希冲突时可能退化为 O(n)） | O(1)（近似，维护链表带来轻微开销） | O(log n)（红黑树操作复杂度） |
| 内存占用 | 较低（仅存储哈希表） | 较高（额外维护链表指针） | 较高（存储树结构节点及平衡信息） |
| 迭代效率 | 低（顺序不可预测，依赖哈希分布） | 高（按插入顺序直接遍历链表） | 中（按排序顺序遍历树结构） |
| 额外功能 | 无 | 保留插入顺序 | 支持范围查询（如 subSet(), headSet(), tailSet()） |
| 适用场景 | 快速去重、无需顺序控制 | 需要保留插入顺序的去重集合 | 需要动态排序或范围查询的有序集合 |
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 源码分析
java
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
}
}- Key-Value 是存放在
HashMap$Node中的 - Key-Value 为了方便遍历，还会创建 EntrySet 集合，该集合存放的元素类型是 Entry，Entry 的类型是 Map， Entry 对象就有 Key-Value 的属性，Entry 对象的 Key-Value 就会指向 Node 对象的 Key-Value，然后把 Entry 对象放到 EntrySet 集合中
java
transient Set<Map.Entry<K,V>> entrySet;- entrySet 中存放的类型是 Map.Entry，但是实际上存放的还是
HashMap$Node，因为 Node 实现了 Entry 接口
java
static class Node<K,V> implements Map.Entry<K,V>- 当把
HashMap$Node对象存放到 entrySet 后就方便遍历，因为 Map.Entry 提供了方法：
java
K getKey();
V getValue();- 简单来说就是会把 Node 节点对象转成 Entry 对象然后放到 EntrySet 集合中
- 也可以调用 keySet 方法把所有的 key 放到一个集合中，可以调用 values 把所有的 value 放到一个集合中
6.5.3 常用方法
put：添加remove：根据键删除映射关系get：根据键获取值size：获取元素个数isEmpty：判断个数是否为 0clear：清除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】，就会进行树化
java
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）执行构造器 new HashMap()，初始化加载因子
java
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}（2）执行 put 方法
java
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}（3）执行 hash(key) 方法
java
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}（4）步过继续执行 putVal 方法
java
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;
}（5）resize 方法
java
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.5.7 HashMap、LinkedHashMap、TreeMap 和 HashTable 四者比较
| 对比维度 | HashMap | LinkedHashMap | TreeMap | HashTable |
|---|---|---|---|---|
| 线程安全 | 非线程安全 | 非线程安全 | 非线程安全 | 线程安全（方法级 synchronized） |
| 允许 null 键/值 | 允许（1个null键，多个null值） | 同 HashMap | 不允许null键（依赖排序规则），允许null值 | 不允许（插入null键/值会抛出异常） |
| 底层数据结构 | 数组 + 链表/红黑树（Java 8+） | 数组 + 链表/红黑树 + 双向链表（维护顺序） | 红黑树（自平衡二叉搜索树） | 数组 + 链表（旧实现，无红黑树优化） |
| 元素顺序 | 无序 | 插入顺序 或 访问顺序（可配置） | 自然排序 或 自定义排序（通过 Comparator） | 无序 |
| 性能（增删查） | O(1)（平均情况，哈希冲突可能退化） | 近似 O(1)（链表维护带来轻微开销） | O(log n)（红黑树操作） | O(1)（同步锁导致多线程性能差） |
| 内存占用 | 较低 | 较高（额外维护双向链表） | 较高（存储树节点及平衡信息） | 同 HashMap |
| 迭代顺序 | 不可预测 | 按插入或访问顺序遍历 | 按键的排序顺序遍历 | 无序 |
| 特殊功能 | 无 | 支持 LRU 缓存（通过访问顺序模式） | 支持范围查询（如 subMap(), headMap()） | 无 |
| 初始容量 | 16 | 同 HashMap | 无固定容量（树结构动态调整） | 11 |
| 扩容机制 | 容量 × 2（如16 → 32） | 同 HashMap | 无（树结构自动平衡） | 容量 × 2 + 1（如11 → 23 → 47） |
| 负载因子 | 默认 0.75 | 同 HashMap | 无 | 默认 0.75 |
| 迭代器 | Iterator（支持快速失败） | 同 HashMap | Iterator（按排序顺序遍历） | Enumeration（不支持快速失败） |
| 适用场景 | 高频键值操作，无需顺序 | 需保留插入顺序或实现 LRU 缓存 | 需动态排序或范围查询 | 遗留代码中的线程安全需求（已被 ConcurrentHashMap 取代） |
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.8 面试题
（1）HashMap 在多线程下会有哪些问题
- 多线程下扩容会死循环，JDK7 中的 HashMap 使用的是头插法来处理链表，在多线程环境下扩容会出现环形链表，造成死循环，JDK8 时通过尾插法修复了这个问题，扩容时会保持链表原来的顺序
- 多线程在进行 put 元素的时候，可能会导致元素丢失，因为计算出来的位置可能会被其它线程覆盖掉，比如一个线程 put 3 的时候，另外一个线程 put 了 7，就把 3 给弄丢了
- put 和 get 并发时，可能导致 get 为 null，线程 1 执行 put 时，因为元素个数超出阈值而扩容，线程 2 此时执行 get ，因为线程 1 执行完 table = newTab 之后，线程 2 中的 table 已经发生了改变，比如说索引 3 的键值对移动到了索引 7 的位置，此时线程 2 去 get 索引 3 的元素就 get 不到了
（2）TreeMap 和 HashMap 的区别
TreeMap 是基于红黑树实现的，put 元素的时候会先判断根节点是否为空，如果为空，直接插入到根节点，如果不为空，会通过 key 的比较器来判断元素应该插入到左子树还是右子树，TreeMap 的查找效率是 O(logn) ，并且保证了元素的顺序，因此适用于需要大量范围查找或者有序遍历的场景