Java集合八股文

概念

数组和集合的区别

数组是固定长度的数据结构，一旦创建长度就无法改变，而集合是动态长度的数据结构，可以根据需要动态增加或减少元素。
数组可以包含基本数据类型和对象，而集合只能包含对象。
数组可以直接访问元素，而集合需要通过迭代器或其他方法访问元素。

说一说Java中的集合？

常见的List：

ArrayList：是容量可变的非线程安全列表，它的底层使用数组实现。当几何扩容时，会创建更大的数组，将原数组复制到新数组。ArrayList支持对元素的快速随机访问，但是插入与删除速度很慢。
LinkedList：本质是一个双向链表，与ArrayList相比，其插入和删除速度更快，但随机访问速度更慢。

Set不允许存在重复元素，与List不同，Set中的元素是无序的，常见的Set：

HashSet：通过HashMap实现，HashMap的Key即HashSet存储的元素，所有Key都是用相同的Value，一个Object类型常量。使用Key保证元素唯一性，但不保证有序性。由于HashSet是HashMap实现的，因此线程不安全。
LinkedHashSet：继承自HashSet，通过LinkedHashMap实现，使用双向链表维护元素插入顺序。
TreeSet：通过TreeMap实现的，添加元素到集合时按照比较规则将其插入合适的位置，保证插入后的集合仍然有序。

Map 是一个键值对集合，存储键、值和之间的映射。Key 无序，唯一；value 不要求有序，允许重复，常见的Map：

HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突），JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
HashTable：数组+链表组成的，数组是 HashTable 的主体，链表则是主要为了解决哈希冲突而存在的
ConcurrentHashMap：Node数组+链表+红黑树实现，线程安全的（jdk1.8以前Segment锁，1.8以后volatile + CAS 或者 synchronized）

Java中线程安全的集合有哪些？

在java.util包下：

Vector
Hashtablle

并发Map：

ConcurrentHashMap

并发Set：

CopyOnWriteArraySet

并发List：

CopyOnWriteArrayList

List

线程安全：Vector、CopyOnWriteArrayList

现场不安全：ArrayList、LinkedList

ArrayList

ArrayList 基于动态数组实现，它允许快速的随机访问，即通过索引访问元素的时间复杂度为 O (1)。在添加和删除元素时，如果操作位置不是列表末尾，可能需要移动大量元素，性能相对较低。适用于需要频繁随机访问元素，而对插入和删除操作性能要求不高的场景，如数据的查询和展示等。

ArrayList的扩容机制

ArrayList在添加元素的时候，如果当前元素个数到达内部数组容量上限，就会触发扩容操作。主要包括以下几个步骤：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

计算新的容量：将旧的容量(oldCapacity)扩大为原来的int newCapacity = oldCapacity + (oldCapacity >> 1);，然后检查是否超过了最大容量限制；

为什么要用 >> 右移运算？

对比于$\times 1.5$，>> 右移运算是CPU一级加速，要快很多

使用位运算可以避免引入浮点计算，同时无需处理溢出的额外逻辑。如果原数组大小为7，$7\times 1.5$就会产生小数，而$(111){2} >> 1=(11){2}=3$不会产生小数

之后调用Arrays.copyOf，它的作用是创建新的数组，将元素赋值，完成扩容

ArrayList线程安全吗？

不是线程安全的。

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

在add()添加元素的方法中

ensureCapacityInternal：用于确保容量的大小，如果不足则触发 grow() 扩容
elementData[size++] = e;：将元素加入数组中，再size自增

这里就可能出现两种线程安全问题

size++不是原子操作，多线程同时add会导致数据丢失，比如同时操作elementData[3 ++ ] = 'jason'，可能出现elementData[4] = null的情况
扩容grow()不是线程安全的，在多线程下可能会造成数组覆盖，数组长度增加的情况

LinkedList

Java 提供的双向链表，所以它不需要像上面两种那样调整容量，它也不是线程安全的。

LinkedList和ArrayList的区别？

底层数据结构不同：ArrayList使用数组实现，通过索引进行快速访问元素。LinkedList使用链表实现，通过节点之间的指针进行元素的访问和操作。
插入和删除操作的效率不同：ArrayList在尾部的插入和删除操作效率较高，但在中间或开头的插入和删除操作效率较低，需要移动元素。LinkedList在任意位置的插入和删除操作效率都比较高，因为只需要调整节点之间的指针，但是LinkedList是不支持随机访问的，所以除了头结点外插入和删除的时间复杂度都是0(n)。
随机访问的效率不同：ArrayList支持通过索引进行快速随机访问，时间复杂度为O(1)。LinkedList需要从头或尾开始遍历链表，时间复杂度为O(n)。
空间占用：ArrayList在创建时需要分配一段连续的内存空间，因此会占用较大的空间。LinkedList每个节点只需要存储元素和指针，因此相对较小。
使用场景：ArrayList适用于频繁随机访问和尾部的插入删除操作，而LinkedList适用于频繁的中间插入删除操作和不需要随机访问的场景。
线程安全：这两个集合都不是线程安全的，Vector是线程安全的

