当前位置：首页>后端>正文

java 集合

后端2024-04-20 16:16:06

一、集合基础

1.01 集合的类继承关系？

java集合主要由Collection和Map两大接口派生出来：
- Collection用于存放单一元素：
  - List
  - Set
  - Queue
- Map用于存放键值对

1.02 说说 List, Set, Queue, Map 四者的区别？

List：有序的、可重复
- Arraylist： Object[] 数组
- Vector：Object[] 数组
- LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)
Set：无序不可重复
- HashSet(无序，唯一): 基于 HashMap 实现的，底层采用
- LinkedHashSet: LinkedHashSet 是 HashSet 的子类，构造函数是用LinkedHashMap来构造的，LinkedHashMap又是在HashMap的基础上，重写了三个保留方法 afterNodeAccess、afterNodeInsertion、afterNodeRemoval来维护双向链表的。
- TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)
Queue：先进先出、有序、可重复
- ArrayBlockingQueue：数组 + 双指针
- PriorityQueue：Object[] 数组来实现二叉堆
Map：键值对存储，key不可重复，value可以重复
- HashMap：JDK1.8 之前 HashMap 由数组+链表组成的，之后换成了数组+链表+红黑树的方式，当链表长度达到8时，看看数组长度，数组长度小于64，进行扩容，大于64，转成红黑树
- Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
- TreeMap： 红黑树（自平衡的排序二叉树）

1.03 如何选用集合？

当存放键值对时，选用Map接口下集合，需要对key排序时，选用TreeMap，需要保证线程安全，就用ConcurrentHashMap。
当我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

1.04 为什么要使用集合？

为了存储一组类型相同的数据。

1.05 Arraylist 和 Vector 的区别?

ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全。
Vector 是 List 的古老实现类，底层使用Object[ ] 存储，线程安全的（方法上加synchronized关键字）。

1.06 Arraylist 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构。
插入和删除是否受元素位置的影响：
- ArrayList插入O(1)，删除O(n)要移动元素，按照index插入O(n)
- LinkedList：插入O(1)，按照index插入O(n)指针移动到删除位置，删除O(1)
是否支持快速随机访问：
- LinkedList 不支持高效的随机元素访问
- ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象
内存空间占用：
- ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间
- LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（要存放指针）

1.07 comparable 和 Comparator 的区别？

comparable：接口来自java.lang包，内部比较器，一个类如果想要使用 Collections.sort(list) 方法进行排序，则需要实现该接口，重写compareTo(Object obj)方法。
Comparator：接口来自Java.util包，外部比较器，用于对那些没有实现Comparable接口或者对已经实现的Comparable接口中的排序规则不满意进行排序。无需改变类的结构，更加灵活。重写compare(Object obj1, Object obj2)方法，（策略模式）。

1.08 无序性和不可重复性的含义是什么？

无序性是指不按照数组的索引顺序添加，而是根据数据的hash值决定。
不可重复性是指，添加的元素按照equals方法比较时，返回false。要求重写equals和hashCode方法。

1.09 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

相同：都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
底层数据结构不同：
- HashSet 的底层数据结构是哈希表（基于 HashMap 实现）
- LinkedHashSet 继承自HashSet（基于LinkedHashMap实现），在构造函数中，调用了HashSet的提供LinkedHashMap的构造函数，由LinkedHashMap来保证FIFO，其他api都是共用HashSet的。
- TreeSet 底层数据结构是红黑树（基于TreeMap实现，TreeMap是用红黑树实现的），元素是有序的，排序的方式有自然排序和定制排序。
应用场景不同：
- HashSet 用于不需要保证元素插入和取出顺序的场景
- LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景
- TreeSet 用于支持对元素自定义排序规则的场景

1.20 Queue 与 Deque 的区别？

Queue：
- Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循先进先出（FIFO）规则。
- 根据因为容量问题而导致操作失败后处理方式的不同可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
  
  Queue接口抛出异常返回特殊值
  
  插入队尾 add(E e) offer(E e)
  
  删除队首 remove() poll()
  
  查询队首元素 element() peek()
  
  类似基于列表的方法抛异常，add、remove、element

Queue接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque:

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类。

Deque接口	抛出异常	返回特殊值
插入队首	addFirst(E e)	offerFirst(E e)
插入队尾	addLast(E e)	offerLast(E e)
删除队首	removeFirst()	pollFirst()
删除队尾	removeLast()	pollLast()
查询对首元素	getFirst()	peekFirst()
查询队尾元素	getLast()	peekLast()

