面试必备：揭开Java集合神秘面纱，HashMap、ArrayList等底层揭秘！

偏执的太偏执、 2024-03-22 20:31 72阅读 0赞

大家好，我是你们的小米小编，在这里我将为大家带来一场关于Java集合的底层实现的深度解析。作为面试题，对于HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList这五个常用的数据结构，我们一起来揭开它们神秘的面纱，一起探索它们是如何在底层实现的吧！

## HashMap ##

HashMap是Java中最常用的一种哈希表实现。它基于键（Key）-值（Value）对的存储方式，通过哈希算法来保证元素的快速查找。

**底层数据结构：数组+链表+红黑树（JDK 8及以上版本）**

*  **数组：** HashMap的核心数据结构是一个Entry数组，每个Entry对象包含一个键值对，以及用于解决哈希冲突的链表或红黑树的指针。数组的初始大小是16（JDK 8及以上版本），每次扩容都是当前大小的2倍。
 *  **链表：** 当发生哈希冲突时，即不同的键计算出相同的哈希值，新的Entry会被插入到数组对应位置的链表中。
 *  **红黑树：** JDK 8及以上版本，在哈希冲突的链表长度超过一定阈值（默认为8），链表会转化为红黑树，以提高搜索效率。

## LinkedHashMap ##

LinkedHashMap继承自HashMap，除了具有HashMap的特性外，还能保持元素的插入顺序。

**底层数据结构：HashMap + 双向链表**

*  **HashMap：** LinkedHashMap内部依然使用HashMap来存储键值对，维护着快速的查找能力。
 *  **双向链表：** 在HashMap的基础上，LinkedHashMap引入了一个双向链表来维护元素的插入顺序。每次插入新元素时，除了在HashMap中添加Entry，还会在双向链表的尾部插入新的节点。

LinkedHashMap保持了键值对的添加顺序，所以在遍历时，输出的顺序与添加顺序相同。

## ConcurrentHashMap ##

ConcurrentHashMap是为了在多线程环境下提供高效的并发性能而设计的集合类。

**底层数据结构：数组+链表+红黑树（JDK 8及以上版本）**

*  **数组：** 与HashMap类似，ConcurrentHashMap的底层也是一个Entry数组，每个Entry存储一个键值对。
 *  **链表与红黑树：** 处理哈希冲突的方式与HashMap相同，通过链表或红黑树来解决冲突，提高查询效率。
 *  **分段锁：** ConcurrentHashMap引入了“分段锁”机制，将整个数据结构划分成多个小的Segment，每个Segment独立地控制一部分数据。这样，在多线程环境下，不同线程可以同时访问不同的Segment，从而提高了并发性能。

## ArrayList ##

ArrayList是基于动态数组实现的，它提供了快速的随机访问能力。

**底层数据结构：数组**

*  **数组：** ArrayList的底层是一个Object类型的数组，默认初始容量为10。每次扩容时，当前容量会增加50%。
 *  **动态扩容：** 当元素数量超过当前数组容量时，ArrayList会触发扩容操作，创建一个更大的数组，并将原有数据复制到新数组中。

## LinkedList ##

LinkedList是基于双向链表实现的，它提供了快速的插入和删除能力。

**底层数据结构：双向链表**

*  **双向链表：** LinkedList的底层是一个双向链表，每个节点包含元素值、前向指针和后向指针。
 *  **插入和删除：** 由于双向链表的特性，插入和删除操作非常高效，只需要调整节点的指针即可。

## 总结 ##

通过本次深入解析，我们了解到了HashMap、LinkedHashMap、ConcurrentHashMap、ArrayList、LinkedList的底层实现原理。

*  **HashMap和LinkedHashMap都使用数组+链表（或红黑树）的数据结构，其中LinkedHashMap又额外引入了双向链表来保持插入顺序。**
 *  **ConcurrentHashMap在保留HashMap特性的基础上，通过分段锁的机制提高了并发性能。**
 *  **ArrayList是基于动态数组实现，提供了快速的随机访问能力。**
 *  **LinkedList是基于双向链表实现，提供了快速的插入和删除能力。**

## END ##

希望本篇文章能对大家理解这些数据结构的底层实现有所帮助。如果有任何疑问或者更多想了解的话题，欢迎在评论区留言，我们下期再见！加油，一起探索更多有趣的技术知识！

如有疑问或者更多的技术分享，欢迎关注我的微信公众号“**知其然亦知其所以然**”！

![8ad0b71191ba403d8f09454c5fb9dbb2.webp][]![5aee22ea0d38431e8798c3b2c773f453_tplv-obj.jpg_traceid_20230725101346562F3D837C118DB9A105_x-expires_2147483647_x-signature_IocGXuSo381CU2XODR3nujjYvlw_3D][]

[8ad0b71191ba403d8f09454c5fb9dbb2.webp]: https://img-blog.csdnimg.cn/8ad0b71191ba403d8f09454c5fb9dbb2.webp
[5aee22ea0d38431e8798c3b2c773f453_tplv-obj.jpg_traceid_20230725101346562F3D837C118DB9A105_x-expires_2147483647_x-signature_IocGXuSo381CU2XODR3nujjYvlw_3D]: https://p3-sign.toutiaoimg.com/tos-cn-i-qvj2lq49k0/5aee22ea0d38431e8798c3b2c773f453~tplv-obj.jpg?traceid=20230725101346562F3D837C118DB9A105&x-expires=2147483647&x-signature=IocGXuSo381CU2XODR3nujjYvlw%3D