Java集合

写在前面

本人在学习JUC过程中学习到集合和并发时有许多稀碎知识点 需要总结梳理思路与知识点  本文内容会涉及到ArrayList，HashMap以及扩容机制，ConcurrentHashMap，Synchronized，Volatile，ReentrantLock，CAS，AQS以上的底层原理等常见内容 本文内容部分引自Javaguide,小林coding等热门八股 用于个人学习用途 后续会添加内容

Java集合

为什么需要Java集合与Java并发 有什么关联？

对于常见的1+2+3 可以用数组实现该数学问题 但是在实际应用中 数组并不能满足所有的场景 于是出现了数据结构与算法 Java集合与其相互成就 常见Java集合为 List (列表) Set (集合) Map (映射）

同时在高并发场景下一定会有并发安全与线程安全问题 Java集合即能存数据 又能安全操作数据（如ConcurrentHashMap）多好。（Java并发系列单出一page 此处为集合相关八股）

集合常见数据结构

List如何实现？

三种实现方法

Vector 线程安全动态数组 若不需要线程安全 不建议使用 同步毕竟是有开销的Vector内部使用Object[ ]数组存储数据可根据需要自己扩容 扩容原来的1倍 如果数据已满 则copy原数组并重新创建一个数组再copy数据 

ArrayList 动态数组实现 非线程安全 性能比Vector要好不少都用Object[ ] 也是根据需要自己扩容

扩容原来的0.5倍

LinkedList是Java提供的双向链表 不需要扩容 因为可以无限加节点 也是非线程安全的

在什么场景下使用List的不同实现？

在需要大量增删改的情况下 链表总是占优的 操作时间复杂度为O(1) 但是遍历时就只能整表遍历

但是在大量查的情况下 用Vector或ArrayList明显占优 查询只要O(1) 但是要修改中间某节点就要移动后续节点 比较繁琐

ArrayList与LinkedList的区别

1.底层实现不同 Array用数组 LinkedLIst用链表 

2.在查询和插入时效率不同 用数组时查快插入慢 用链表时插入快查慢

3.两者都不保证线程安全

4.ArrayList支持快速随机访问 LinkedList不支持 需要遍历到指定元素输出

5.内存占用上 ArrayList会在数组末尾留下一定空间 LinkedList则每次保存一个数据就会占很大空间 要保存上个节点到该节点和该节点到下一个节点的两个指针

ArrayList 底层原理

ArrayList 的底层是一个动态数组（Object[] elementData）支持快速随机访问（时间复杂度 O(1)） 核心机制包括：

1. 扩容：当数组容量不足时扩容为原来的 1.5 倍 并将旧数据复制到新数组。

2. 添加：在末尾添加元素时间复杂度为 O(1) 在指定位置插入需要移动元素 时间复杂度为 O(n) 

3. 删除：删除元素需要移动后续元素 时间复杂度为 O(n)

4. 保证线程安全：ArrayList 是非线程安全的 多线程环境下可用 Collections.synchronizedList 或 CopyOnWriteArrayList

ArrayList扩容机制

1.计算新容量 一般都会扩容为原来的1.5倍再检查是否超过最大容量限制

2.创建新数组 3.copy数据 4.更新引用:把ArrayList内部指向的引用指向到新数组上 5.完成扩容

扩容要扩到原来的1.5倍

因为1.5可以充分利用位运算移位 大大提高运算效率 位运算一定比除2要好很多

grow()方法是扩容机制最核心部分 贴上（代码来自JavaGuide）

/*** 要分配的最大数组大小*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** ArrayList扩容的核心方法。*/
private void grow(int minCapacity) {// oldCapacity为旧容量，newCapacity为新容量int oldCapacity = elementData.length;// 将oldCapacity 右移一位，其效果相当于oldCapacity / 2。// 我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍。int newCapacity = oldCapacity + (oldCapacity >>> 1);// 然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组if (newCapacity - minCapacity < 0)newCapacity = minCapacity;// 如果新容量大于 MAX_ARRAY_SIZE, 进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE// 如果minCapacity大于最大容量，则新容量则为 `Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZEif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:elementData = Arrays.copyOf(elementData, newCapacity);
}

Set

用的不多 提一嘴 Set存储元素不可重复

Set底层实现

用哈希表和红黑树来实现key的无重复 当向Set集合插入元素时 先根据元素Hashcode来判断当前元素存储位置 再用内部的equals方法来判断是否存在已经相同的元素 是则不插入 否则插入 保证元素唯一性

有序Set

有TreeSet（红黑树）和LinkedHashSet（哈希表和双重链表）保证元素自然顺序排序

按照插入顺序排序的set是LinkedHashSet 保证唯一且有序

Map（划重点）

对于在学习过程中 Map是学的最多最杂的 在实际开发中也是应用最广泛的

常见的Map集合:（非线程安全）

HashMap：基于哈希表实现的map 通过key-value（entry）键值对的形式存储值 在jdk1.8中底层实现为数组+链表+红黑树实现 多线程下同时操作数据会不一致 比如扩容时会破坏哈希表结构

LinkedHashMap：继承自HashMap 但是他加上了双向链表保证排序按照插入顺序 同样和hashmap有一致线程安全问题存在

TreeMap：基于红黑树实现的map 可以对键排序 默认情况下升序排序 也可以按照指定比较器排序

常见的Map集合:（线程安全）

HashTable:实现方法与HashMap类似 但在方法上用了synchronized关键字来保证线程安全 这样会导致效率很低 非常僵硬

ConcurrentHashMap

原理：在JDK 1.7之前采用分段锁的方式（segment）实现，把数据分成多个段 每段都有自己独立的锁 在线程对其操作时 只需要获取对应分段的锁 而不是获取整个map的锁 这样做就可以允许多线程访问不同段 而不受到干扰 在JDK 1.8之后就用了volatile+CAS或者synchronized来保证并发安全

对map快速遍历的方法：

使用for-each和EntrySet方法遍历 输出键值对的键和值

只想输出键用keySet

HashMap底层实现原理 

JDK1.7之前 HashMap数据结构是数组和链表 HashMap通过哈希算法把元素的键（key）映射到数组中的槽位（Bucket） 若多个键映射到同一个槽位 他们会用链表的形式存储在同槽位上 因为链表的查询时间为O(n) 所以冲突很严重 一旦链表非常长 效率相当低

图解引自小林coding:

所以到了JDK 1.8的时候 当一个链表长度超过8 用红黑树进行存储 查询时为O(logn)的时间复杂度 数量较少时（codes < 6）回退成链表

图解引自小林coding:

有关红黑树和B+Tree的原理与区别 之后会在mysql时分析

当然有问题存在 如果我存的数据经过hashcode计算后一致 我该怎么存啊 ！

存在哈希冲突时的解决方案

链接法 ：很简单的第一种方法就是直接采用链表连接 叫做链接法 

开放寻址法：或者可以去找找别的地方有没有闲的让我用用 探测一下哪些地方能用 常用的有线性探测 二次探测 双重散列表探测

再哈希法：那我也可以用别的公式再算一遍 在其他槽有空闲位置就到那去 利用其他哈希函数计算hashcode 在表中找到空闲bucket并插入entry

哈希桶扩容：塞得满满当当 就该买家具了 所以可以扩容哈希桶来存储数据 重新分配entry减少哈希冲突

hashmap当然不是线程安全的 有没有替代方案（有没有其他人能处理两个人同时对他说话）

有！

HashMap的线程安全问题

可以用Collections.synchronizedMap同步加锁的方式 也可以用HashTable 但是显而易见 要求同步性能绝对不达标 所以可以用ConcurrentHashMap

ConcurrentHashMap 

在JDK 1.7版本中采用分段锁segment+HashEntry的形式存储信息 每段都有自己独立的锁 不同可以获取不同段锁从而独立访问不同段数据 JDK 1.8抛弃了Segment 用volatile+CAS(compare and swap) + synchronized + Node实现 同样也加入了红黑树 避免链表过长导致性能下降

HashMap中 put方法如何执行？ 怎么添加Entry？

以JDK 1.8版本为例 

1,根据要添加的键的哈希码（hashcode）找到数组中对应的位置

2.检查该位置是否为空 为空 则创建一个Entry把要存入的键值对放进去 并保存在数组的对应位置 把HashMap的修改次数+1（modcount）以便在迭代时发现并发修改

3.若已经存在键值对 检查该位置的第一个键值对的hashcode哈希码和键和添加的键值对是否same如果是 则说明找到相同的key 把新值替换旧值

4.若第一个键值对的哈希码和键不相同 则需要遍历链表或者红黑树来查找是否有相同键 

对于链表来说 找到就替代旧值 没找到就把键值对更新在链表头部

对于红黑树 找到就替代 找不到就加入红黑树

5.检查链表长度是否为阈值（默认为8）是且数组长度>=64 则会把链表转化为红黑树 以提高查询效率

6.检查负载因子是否超过阈值（默认0.75）如果键值对的数量（size）与数组长度的比值大于阈值则需要扩容

7.扩容操作 创建一个新的两倍大的数组 把旧数组的重新计算哈希码并分配到新数组的位置 更新hashmap的引用和阈值参数

8.完成添加操作 hashmap还是线程不安全 可以用同步机制或者用ConcurrentHashMap

hashmap中get方法不一定安全！

空指针异常：hashmap可以存null为key 但是用null为键调用get方法会返回空指针异常

线程安全：一个线程调用get 另一个线程update键值对 会导致查到错误结果或者报异常ConcurrentModificationException 。如果需要在多线程环境中使用类似 HashMap 的数据结构，可以考虑使用 ConcurrentHashMap 。

HashMap一般用什么做key？ 为什么用String?

String在Java里是不可变的 唯一String确保key的稳定性 若不定可能会导致hashcode和equals方法不一致 进而影响HashMap准确性

为什么 HashMap 使用红黑树而不是平衡二叉树

平衡二叉树是啥？任何节点的左右子树高度差不会小于1 树的节点 虽然平均分配 但是每次修改或者添加节点都会破坏树结构 要保证树结构就要用左旋或者右旋来维持结构

对于红黑树来说 追求“弱平衡” 最长路径不超过最短路径的 2 倍 插入/删除时较少破坏平衡 调整频率低 性能更优 适合频繁插入/删除的场景（如 HashMap 的链表转树）

HashMap 在多线程下的问题

JDK 1.7HashMap头插法扩容可能导致环形链表，造成死循环 JDK 1.8时使用尾插法 避免环形链表问题 都存在多线程put操作扔可能导致数据覆盖或丢失

HashMap扩容机制

hashmap默认负载因子为0.75 超过本身大小的75%就会触发扩容 分为两步

1.对哈希表长度的扩展（两倍）2.把旧哈希表数据放到新哈希表里

图解引自小林coding：

所以在扩充时 不需要重新计算hashcode 只需要看他新的bit是0还是1 是0就不变 是1就是“原索引+oldCap”

图解引自小林coding：

非常好的扩容 省去计算hash值的时间 同时可以通过判断新增的bit是1还是0可以认为是随机的 因此resize的过程 均匀的把之前冲突的节点分散到其他的bucket里了

HashMap 的大小为什么是 2 的 n 次方？

JDK1.7中 HashMap 整个扩容过程就是分别取出数组元素 一般该元素是最后一个放入链表中的元素 然后遍历以该元素为头的单向链表元素 依据每个被遍历元素的hash 值计算其在新数组中的下标然后进行交换 这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部

JDK1.8中 HashMap 对扩容操作做了优化 由于扩容数组的长度是2倍关系 所以对于假设初始tableSize = 4 要扩容到8 来说就是0100 到1000的变化（左移一位就是2倍）在扩容中只用判断原来的hash 值和左移动的一位（newtable的值）按位与操作是0 或1就行 0的话索引不变 1的话索引变成原索引加上扩容前数组

之所以能通过这种“与运算”来重新分配索引 是因为hash 值本来就是随机的 而hash 按位与上newTable得到的0（扩容前的索引位置）和1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的 所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去

因为hash值本身是随机的 进行位运算又是基本上相当快的 所以把hash值左移一位时 即把原本数据随机分布 避免哈希冲突 又能迅速扩容 一举两得

HashMap负载因子

负载因子太低会导致产生大量空桶 负载因子过高会导致大量碰撞 降低性能

0.75的负载因子在减少哈希冲突和提高空间利用率之间取得了一个折中，既避免了频繁扩容，也避免了过多的哈希冲突，从而在大多数情况下提供了较好的性能。

ConcurrentHashMap如何实现

JDK1.7 数组加链表 数组又分为大数组（segment）和小数组（hashEntry） Segment是可重入锁（Reentrantlock）扮演锁的角色 HashEntry用于存储键值对数组 每个HashEntry是链表结构元素

JDK 1.8 数组加链表/红黑树 主要通过volatile + CAS 或者 synchronized 来实现线程安全 添加元素时会判断容器是否为空 如果为空会用CAS + volatile 来初始化

如果容器不为空 根据存储元素判断当前位置是否为空  若根据存储元素计算为空 则用CAS 设置改节点 不为空就用synchronized 之后遍历桶数据 并替换新节点到桶里 最后再判断是否需要转为红黑树 就能保证并发安全

总结 ConcurrentHashMap通过对头结点加锁来保证线程安全 锁的粒度相对Segment更小了 发生冲突和加锁的概率降低了 红黑树优化固定链表 可以优化查询时间复杂度

分段锁如何加锁

ConcurrentHashMap把整个数据结构分为多个segment 每个segment类似一个小的hashmap 每个segment都有自己的锁 不同segment之间互不影响 插入 删除 查询操作需要先定位到具体segment然后在改segment上加锁 而不是像传统的HashMap里直接对整个数据结构进行加锁 可以使得不同segment并行操作 提高并发性能

分段锁的基础是  ReentrantLock 是可重入锁

ConcurrentHashMap用的是乐观锁还是悲观锁？

都有用到！首先 添加元素时判断容器是否为空：

如果为空则使用volatile加乐观锁（CAS）来初始化

若不为空就根据元素计算该位置是否为空 为空时 利用乐观锁（CAS）来设置该节点

不为空 就用synchronized（悲观锁）之后遍历桶中数据 替换或者新增节点到桶中 最后判断是否需要转为红黑树 保证并发安全

HashTable底层数据原理

数组加链表 所有方法都用synchronized修饰 保证线程安全 当一个线程访问同步方法 另一个也访问的时候会阻塞或者轮询

HashTable和ConcurrentHashMap有什么区别？如何实现线程安全？

ConcurrentHashMap JDK 1.7之前用分段数组加链表 JDK 1.8之后用数组+链表/红黑树 

HashTable采用数组 + 链表 数组是主体 链表是用来解决hash冲突的

实现线程安全方式

jdk8以前 ConcurrentHashMap 用分段锁的方式进行分段分割 每把锁只锁容器里的部分数据 多线程访问不同数据段的数据不会存在锁竞争 jdk8以后 直接采用数组+链表/红黑树 并发控制使用CAS + synchronized实现 更能提高效率

HashTable 所有方法都加锁来保证线程安全 效率很低 当一个线程访问同步方法时 另一个线程同时访问则会陷入阻塞或者轮询状态

什么是哈希函数？常见hashcode方法是什么？

首先 hash函数在计算机科学中 应用于：

• 哈希表（如 HashMap、HashSet）：快速定位数据。

• 数据校验（如文件完整性验证）。

• 加密（如密码存储，需结合盐值）。

Java 中的 hashCode() 方法

在 Java 中，hashCode() 是 Object 类的方法，用于返回对象的哈希码。默认实现基于对象的内存地址，但大多数情况下需要根据对象的实际内容重写该方法，以满足以下规则：

1. 一致性：如果 a.equals(b) 为 true，则 a.hashCode() 必须等于 b.hashCode()。

2. 非唯一性：允许不同对象有相同的哈希码（哈希冲突），但需尽量降低概率。

基本类型字段的哈希计算

• int：直接使用值。

• long：将高32位与低32位异或。

  long value = 123L;
  int hash = (int) (value ^ (value >>> 32));

• double：使用 Double.hashCode(value)。

• boolean：true 视为 1，false 视为 0。

• String：Java 默认实现为多项式哈希。

  // String 类的哈希计算（简化版）
  public int hashCode() {int hash = 0;for (char c : chars) {hash = 31 * hash + c;}return hash;
  }

2. 组合多个字段的哈希值

通过将多个字段的哈希值组合成一个整数，常见方法是使用 素数乘法 和 加法：

@Override
public int hashCode() {int result = 17; // 初始值选一个非零质数result = 31 * result + name.hashCode(); // 31 是常用质数result = 31 * result + age;result = 31 * result + (int) (id ^ (id >>> 32));return result;
}

为什么选择 31？

• 31 是奇质数，减少哈希冲突。

• 31 的乘法可优化为 (i << 5) - i，提升性能。

3. 使用工具类简化

Java 7+ 提供了 Objects.hash() 方法，自动组合多个字段：

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

HashMap ConcurrentHashMap HashTable的区别？

• HashMap线程不安全 效率比较高 可存储null的key与value null的key只能有一个 null的value可以有多个 默认初始容量为16 每次扩充为原来2倍 创建时若给定初始容量 则扩充为2的幂次方大小 底层结构为数组+链表 插入元素后若链表元素长度大于8 先判断数组长度是否小于64 如果小于 就扩充数组 反之 则链表转换为红黑树 以减少搜索时间
• HashTable 线程安全 效率比较低 内部方法都经过synchronized修饰 不可以有null的key和value 默认初始容量为11  每次扩容都变为原来的2n+1 创建时给定初始容量就用给定大小 底层数据结构为数组+链表 
• ConcurrentHashMap 线程安全的哈希表实现 可在多线程环境下并发的进行读写操作 而不需要像传统意义上的hashtable一样对所有读写操作加锁 ConcurreentHashMap基于分段锁和CAS操作 把整个哈希表分成多个段（segment）每个segment都类似于一个小的HashMap 它拥有一个自己的数组和独立的锁 在ConcureentHashMap里 读操作不需要锁 可直接用segment进行读取 而写操作只需要锁定对应的segment 而不是整个哈希表

杂谈

List和Set的读写效率与区别？

1.元素唯一性 

list可重复 set不可重复唯一

2.元素顺序

list有序 文件按照插入顺序排序 也可以用下标和索引来排序 ArrayList和LinkedList 都维护插入顺序  set通常是无序的 LinkedHashSet会维护插入顺序 TreeSet根据元素自然顺序或者自定义比较器进行排序

3.实现类 List：

ArrayList基于动态数组 随机访问 LinkedList基于双向链表 适合频繁插入和删除  Vector线程安全的动态数组                                                                                                                                      Set：HashSet基于Hash表 无序且高效 TreeSet基于红黑树 元素有序 LinkedHashSet基于hash表和链表 维护插入顺序 

4.读写效率 

List中 ArrayList通过下标访问时间复杂度效率为O(1) 写在尾部为O(1) 插入在头部或者中间位置  假设数组足够长 长度为n 插入在中间需要把后续元素向后移动一个单位  时间复杂度为O(n)

LinkedList通过遍历链表查询访问元素 时间复杂度为O(n) 插入或者删除时间复杂度为O(1)

Set中 HashSet和LinkedHashSet查询效率高O(1) 插入效率高O(1) TreeSet基于红黑树 查询和插入效率都是O(n)

5.使用场景 

List适合需要保留元素插入顺序 允许重复元素 高频需要通过索引查询元素 （存储用户操作记录或者日志） Set需要保证元素的唯一性 不需要保留插入元素（除了LinkedHashSet）用于存储唯一用户名 去重操作等等

6.遍历方式 

List提供基于索引的方法 get set 支持通过索引遍历 而Set不提供基于索引的方法 只能通过迭代器或者增强for遍历