集合框架类

本章内容都由网上整合，以及个人思考，仅用于学习分享，如有侵权部分或者思考错误地方，欢迎大家及时提出，本人一定及时纠正。

Java的集合类有哪些

Java集合主要由两大接口派生：

Collection：主要用于存放单一元素
Map：主要存放键值对

Collection（抽象类和辅助类并未列出）

List：存储的元素是有序、可重复的

ArrayList：Object[]数组
Vector：Object[]数组
LinkList：双向链表（JDK1.6前为循环链表）

Set：存储的元素不可重复

HashSet（无序，唯一）：基于 HashMap 实现，底层采用 HashMap 保存元素
LinkedHashSet：是 HashSet 的子类，内部由 LinkedHashMap 实现
TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树）

Queue：按特定的排队规则来确定先后顺序，有序、可重复

PriorityQueue：Object[] 数组实现小顶堆
DelayQueue：PriorityQueue
ArrayDeque：可扩容动态双向数组

Map

HashMap：JDK1.8前由数组+链表组成，且数组是 HashMap 的主体，链表则是为了解决哈希冲突（“拉链法”）。JDK1.8后，在解决哈希冲突时有了较大变化，当链表长度大于阈值（默认为8）（将链表转换成红黑树前会判断，如果当前数组长度小于64，会选择先进行数组扩容，而不是转换）时，将链表转换成红黑树，以减少搜索时间。
LinkedHashMap：继承自 HashMap ，所以底层依然是基于拉链式散列结构，即由数组和链表或红黑树组成。除此之外，LinkedHashMap在这基础上，增加了一条双向链表，用于维护键值对的插入顺序或访问顺序
Hashtable：数组+链表组成，数组是 Hashtable的主体，链表是为了解决哈希冲突
TreeMap：红黑树

集合类中哪些是线程安全的，哪些是不安全的

线程安全

Vector：Vector 是一个古老的集合类，所有方法都使用了 synchronized 关键字进行同步，因此线程安全。由于 synchronized 作用于每个方法上，多个线程访问 Vector 时，会阻塞其他线程，影响性能。现在通常建议使用 ArrayList + 显式同步（如 Collections.synchronizedList() 或 CopyOnWriteArrayList）
HashTable：HashTable 是一个古老的哈希表，方法都是同步的。但现在一般推荐使用 HashMap
Collections.synchronizedList、Collections.synchronizedSet、Collections.synchronizedMap：这些方法可以将非线程安全的集合包装成线程安全的

线程不安全

ArrayList、LinkedList、HashSet、TreeSet
TreeMap、HashMap、Hashtable

ArrayList 和 Array 有什么区别

大小和自动扩容
- Array在创建时必须指定大小，且大小固定。一旦创建，大小不能修改
- ArrayList是动态数组实现，大小可动态增长或缩小
支持泛型
- Array可以存储任何类型的元素，但不支持泛型
- ArrayList支持泛型，可以指定存储的元素类型
存储对象
- Array可以直接存储基本类型数据，也可以存储对象
- ArrayList只能存储对象。对于基本类型数据，需要使用对应的包装类（Integer、Double等）
集合功能
- Array简单的数据结构，不提供额外的方法对元素进行增删改查
- ArrayList是集合框架的一部分，提供了丰富的方法

ArrayList 和 LinkedList 的区别是什么，底层实现是怎么样的

ArrayList
- 内部结构：底层基于动态数组实现，提供快速的随机访问和非常快的遍历操作
- 性能：
  - 随机访问：基于数组，时间复杂度为 O(1)
  - 添加/删除元素：时间复杂度为 O(n)
  - 扩容开销：扩容时 Arrays.copyOf() 重新分配数组，时间复杂度为 O(n)
- 使用场景：当需要频繁访问列表中的元素，且添加和删除操作主要在列表末尾时，ArrayList 是一个很好的选择
补充：
1. 扩容机制：
  ArrayList默认容量10（JDK1.7）或0（JDK1.8+）。
  JDK1.8+：
  - 初始创建 ArrayList<>()时，容量为0，当添加第一个元素后，进行初始化（懒加载）DEFAULT_CAPACITY = 10。
  - 当第11个元素添加后，扩容为 1.5 * 10 = 15
  - 当第16个元素添加时，扩容为 15 * 1.5 = 22
  部分源码
  java