类似基于列表的方法抛异常，add、remove、get

Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

1.21 ArrayDeque 与 LinkedList 的区别？

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能。
ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。

1.22 谈一谈 PriorityQueue？

PriorityQueue 与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。
利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据。
通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

1.23 HashMap 和 Hashtable 的区别？

线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的,因为 Hashtable 内部的方法基本都经过synchronized 修饰。（如果你要保证线程安全的话就使用 ConcurrentHashMap 吧！）
效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。另外，Hashtable 基本被淘汰，不要在代码中使用它。
对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
初始容量大小和每次扩充容量大小的不同：
- ① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
- ② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证，下面给出了源代码）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

底层数据结构： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

1.24 HashMap 和 HashSet 区别?

HashSet 底层就是基于 HashMap 实现的，HashSet 持有一个HashMap。
HashMap实现了Map接口，HashSet实现了Set接口。
HashMap存键值对，HashSet存对象，（值存的一个Object假值）。
HashMap添加元素用put方法，HashSet添加元素用add方法。
HashMap计算hashCode用键计算，HashSet用存储的对象计算。

1.25 HashMap 和 TreeMap 区别？

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。
NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。
SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器，比如在创建TreeMap时，实现Comparator接口。

1.26 HashSet 如何检查重复？

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相等的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

1.27 HashMap 的长度为什么是 2 的幂次方？

为了让计算槽位的算法能从 hashCode%n 转换成位移&运算，提高运算速度。
为了让数据分布更加均匀

1.28 HashMap 有哪几种常见的遍历方式?

迭代器 EntrySet
迭代器 KeySet
ForEach EntrySet
ForEach KeySet
Lambda forEach
EntrySet/KeySet Streams

1.29 ConcurrentHashMap 和 Hashtable 的区别？

底层数据结构：
- JDK1.7 的 ConcurrentHashMap 底层采用分段的数组+链表实现，JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样，数组+链表/红黑二叉树。
- Hashtable 的底层数据结构采用数组+链表的形式。
实现线程安全的方式：
- 在 JDK1.7 的时候，ConcurrentHashMap（分段锁）对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。到了 JDK1.8 的时候已经摒弃了 Segment 的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap。
- Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

1.30 ConcurrentHashMap 线程安全的具体实现方式/底层具体实现？

JDK1.7：
- 首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
- ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。
- Segment 实现了 ReentrantLock,所以 Segment 是一种可重入锁。
- .一个 ConcurrentHashMap 里包含一个 Segment 数组。一个 Segment 包含一个 HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry 数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。
JDK1.8：
- ConcurrentHashMap 取消了 Segment 分段锁，采用 CAS 和 synchronized 来保证并发安全。
- 数据结构跟 HashMap1.8 的结构类似，数组+链表/红黑二叉树。
- Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))。
- synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

1.31 Collections 工具类常用方法？

排序：

// 反转
void reverse(List list)
// 随机排序
void shuffle(List list)
// 按自然排序的升序排序
void sort(List list)
// 定制排序，由Comparator控制排序逻辑
void sort(List list, Comparator c)
// 交换两个索引位置的元素
void swap(List list, int i , int j)
// 旋转。当distance为正数时，将list后distance个元素整体移到前面。
// 当distance为负数时，将 list的前distance个元素整体移到后面
void rotate(List list, int distance)

查找,替换操作：

// 对List进行二分查找，返回索引，注意List必须是有序的
int binarySearch(List list, Object key)
// 根据元素的自然顺序，返回最大的元素。 类比int min(Collection coll)
int max(Collection coll)
// 根据定制排序，返回最大元素，排序规则由Comparatator类控制。
// 类比int min(Collection coll, Comparator c)
int max(Collection coll, Comparator c)
// 用指定的元素代替指定list中的所有元素
void fill(List list, Object obj)
// 统计元素出现次数
int frequency(Collection c, Object o)
// 统计target在list中第一次出现的索引，找不到则返回-1，
// 类比int lastIndexOfSubList(List source, list target)
int indexOfSubList(List list, List target) 
// 用新元素替换旧元素
boolean replaceAll(List list, Object oldVal, Object newVal)

**同步控制 **(不推荐，需要线程安全的集合类型时请考虑使用 JUC 包下的并发集合)

二、集合使用问题

2.01 判断所有集合内部的元素是否为空?

