当前位置：首页 > news >正文

Java-List，Set，Map（八股）

news 2026/5/11 16:18:45

List

实现方法：

ArrayList,LinkedList（两者都不保证线程安全）

底层数据结构：

ArrayList底层使用的是Object数组，LinkedList底层使用的是双向链表。

使用场景：

ArrayList适用于需要频繁访问集合元素的场景。基于数组实现，可以通过索引快速访问元素。当需要频繁访问和遍历集合元素的时候，推荐使用ArrayList。

LinkedList适用于频繁进行插入和删除操作的场景。它基于链表实现，插入和删除元素的操作是需要频繁调整节点的指针，因此在插入和删除操作上具有较高的性能。

ArrayList的扩容机制：

扩容的前置核心前提：

ArrayList底层是基于定长数组实现的，内部维护了一个核心的数组属性elementData，所有元素都存放在这个数组中，这个数组的长度就是ArrayList当前的容量。扩容的本质就是解决数组长度不可变的问题，当数组存满的时候，创建新的更大的数组，把原数组元素复制过去，从而实现容量的增长。

初始化容量规则：

初始化时，底层数组elementData赋值为一个空数组，只有在第一次调用add（）方法时，容量扩充为10。

触发机制：

当前元素个数+待添加元素个数 > 底层数组的容量。

扩容规则：

默认1.5倍扩容。

扩容本质：

调用Arrays.copyOf()创建新数组，拷贝原数组元素，重新赋值引用。

Set

实现方法：

HashSet

HashSet的实现原理：

HashSet基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，相关HashSet的操作，基本上都是调用底层HashMap相关方法来完成。

Map

实现方法：

HashMap，HashTable，ConcurrentHashMap（后面两个线程安全）

HashMap底层实现原理：

HashMap底层数据结构在Java8之前是数组+链表的形式，在Java8之后是数组+链表+红黑树的形式。

初始化和扩容机制：

当创建时默认长度为0，调用put方法长度会扩容为16，当我们里面的元素个数/总容量超过默认负载因子0.75时就会进行扩容，每次扩容2倍。

扩容规则：

添加后当链表长度大于8且数组容量大于等于64时则将链表转为红黑树，追加完毕或转为红黑树如果数组内的元素个数大于数组长度*负载因子则进行扩容。

添加元素过程：

当添加对象是首先会对key进行hashCode（）运算，再调用HashMap的hash（）方法进行二次哈希，计算出桶下标，如果当前下标内容为空直接添加，不为空时则判断key的hashCode（）是否一致，如果不一致就向后找，直到下标为空时添加，如果一致则进行equals运算判断内容是否相同，相同则将value进行替换。

索引下标的计算方法：

JDK1.8之前：取模数组长度。

JDK1.8之后：与当前容量-1进行位运算&

ConcurrentHashMap和HashTable：

底层数据结构：JDK1.7的ConcurrentHashMap底层采用分段的数组+链表实现，JDK1.8采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑树。HashTable和JDK1.8之前的HashMap的底层数据结构类似都是采用数组+链表的形式，数组是HashMap的主体，链表则是主要为了解决哈希冲突存在的。