Java集合各实现类的底层实现原理_java集合底层实现

1. LinkedList是List接口的双向链表非同步实现，并允许包括null在内的所有元素。

2. 底层的数据结构是基于双向链表的，该数据结构我们称为节点

3. 双向链表节点对应的类Node的实例，Node中包含成员变量：prev，next，item。其中，prev是该节点的上一个节点，next是该节点的下一个节点，item是该节点所包含的值。

4. 它的查找是分两半查找，先判断index是在链表的哪一半，然后再去对应区域查找，这样最多只要遍历链表的一半节点即可找到

HashMap实现原理要点概括

---

参考文献：http://zhangshixi.iteye.com/blog/672697

参考文献：http://blog.csdn.net/lizhongkaide/article/details/50595719

1. HashMap是基于哈希表的Map接口的非同步实现，允许使用null值和null键，但不保证映射的顺序。

2. 底层使用数组实现，数组中每一项是个单向链表，即数组和链表的结合体；当链表长度大于一定阈值时，链表转换为红黑树，这样减少链表查询时间。

3. HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Node对象。HashMap底层采用一个Node[]数组来保存所有的key-value对，当需要存储一个Node对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Node时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Node。

4. HashMap进行数组扩容需要重新计算扩容后每个元素在数组中的位置，很耗性能

5. 采用了Fail-Fast机制，通过一个modCount值记录修改次数，对HashMap内容的修改都将增加这个值。迭代器初始化过程中会将这个值赋给迭代器的expectedModCount，在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，马上抛出异常

Hashtable实现原理要点概括

---

参考文献：http://blog.csdn.net/zheng0518/article/details/42199477

1. Hashtable是基于哈希表的Map接口的同步实现，不允许使用null值和null键

2. 底层使用数组实现，数组中每一项是个单链表，即数组和链表的结合体

3. Hashtable在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

4. synchronized是针对整张Hash表的，即每次锁住整张表让线程独占

ConcurrentHashMap实现原理要点概括

---

参考文献：http://blog.csdn.net/zheng0518/article/details/42199477

1. ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。

2. 它使用了多个锁来控制对hash表的不同段进行的修改，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个并发发生在不同的段上，它们就可以并发进行。

3. ConcurrentHashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。Hashtable底层采用一个Entry[]数组来保存所有的key-value对，当需要存储一个Entry对象时，会根据key的hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据key的hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

4. 与HashMap不同的是，ConcurrentHashMap使用多个子Hash表，也就是段(Segment)

5. ConcurrentHashMap完全允许多个读操作并发进行，读操作并不需要加锁。如果使用传统的技术，如HashMap中的实现，如果允许可以在hash链的中间添加或删除元素，读操作不加锁将得到不一致的数据。ConcurrentHashMap实现技术是保证HashEntry几乎是不可变的。

HashSet实现原理要点概括

---

参考文献：http://zhangshixi.iteye.com/blog/673143l

1. HashSet由哈希表(实际上是一个HashMap实例)支持，不保证set的迭代顺序，并允许使用null元素。

2. 基于HashMap实现，API也是对HashMap的行为进行了封装，可参考HashMap

LinkedHashMap实现原理要点概括

---

参考文献：http://zhangshixi.iteye.com/blog/673789l

1. LinkedHashMap继承于HashMap，底层使用哈希表和双向链表来保存所有元素，并且它是非同步，允许使用null值和null键。

最后

自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。

深知大多数Java工程师，想要提升技能，往往是自己摸索成长，自己不成体系的自学效果低效漫长且无助。

因此收集整理了一份《2024年Java开发全套学习资料》，初衷也很简单，就是希望能够帮助到想自学提升又不知道该从何学起的朋友，同时减轻大家的负担。

既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，不论你是刚入门Java开发的新手，还是希望在技术上不断提升的资深开发者，这些资料都将为你打开新的学习之门！

如果你觉得这些内容对你有帮助，需要这份全套学习资料的朋友可以戳我获取！！

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
朋友可以戳我获取！！**](https://bbs.csdn.net/topics/618164986)

由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！