判断所有集合内部的元素是否为空，使用 isEmpty() 方法，而不是 size()==0 的方式。
因为 isEmpty() 方法的可读性更好，并且时间复杂度为 O(1)。
绝大部分我们使用的集合的 size() 方法的时间复杂度也是 O(1)，不过，也有很多复杂度不是 O(1) 的，ConcurrentHashMap的size()时间复杂度为O(n)，动态去统计hash槽里的数据。

2.02 集合转 Map？

在使用 java.util.stream.Collectors 类的 toMap() 方法转为 Map 集合时，一定要注意当 value 为 null 时会抛 NPE 异常。

2.03 集合遍历？

不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator 方式，如果并发操作，需要对 Iterator 对象加锁。
Java8 开始，可以使用 list.removeIf()方法删除满足特定条件的元素。

2.04 集合去重？

可以利用 Set 元素唯一的特性，可以快速对一个集合进行去重操作，避免使用 List 的 contains() 进行遍历去重或者判断包含操作。
HashSet 的 contains() 方法底部依赖的 HashMap 的 containsKey() 方法，时间复杂度接近于 O（1）（没有出现哈希冲突的时候为 O（1））。
ArrayList 的 contains() 方法是通过遍历所有元素的方法来做的，时间复杂度接近是 O(n)。

2.05 集合转数组？

使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。

2.06 数组转集合？

使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。

2.07 数组转换为 ArrayList的方式?

手动实现工具类，for循环挨个添加。
最简便的方法，利用ArrayList的构造方法，接收一个数组创建。
java8的Stream；List myList = Arrays.stream(myArray).collect(Collectors.toList());
使用 Guava
使用 Apache Commons Collections
使用 Java9 的 List.of()方法

三、源码分析

3.1 ArrayList源码&扩容机制分析

3.1.1 ArrayList 简介？

ArrayList继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口
RandomAccess 是一个标志接口，表明实现这个这个接口的 List 集合是支持快速随机访问的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList 实现了 Cloneable 接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现了 java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

3.1.2 Arraylist 和 Vector 的区别?

ArrayList 是 List 的主要实现类，底层使用 Object[ ]存储，适用于频繁的查找工作，线程不安全 .
Vector 是 List 的古老实现类，底层使用 Object[ ]存储，线程安全的，整个方法添加synchronized关键字，即锁住当前对象.

3.1.3 Arraylist 与 LinkedList 区别?

是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。
底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表数据结构。
插入和删除是否受元素位置的影响：
- ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。
- LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index, E element)）时间复杂度近似为o(n))因为需要先移动到指定位置再插入。
是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会可能会浪费一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

3.1.4 Arraylist源码分析？

默认初始容量大小10。
无参构造默认返回一个空数组，第一次添加元素时扩容到默认初始容量10。
用Object数组保存数据。
带初始容量参数的构造函数，会返回一个初始容量大小的Arraylist。
带集合参数的构造函数，构造一个包含指定集合的元素的列表。

3.1.5 Arraylist扩容机制？

add添加元素之前，先扩容。
首先计算每次add前，需要的最小数组长度，为元素个数+1。当元素个数为0时，最小需要长度会赋默认值10。当最小需要值大于数组的长度，需要进行扩容。
扩容大小为，oldCapacity + (oldCapacity >> 1)，即1.5倍原长度。
因为不是线程安全的，不会加锁。

3.1.6 System.arraycopy() 和 Arrays.copyOf()方法？

System.arraycopy()是本地方法
Arrays.copyOf()是基于System.arraycopy()封装的方法

3.1.7 ensureCapacity(int minCapacity)方法？

ensureCapacity方法在源码中没有调用，这个方法是留给使用者调用，作用是大量add元素时，减少扩容次数，提高效率。

3.2 HashMap源码&底层数据结构分析

3.2.01 HashMap源码&底层数据结构分析？

JDK1.8 之前 HashMap 由数组+链表组成的，JDK1.8 之后由数组 + 链表/红黑树组成。当链表长度大于阈值（默认为 8）（数组的长度大于等于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。
默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。
哈希表大小总是2的幂次，是为了将求余计算转为逻辑与运算，提高运算效率，同时为了让键值分布更均匀。

3.2.02 HashMap类成员变量？