```
private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
```

LinkedList

内部结构：基于双向链表实现，每个元素都包含前一个和后一个元素的引用

java

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;
    }
}

性能：
- 随机访问：时间复杂度 O(n)
- 添加/删除元素：时间复杂度 O(1)

`HashMap`、`HashTable` 和 `ConcurrentHashMap` 的区别

(1) `HashMap`

线程安全：HashMap 是非线程安全的。如果多个线程同时修改一个 HashMap（如添加或删除元素），会导致不一致的结果。在多线程环境下，通常需要通过外部同步来保证线程安全。
底层数据结构：HashMap 使用哈希表（数组+链表）的数据结构。在哈希冲突时，HashMap 会将冲突的元素存储在链表中（Java 8 之后，链表会在一定条件下转为红黑树，以提高查找性能）。
扩容机制：当 HashMap 中的元素个数超过负载因子 * 容量时（负载因子通常是 0.75），它会进行扩容，通常是原容量的 2 倍，并且将所有元素重新散列到新的数组中。
性能：HashMap 的查找、插入和删除操作的时间复杂度是 O(1)，但是由于可能会发生哈希冲突，实际情况中可能退化为 O(n)（如果链表很长）。为了避免性能退化，Java 8 引入了红黑树。

(2) `HashTable`

线程安全：HashTable 是线程安全的，它通过同步锁 (synchronized) 来保证对数据的访问是互斥的。因此，它在多线程环境下是安全的，但由于锁的开销，性能较差。
底层数据结构：与 HashMap 类似，HashTable 也是基于哈希表实现的。它使用链表来处理哈希冲突。
性能问题：HashTable 在高并发情况下由于加锁的机制，性能较差。HashTable 不仅仅是为了线程安全而加锁，它对每个操作都加锁，导致并发性能不高。
扩容机制：HashTable 扩容时会将容量扩大为原来的 2 倍，但扩容时没有像 HashMap 那样提供动态负载因子的调节。

(3) `ConcurrentHashMap`

线程安全：ConcurrentHashMap 是线程安全的，它使用了不同于 HashTable 的机制。ConcurrentHashMap 的设计采用了分段锁（Java 7），而在 Java 8 中采用了桶级锁（锁粒度更细），它通过分割哈希表并对每个段加锁来提供更高的并发性。
底层数据结构：ConcurrentHashMap 也采用了哈希表的实现，底层是数组和链表（Java 8 之后同样支持红黑树）。它允许多个线程同时访问哈希表的不同部分而不会发生冲突，从而提高了并发性能。
性能：由于采用了更细粒度的锁机制（桶级锁），ConcurrentHashMap 在高并发环境下能提供比 HashTable 更高的性能。
扩容机制：ConcurrentHashMap 在 Java 8 之后采用了无锁扩容机制，可以在扩容时对不同桶的并发修改进行更高效的处理。

Java8为什么把HashMap的头插法改成尾插法

头插法插入会改变链表的顺序，导致并发情况下可能出现环形链表的情况，而改为尾插法之后，由于新插入元素之后维持原来链表的顺序不变，不会有环形链表的情况出现，但是在并发的情况下，会出现值覆盖的情况。

举例：环形链表的情况

假设有一个初始空链表，多个线程同时执行插入操作。每个线程执行插入操作时，都会修改链表的头指针。

线程 A 插入一个新节点，并将头指针指向该节点。
线程 B 同时插入另一个新节点，并将头指针指向该节点。
由于没有合适的同步机制，头指针的更新可能出现竞争，导致链表的头尾相接，从而形成环形链表。

例如，线程 A 插入了节点 X，线程 B 插入了节点 Y。假设在并发情况下，最后头指针指向节点 Y，而 Y 的 next 指向节点 X，而 X 的 next 又指向 Y，形成环形链表。

为什么 HashMap中的 `负载因子`是 `0.75`

官方给的答案是这样的：

As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.

简单来说，负载因子太低会导致大量的空桶浪费空间，负载因子太高会导致大量的碰撞，降低性能。0.75 的负载因子在这两个因素之间取得了良好的平衡。