Vector

Vector和ArrayList类似，也是基于数组实现。Vector中的方法大多是同步的，这使得它在多线程环境下可以保证数据的一致性，但在单线程环境下，由于同步带来的开销，性能会略低于ArrayList。

Vector 的所有方法都是 synchronized，加的是粗锁，性能差，被淘汰了。（结合Synchronized锁升级中jdk15禁用偏向锁来说）

CopyOnWriteArrayList

CopyOnWriteArrayList在对列表进行修改（如添加、删除元素）时，会创建一个新的底层数组，将修改操作应用到新数组上

加Reentrantlock，然后复制新数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean add(E e) {
 final ReentrantLock lock = this.lock;
 lock.lock();
 try {
     Object[] elements = getArray();
     int len = elements.length;
     Object[] newElements = Arrays.copyOf(elements, len + 1);
     newElements[len] = e;
     setArray(newElements);
     return true;
 } finally {
     lock.unlock();
 }
}
注意：

写操作是复制整个数组

写期间加锁

最后用 setArray(newElements)一次性替换

而读操作仍然在原数组上进行，这样可以保证读操作不会被写操作阻塞，实现了读写分离，提高了并发性能。

直接读数组，不加锁，这是因为数组引用的是 volatile，读数据不会改变数据结构

优点：

读操作无锁，非常快，适合读多写少的高并发场景
读写完全分离，并发性很强
不会爆ConcurrentModificationException异常

缺点：

写的开销很大，因为要复制整个数组
内存占用高，因为同时存在两个数组
写操作不适合大数据量，写操作一次，要复制几十万的数据，耗资源
无法保证实时一致性，读到的是旧数据，不是刚刚写进去的内容

Map

线程安全：HashTable、ConcurrentHashMap

线程不安全：HashMap、LinkedHashMap

哈希冲突的解决方法？

链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap

HashMap是基于哈希表实现的Map，它根据键的哈希值来存储和获取键值对，JDK 1.8中是用数组+链表+红黑树来实现的。HashMap是非线程安全的，在多线程环境下，当多个线程同时对HashMap进行操作时，可能会导致数据不一致或出现死循环等问题。比如在扩容时，多个线程可能会同时修改哈希表的结构，从而破坏数据的完整性。

HashMap 底层结构是数组 + 链表 + 红黑树
当链表的长度大于8的时候会转化为红黑树优化查询
-------------------
index 0 | Node -> Node -> Node (链表)
index 1 | Node
index 2 | TreeNode (红黑树)
index 3 | null
index 4 | Node
...

通过(n - 1) & hash计算bucket下标

^ 按位异或、& 按位与

hash值是什么？

它的计算是由用户传入的key + hashCode计算 + 内部的再次扰动生成的
1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
为什么要用h ^ (h >>> 16)?

>>>运算符的作用是将右移动位，左补零

例子：(159 >>> 4) = (1001 1111 >>> 4) = 0000 1001

^的作用是1^1=0、0^0=0、0^1=1、1^0=1（相同为 0，不同为 1）

159 ^ (159 >>> 4) = (1001 1111) ^ (0000 1001) = (1001 0110)

作用是：为了把高位信息混合到低位，使 hash 分布更均匀

冲突的时候：

链表
当链表长度 > 8时，转为红黑树

HashMap使用的是尾插法

为什么使用尾插法？

resize（扩容）会把链表重新 hash 到新数组。

Java 7 的 rehash 过程会依赖链表的顺序来拆分链表。而使用了头插法，并且链表是单向链表，这会导致节点的next指针错乱，可能会产生自环导致死循环。

所以在java 8的时候改为了尾插法，它不会改变链表的顺序。

HashMap 为什么必须保证数组长度是 2 的幂（如 16、32、64）

首先HashMap中哈希计算是(length - 1) & hash，用&比%快很多，它是CPU一级加速，&的作用是$1&1=1、0&1=0、0&0=0$（两个值都为1才为1）

length的长度必须是2的幂是因为当$length = 2^n$的时候，$length - 1=(011…111){2}$，对比于$length=(100…000){2}$来说，length - 1在做&运算的时候，除了第一位所有位都能用上，减少哈希冲突