默认的初始容量是16。
默认的填充因子0.75f，除了默认的填充因子，还可以自己指定填充因子。
- 填充因子是控制数据疏密的程度的，填充因子越接近1，填充密度越大，查找越慢（越容易出现冲突）。填充因子越接近0，填充密度约小（浪费空间），越容易查找。官方给出的默认值是0.75f.
链表转成红黑树阈值是8。
红黑树退化成链表阈值是6。
链表转红黑树数组的最小长度是64。
Node<k,v>[]数组存储键值对，数组长度是2的幂次。
修改计数器。
存储的元素个数。
临界值 = 容量*填充因子，当实际存入个数大于临界值时，会触发扩容。
- threshold = capacity * loadFactor（临界值 = 容量*填充因子），当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是衡量数组是否需要扩增的一个标准。

3.2.03 HashMap 三个构造函数？

无参构造函数，创建一个数组大小默认16的HashMap。
包含另一个“Map”的构造函数。
指定“容量大小”的构造函数。
指定“容量大小”和“加载因子”的构造函数。

3.2.04 HashMap put方法分析?

判断table数组是否为空，如果为空进行扩容。
计算哈希值，看看在table中是否存在，不存在直接插入数据，存在进行对比值，值相同直接覆盖返回，值不同判断节点类型。
如果节点为树节点，直接插入，如果节点为链表，插入后判断长度是否大于8，table长度是否大于64，是的话转换成树，否则++size后，判断是否需要扩容。

3.2.05 HashMap get方法？

计算hash取余（转移位运算），计算出在table中的位置。
取第一个节点key的进行相等判断，如果key相等，直接返回，如果key不相等继续判断节点类型。
如果节点为树，遍历树，如果节点为链表遍历链表。

3.2.06 resize 扩容方法？

首先判断原始容量是不是已经达到最大值（Integer的最大值21亿，-2^31 —— 2^31-1），如果达到最大值，不再扩容，只能随便碰撞了。
如果没有达到最大值，扩大到原值的2倍。
重新计算临界值（阈值）。
新创建一个原来容量2倍容量的table，遍历旧table，将旧table的数据重新hash插入到新table中，重新插入会分三种情况：
- 如果旧节点的next为空，直接插入新的节点
- 如果旧节点的类型是树
- 如果旧节点是链表
扩容会伴随重新hash（hash存放在Node节点里），非常耗时。所以应该尽量避免触发扩容。

3.3 ConcurrentHashMap源码&底层数据结构分析

3.3.1 JDK1.7:

3.3.1.1 ConcurrentHashMap源码&底层数据结构分析？

不可变的Segment数组内嵌套可扩容的HashEntry<K,V>[]数组组成，当出现冲突时，HashEntry<K,V>会转成链表解决冲突，Segment数组默认长度为16（不可变），可以理解为支持最大16个并发。

3.3.1.2 put方法分析？

计算要 put 的 key 的位置，获取指定位置的 Segment
如果指定位置的 Segment 为空。则初始化这个 Segment：
- 检查计算得到的位置的 Segment 是否为null
- 为 null 继续初始化，使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。
- 再次检查计算得到的指定位置的 Segment 是否为null。
- 使用创建的 HashEntry 数组初始化这个 Segment。
- 自旋判断计算得到的指定位置的 Segment 是否为null，使用 CAS 在这个位置赋值为 Segment。
Segment.put 插入 key,value 值：
- tryLock() 获取锁，获取不到使用 scanAndLockForPut 方法继续获取。
- 计算 put 的数据要放入的index 位置，然后获取这个位置上的 HashEntry 。
- 遍历 put 新元素。为什么要遍历？因为这里获取的 HashEntry 可能是一个空元素，也可能是链表已存在，所以要区别对待：
  - 如果这个位置上的 HashEntry 不存在：
    - 如果当前容量大于扩容阀值，小于最大容量，进行扩容
    - 直接头插法插入。
  - 如果这个位置上的 HashEntry 存在：
    - 判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值。
    - 不一致，获取链表下一个节点，直到发现相同进行值替换，或者链表表里完毕没有相同的。
    - 如果当前容量大于扩容阀值，小于最大容量，进行扩容。
    - 直接链表头插法插入
- 如果要插入的位置之前已经存在，替换后返回旧值，否则返回 null

3.3.1.3 scanAndLockForPut方法分析？

自旋获取锁，如果自旋超过最大自旋次数，使用lock() 阻塞获取锁。

3.3.1.4 rehash方法扩容？