Stack Overflow 一位大神 https://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap 从科学的角度推测了这个问题的答案。简单来说是通过二项式哈希函数的冲突概率来解释 0.75 这个问题的。感兴趣的朋友可以自行查看

谈谈对HashMap的理解

HashMap 将数据以键值对的形式存储，线程不安全
底层实现：
- JDK1.7 使用的是数组+链表。在冲突过多的情况下，链表可能会特别长，导致复杂度无限接近于O(N)
- JDK8 引入了红黑树，链表长度超过8时，将链表转换成红黑树，以提高长链表时的查找性能。这种结构称为树化桶
为什么链表大小超过8会自动转红黑树，小于6时重新变成链表
- 根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8时转换成红黑树，小于等于6的时候转换成链表
为什么引入红黑树而不是其它树呢
- 首先树的查找时间复杂度为 O(logN)
- 如果引用例如BST时，在极端情况下，会出现其中一端无限长，导致退化成链表。基于此情况衍生出了平衡二叉树，但由于要保持平衡，在数据量较大的时候进行插入/删除操作，又会带来大量的 IO开销
- 引入红黑树是因为它具有以下特性：
  1. 不追求绝对平衡，允许局部不平衡的存在，相较于AVL树，减少了很多性能开销
  2. 红黑树是一种自平衡的二叉搜索树，因此插入和删除的时间复杂度都是 O(logN)
红黑树是否会一直增高变成无限高
不会，原因如下：
1. 红黑树的自平衡性
  红黑树是一种自平衡二叉查找树，通过旋转和变色操作确保高度始终保持在 O(log⁡n) 级别。即使元素数量增加，树的高度增长是对数级而非线性的，因此不会无限增高。
2. 动态转换机制
  - 链表转红黑树：当链表长度超过阈值（默认8）时，转换为红黑树以优化查询效率。
  - 红黑树退化为链表：当节点数量减少到阈值以下（默认6）时，红黑树会重新转换为链表。这种动态转换防止了红黑树的持续增长。
3. 扩容机制 HashMap在元素数量超过负载因子（默认0.75×容量）时会触发扩容。扩容后，元素被重新分配到新的桶中，分散了单个桶的压力，可能拆分红黑树或减少节点数量，从而限制树的高度。
4. 容量阈值限制 Java规定红黑树转换的最小容量为64（MIN_TREEIFY_CAPACITY）。若HashMap容量未达此值，即使链表长度超过8，也会优先扩容而非转换为红黑树。

Hash冲突有什么解决方式？HashMap是如何解决hash冲突的

哈希冲突的通用解决方法：

开放定址法（Open Addressing）
- 原理：当冲突发生时，按某种规则（如线性探测、平方探测）寻找下一个空闲位置。
- 缺点：容易产生聚集现象，且删除操作复杂。
链地址法（Separate Chaining）
- 原理：每个哈希桶中维护一个链表（或树），冲突的键值对直接加入链表。
- 优点：实现简单，适合高冲突场景。
再哈希法（Double Hashing）
- 原理：使用第二个哈希函数重新计算位置，直到找到空闲桶。
- 优点：减少聚集现象，但计算成本较高。
公共溢出区法
- 将冲突元素统一存入一个独立的存储区域，与主表分离。

HashMap解决哈希冲突的具体实现

HashMap采用链地址法，并引入红黑树优化和动态扩容机制，具体细节如下：

数组 + 链表/红黑树结构
- 每个哈希桶是一个链表头节点。
- Java 8优化：当链表长度超过阈值（默认8）时，链表转换为红黑树，查询效率从 O(n)O(n) 提升至 O(log⁡n)O(logn)；当红黑树节点数减少到阈值以下（默认6），退化为链表。
扩容机制
- 负载因子（默认0.75）：当元素数量超过 容量 × 负载因子 时，触发扩容。
- 重新哈希：扩容后所有元素重新计算哈希值并分配到新桶中，分散冲突压力。
- 容量阈值：Java规定红黑树转换的最小容量为64（MIN_TREEIFY_CAPACITY），未达此值时优先扩容而非树化。

哈希函数优化

扰动函数：HashMap通过两次哈希（高16位异或低16位）减少哈希碰撞概率。

示例代码：

java

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

HashMap 的 put 方法流程