如果不是2的幂就会导致在二进制上出现分布不均匀的0，一些位永远用不上，造成大量的hash落到同一个桶中

hashmap的put过程介绍一下

put(k, v)
 ├─ 1. 计算 hash（扰动函数）
 ├─ 2. 计算 index = (n - 1) & hash
 ├─ 3. 桶为空 → 直接插入
 ├─ 4. 桶不为空：
 │     ├─ key 一样 → 覆盖旧值
 │     ├─ key 不一样 → 冲突 → 链表 / 红黑树处理
 ├─ 5. 插入后判断是否需要树化（链表长度>8）
 ├─ 6. 插入完成后判断是否需要扩容 resize
 └─ END

为什么 (n - 1) & hash == hash % n（仅当 n 是 2 的幂）？

假设n = 16，n - 1 = (1111)，hash = 7 = (0111)

(n - 1) & hash = (1111) & (0111) = (0111) = 7，本质是取hash的低4位

hash % n = 7 & 16 = 7，%16的余数本质也是取hash的低4位

转红黑树的处理？

只有当链表$\ge 8$并且数组长度$\ge 64$才能转树，如果链表 $\ge$ 8 但是数组很小（小于64），HashMap 会干什么？

👉 不转树！只是扩容（resize）！

HashMap 把链表转红黑树的阈值定为 8，是基于大量统计结果与概率论

HashMap 只有在链表长度 ≥ 8 且桶数组容量 ≥ 64 时才树化。
因为链表过长会导致查找退化为 O(n)，红黑树可以优化为 O(log n)。
但树化成本较高，如果数组容量太小，扩容后元素会重新分布，链表自然变短，不需要树化，因此 HashMap 会优先扩容而非树化。

resize扩容机制？

有两个关键字threshold：阈值 = 数组长度 * loadFactor、loadFactor：默认0.75

当 put 之后，实际元素个数 size > threshold，就会触发 resize。

比如：

初始容量：16

负载因子：0.75

threshold：16 * 0.75 = 12

当第13个元素put进去后，size超过12，就会触发resize()

JDK8中resize主要干了
1
2
3
4
5
6
7
Node<K,V>[] oldTab = table;
int oldCap = oldTab.length;
int newCap = oldCap << 1;          // 容量翻倍
int newThr = oldThr << 1;          // 阈值也翻倍
Node<K,V>[] newTab = new Node[newCap];
table = newTab;
transfer(oldTab, newTab);          // 把旧数据搬过去
核心点：容量翻倍，阈值翻倍，元素重新分布。

最精华的点：JDK 8 如何“聪明地搬元素”（不重新算 hash）？

扩容时只看 (hash & oldCap) 这一位是 0 还是 1，
决定“留在原桶”还是“移到 index + oldCap”。
1
2
3
4
5
6
7
if ((hash & oldCap) == 0) {
    // 这一位是 0 → 还在原来的桶
    放到低位链表 lo
} else {
    // 这一位是 1 → 跑到原 index + oldCap 的桶
    放到高位链表 hi
}
假设oldCap = 16 = (0001 0000)，index + oldCap = 32，hash = 3 = (0000 0011)

(hash & oldCap) = 3 & 16 = (0000 0011) & (0001 0000) = (0000 0000) = 0，这个值就保留在(0, 16)里

假设oldCap = 16 = (0001 0000)，index + oldCap = 32，hash = 17 = (0001 0001)

(hash & oldCap) = 17 & 16 = (0001 0001) & (0001 0000) = (0001 0000) = 16，这个值就保留在(16, 32)里

HashMap 1.7和1.8的区别？

底层结构不同：1.7使用的是数组 + 单向链表；1.8使用的是数组 + 链表 + 红黑树
插入方式不同：1.7使用的头插法；1.8使用的尾插法
扩容逻辑：1.7需要重新计算index；1.8进行了优化，只需要判断（hash & oldCap）
hash扰动函数：1.7需要经过多次扰动函数；1.8只需要经历一次

HashMap调用get一定安全吗？

不是的，需要注意

空指针异常：调用未初始化的HashMap.get(null);会出现空指针异常
线程安全：HashMap不是线程安全的，假设一个线程调用get方法获取key为A的值，另一个线程将key为A的值删除了，就会出现修改异常ConcurrentModificationException

HashMap key可以为null吗？

可以为null

当key为空时，直接另key的哈希值为0，不走key.hashCode()方法；

hashMap虽然支持key和value为null，但是null作为key只能有一个，null作为value可以有多个；