ConcurrentHashMap 的扩容只会扩容到原来的2倍。老数组里的数据移动到新的数组时，位置要么不变，要么变为 index+ oldSize，参数里的 node 会在扩容之后使用链表头插法插入到指定位置。

3.3.1.5 get方法查找？

计算得到 key 的存放位置。
遍历指定位置查找相同 key 的 value 值。

JDK1.8:

3.3.2.1 JDK1.8 ConcurrentHashMap源码&底层数据结构分析？

数据结构：Node 数组 + 链表 / 红黑树，与HashMap类似。

initTable 方法初始化？

ConcurrentHashMap 的初始化是通过自旋和 CAS 操作完成的。里面需要注意的是变量 sizeCtl ，它的值决定着当前的初始化状态。
-1 说明正在初始化
-N 说明有N-1个线程正在进行扩容

put 方法？

key、value不允许为null。
进入自旋处理，首先判断table是不是存在，不存在需要初始化，然后自旋一次。
判断计算出来的位置是不是为null，为null就cas尝试写入，写入成功就跳出自旋，否则进入下一次自旋。
判断hashcode == MOVED == -1，如果是，就需要扩容。
如果都不满足，则利用synchronized加锁写入数据，写入数据要分成链表和红黑树处理。
节点加入成功后，判断是否达到树化阈值8，如果达到，需要进行树化。树化时也要判断数组长度是否达到64了，如果没有达到，只是扩容。

get 方法？

根据 hash 值计算位置。
查找到指定位置，如果头节点就是要找的，直接返回它的 value。
如果头节点 hash 值小于 0 ，说明正在扩容或者是红黑树，查找之。
如果是链表，遍历查找之。

查看全文

https://www.xamrdz.com/backend/3sk1924126.html

一、集合基础

1.01 集合的类继承关系？

1.02 说说 List, Set, Queue, Map 四者的区别？

1.03 如何选用集合？

1.04 为什么要使用集合？

1.05 Arraylist 和 Vector 的区别?

1.06 Arraylist 与 LinkedList 区别?

1.07 comparable 和 Comparator 的区别？

1.08 无序性和不可重复性的含义是什么？

1.09 HashSet、LinkedHashSet 和 TreeSet 三者的异同？

1.20 Queue 与 Deque 的区别？

1.21 ArrayDeque 与 LinkedList 的区别？

1.22 谈一谈 PriorityQueue？

1.23 HashMap 和 Hashtable 的区别？

1.24 HashMap 和 HashSet 区别?

1.25 HashMap 和 TreeMap 区别？

1.26 HashSet 如何检查重复？

1.27 HashMap 的长度为什么是 2 的幂次方？

1.28 HashMap 有哪几种常见的遍历方式?

1.29 ConcurrentHashMap 和 Hashtable 的区别？

1.30 ConcurrentHashMap 线程安全的具体实现方式/底层具体实现？

1.31 Collections 工具类常用方法？

二、集合使用问题

2.01 判断所有集合内部的元素是否为空?

2.02 集合转 Map？

2.03 集合遍历？

2.04 集合去重？

2.05 集合转数组？

2.06 数组转集合？

2.07 数组转换为 ArrayList的方式?

三、源码分析

3.1 ArrayList源码&扩容机制分析

3.1.1 ArrayList 简介？

3.1.2 Arraylist 和 Vector 的区别?

3.1.3 Arraylist 与 LinkedList 区别?

3.1.4 Arraylist源码分析？

3.1.5 Arraylist扩容机制？

3.1.6 System.arraycopy() 和 Arrays.copyOf()方法？

3.1.7 ensureCapacity(int minCapacity)方法？

3.2 HashMap源码&底层数据结构分析

3.2.01 HashMap源码&底层数据结构分析？

3.2.02 HashMap类成员变量？

3.2.03 HashMap 三个构造函数？

3.2.04 HashMap put方法分析?

3.2.05 HashMap get方法？

3.2.06 resize 扩容方法？

3.3 ConcurrentHashMap源码&底层数据结构分析

3.3.1 JDK1.7:

3.3.1.1 ConcurrentHashMap源码&底层数据结构分析？

3.3.1.2 put方法分析？

3.3.1.3 scanAndLockForPut方法分析？

3.3.1.4 rehash方法扩容？

3.3.1.5 get方法查找？

JDK1.8:

3.3.2.1 JDK1.8 ConcurrentHashMap源码&底层数据结构分析？

initTable 方法初始化？

put 方法？

get 方法？

相关文章：