判断数组是否为空，为空则进行初始化
不为空，计算 k 的 hash 值，通过 (n - 1) & hash 计算应当存放在数组下标index
查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在table[index]中
存在数据，说明发生冲突，继续判断key是否相等，若相等，则用新的value替换原数据
如果不相等，则判断当前节点类型是不是树形节点，如果是树形节点，创造树形节点插入红黑树中（如果当前是树形节点，证明当前已经是红黑树了）
如果不是树形节点，创建普通Node加入链表中；判断链表长度是否大于8，并且数组长度大于64，大于的话转换成红黑树
插入完成后，判断当前节点数是否大于阈值，如果大于开始扩容为原数组的两倍

以下为HashMap的putVal方法（JDK8+）的源代码

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;
    }

HashMap的扩容机制

JDK1.7 扩容机制
1. 触发条件
- 当元素数量超过 容量 × 负载因子（默认 0.75） 时触发扩容。
- 例如：默认初始容量为 16，当元素数量超过 16 × 0.75 = 12 时，触发扩容。
2. 扩容过程
- 创建新数组：容量扩大为原来的 2 倍（如 16 → 32）。
- 重新哈希（Rehash）：遍历旧数组的所有元素，对每个键值对重新计算哈希值，确定其在新数组中的位置。
  - 索引计算：index = hash(key) & (newCapacity - 1)。
  - 链表转移：采用头插法将链表元素转移到新数组（链表顺序反转）。
3. 潜在问题
- 并发死循环：多线程扩容时，头插法可能导致链表成环（如线程 A 和线程 B 同时操作同一链表）。
- 性能开销：重新哈希需要遍历所有元素，时间复杂度为 O(n)。

JDK1.8+扩容机制

1. 触发条件

与 JDK 1.7 相同（容量 × 负载因子）。
新增限制：若链表长度超过 8，但 HashMap 总容量未达到 MIN_TREEIFY_CAPACITY（默认 64），则优先扩容而非树化。

2. 扩容优化

链表转移方式：改用尾插法（保持链表顺序不变），避免并发扩容时的死循环问题。
高位掩码优化：
- 无需重新计算哈希值，直接通过高位是否为 1确定新位置：
  - 新位置 = 原位置或原位置 + 旧容量。
- 例如：旧容量为 16（二进制 10000），若哈希值高位为 1，则新位置 = 原位置 + 16。

3. 红黑树处理

树拆分：若红黑树节点被分散到新数组的不同桶中，需检查拆分后的节点数量：
- 若节点数 ≤ 6，退化为链表。
- 否则，保持红黑树结构。
性能提升：树化后查询效率从 O(n)O(n) 提升至 O(log⁡n)O(logn)。

4. 扩容效率改进

减少哈希计算：利用哈希值高位直接定位新位置，避免重新计算。
并行化处理：JDK 1.8 优化了扩容时的遍历逻辑，提高单线程下的执行效率。

对比总结

特性	JDK 1.7	JDK 1.8+
链表转移方式	头插法（链表反转）	尾插法（保持顺序）
并发安全性	可能导致死循环	避免死循环
哈希计算优化	重新计算哈希值	利用高位掩码定位新位置
红黑树支持	无	支持树化和退化
扩容性能	时间复杂度 O(n)O(n)	部分优化，减少哈希计算开销

HashMap 为什么不是线程安全的，如何实现线程安全

为什么不是安全的
主要原因是操作不是原子的
如何实现线程安全
- 使用 Collections.synchronizedMap()方法：可以通过 Collections.synchronizedMap()方法创建一个线程安全的 HashMap，该方法返回一个同步的 Map包装器，使所有对 Map 的操作都是同步的。Collections.synchronizedMap()中的方法都带有 synchronized
  java
```
Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());
```
- 使用 ConcurrentHashMap：专门设计用于多线程环境的哈希表实现。使用分段锁机制，允许多个线程同时进行读操作，提高并发性能
  java
```
Map<String, String> concurrentMap = new ConcurrentHashMap<>();
```
- 使用锁机制：在自定义的 HashMap 操作中使用显式的锁（例如 ReentrantLock）来保证线程安全
  java