因为hashMap中，如果key值一样，那么会覆盖相同key值的value为最新，所以key为null只能有一个。

重写HashMap的equal和hashcode方法需要注意什么？

如果o1.equals(o2)，那么o1.hashCode() == o2.hashCode()总是为true的。
如果o1.hashCode() == o2.hashCode()，并不意味着o1.equals(o2)会为true。

HashMap在比较元素时，会先通过hashCode进行比较，相同的情况下再通过equals进行比较。

列举HashMap在多线程下可能会出现的问题？

JDK1.7中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容的时候有可能导致环形链表的出现，形成死循环。因此，JDK1.8使用尾插法插入元素，在扩容时会保持链表元素原本的顺序，不会出现环形链表的问题。
多线程同时执行 put 操作，如果计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。此问题在JDK 1.7和 JDK 1.8 中都存在。

LinkedHashMap

LinkedHashMap继承自HashMap，它在HashMap的基础上，使用双向链表维护了键值对的插入顺序或访问顺序，使得迭代顺序与插入顺序或访问顺序一致。由于它继承自HashMap，在多线程并发访问时，同样会出现与HashMap类似的线程安全问题。

HashTable

Hashtable是早期 Java 提供的线程安全的Map实现，它的实现方式与HashMap类似，但在方法上使用了synchronized关键字来保证线程安全。通过在每个可能修改Hashtable状态的方法上加上synchronized关键字，使得在同一时刻，只能有一个线程能够访问Hashtable的这些方法，从而保证了线程安全。

ConcurrentHashMap

ConcurrentHashMap在 JDK 1.8 以前采用了分段锁等技术来提高并发性能。在ConcurrentHashMap中，将数据分成多个段（Segment），每个段都有自己的锁。在进行插入、删除等操作时，只需要获取相应段的锁，而不是整个Map的锁，这样可以允许多个线程同时访问不同的段，提高了并发访问的效率。

在 JDK 1.8 的 ConcurrentHashMap 去掉了 Segment，改用 Node 数组 + CAS + synchronized。

get 完全无锁，put 时在桶级别加锁，空桶插入用 CAS，占坑失败就重试。
冲突严重时可以像 HashMap 一样链表转红黑树，做到高并发下的安全与性能平衡。

分段锁怎么加锁的？

在 ConcurrentHashMap 中，将整个数据结构分为多个 Segment，每个 Segment 都类似于一个小的 HashMap，每个 Segment 都有自己的锁，不同 Segment 之间的操作互不影响，从而提高并发性能。

JDK 1.7 ConcurrentHashMap中的分段锁是用了 ReentrantLock，是一个可重入的锁。

已经用了synchronized，为什么还要用CAS呢？

ConcurrentHashMap 的设计理念是：能不用锁就不用锁，能用 CAS 就不去用 synchronized

因此

insert到空桶——>CAS
链表插入，冲突处理——>synchronized

往空桶（tab[i] == null）里放一个节点，使用无锁自旋即可完成，占用资源极小

ConcurrentHashMap用了悲观锁还是乐观锁?

添加元素的时候先判断容器是否为空：

如果为空，则用volatile + CAS（乐观锁）来初始化，再添加元素
如果不为空，使用synchronized（悲观锁）添加元素

说一下HashMap和HashTable、ConcurrentMap的区别

HashMap线程不安全，效率高一点，可以存储null的key和value，null的key只能有一个，null的value可以有多个。默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小。底层数据结构为数组+链表，插入元素后如果链表长度大于阈值（默认为8），先判断数组长度是否小于64，如果小于，则扩充数组，反之将链表转化为红黑树，以减少搜索时间。
HashTable线程安全，效率低一点，其内部方法基本都经过synchronized修饰，不可以有null的key和value。默认初始容量为11，每次扩容变为原来的2n+1。创建时给定了初始容量，会直接用给定的大小。底层数据结构为数组+链表。它基本被淘汰了，要保证线程安全可以用ConcurrentHashMap。
ConcurrentHashMap是Java中的一个线程安全的哈希表实现，它可以在多线程环境下并发地进行读写操作，而不需要像传统的HashTable那样在读写时加锁。ConcurrentHashMap的实现原理主要基于分段锁和CAS操作。它将整个哈希表分成了多Segment（段），每个Segment都类似于一个小的HashMap，它拥有自己的数组和一个独立的锁。在ConcurrentHashMap中，读操作不需要锁，可以直接对Segment进行读取，而写操作则只需要锁定对应的Segment，而不是整个哈希表，这样可以大大提高并发性能。