```
Map<String, String> customMap = new HashMap<>();
ReentrantLock lock = new ReentrantLock();

lock.lock();
try {
    customMap.put("key1", "value1");
} finally {
    lock.unlock();
}
```

`ConcurrentHashMap`如何控制并发操作（JDK1.8开始，JDK1.7的时候还是用Segment分段锁）

CAS 操作（无锁化设计）
- 初始化与扩容：通过 CAS 操作竞争 sizeCtl 的状态，确保只有一个线程执行初始化或扩容。
- 节点插入：若桶为空，直接用 CAS 插入新节点，避免加锁。
- 计数器更新：使用 baseCount 和 CounterCell[] 分片统计元素数量，通过 CAS 减少竞争。
synchronized 锁（细粒度锁）
- 桶级别锁：当 CAS 失败（桶非空），对链表头或树根节点加 synchronized 锁，确保单线程操作。
- 红黑树操作：转换链表为红黑树时，需加锁保证原子性。
1. 多线程协作扩容
- 触发条件：当元素数量超过 容量 × 负载因子，或单个桶链表过长时触发扩容。
  - 分段迁移：
    1. 每个线程负责迁移旧表的一部分桶（通过 transferIndex 分配任务）。
    2. 迁移时使用 ForwardingNode 标记已处理的桶，其他线程遇到后协助迁移。
- 无锁化推进：通过 CAS 更新 transferIndex，避免线程冲突。
红黑树的并发控制
- TreeBin 内部锁：对红黑树的插入、删除操作使用 synchronized 锁。
- 读写分离：读操作无锁（依赖 volatile 的 TreeNode 状态），写操作加锁。

总结

ConcurrentHashMap 通过以下方式实现高并发：

CAS + synchronized 结合：减少锁竞争，仅在必要时加锁。
分段迁移与协作扩容：多线程共同完成扩容任务，提升效率。
红黑树的并发控制：通过 TreeBin 和内部锁保证树操作的线程安全。

集合框架类 ​

Java的集合类有哪些 ​

Collection（抽象类和辅助类并未列出） ​

List：存储的元素是有序、可重复的 ​

Set：存储的元素不可重复 ​

Queue：按特定的排队规则来确定先后顺序，有序、可重复 ​

Map ​

集合类中哪些是线程安全的，哪些是不安全的 ​

线程安全 ​

线程不安全 ​

ArrayList 和 Array 有什么区别 ​

ArrayList 和 LinkedList 的区别是什么，底层实现是怎么样的 ​

HashMap、HashTable 和 ConcurrentHashMap 的区别 ​

(1) HashMap ​

(2) HashTable ​

(3) ConcurrentHashMap ​

Java8为什么把HashMap的头插法改成尾插法 ​

为什么 HashMap中的 负载因子是 0.75 ​

谈谈对HashMap的理解 ​

Hash冲突有什么解决方式？HashMap是如何解决hash冲突的 ​

HashMap 的 put 方法流程 ​

HashMap的扩容机制 ​

HashMap 为什么不是线程安全的，如何实现线程安全 ​

ConcurrentHashMap如何控制并发操作（JDK1.8开始，JDK1.7的时候还是用Segment分段锁） ​

集合框架类

Java的集合类有哪些

Collection（抽象类和辅助类并未列出）

List：存储的元素是有序、可重复的

Set：存储的元素不可重复

Queue：按特定的排队规则来确定先后顺序，有序、可重复

Map

集合类中哪些是线程安全的，哪些是不安全的

线程安全

线程不安全

ArrayList 和 Array 有什么区别

ArrayList 和 LinkedList 的区别是什么，底层实现是怎么样的

`HashMap`、`HashTable` 和 `ConcurrentHashMap` 的区别

(1) `HashMap`

(2) `HashTable`

(3) `ConcurrentHashMap`

Java8为什么把HashMap的头插法改成尾插法

为什么 HashMap中的 `负载因子`是 `0.75`

谈谈对HashMap的理解

Hash冲突有什么解决方式？HashMap是如何解决hash冲突的

HashMap 的 put 方法流程

HashMap的扩容机制

HashMap 为什么不是线程安全的，如何实现线程安全

`ConcurrentHashMap`如何控制并发操作（JDK1.8开始，JDK1.7的时候还是用Segment分段锁）