【Java】集合底层原理_java集合集合底层原理

整体

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的

从底层结构而言：

ArrayList —> 数组
LinkedList 、Queue 、TreeMap —> 引用
HashSet —> HashMap —> 数组 + 链表 —> 数组 + 引用
LinkedHashSet —> LinkedHashMap —> 数组 + 双向链表 —> 数组 + 引用

---

 
 

Collection体系

 

ArrayList

底层结构：数组（动态Object[ ]数组）

实现原理：

1、当调用add()方法，先计算容器的大小，重新new一个新的数组大小，并将当前的数组所有元素复制到这个新的数组中，然后将最新的值放入数组的最后一个

2、底层采用数组实现，若使用不带参数的构造方法，则生成长度为10的Object类型数组

3、若个数超过10，则生成一个新数组，长度为原数组的1.5倍+1，原数组的内容复制到新数组中

4、删除时，后续前移，代价高

---

LinkedList

底层结构：双向链表

实现原理：

1、链表由每一个节点构成，每一个节点包含指向前后两个节点的指针和业务数据

2、头结点不存放数据，无参构造方法创建包含head节点的空链表

3、不存在容量不足问题，不需要扩容

---

HashSet

底层结构：HashMap

实现原理：

1、HashMap的put()方法是一个键值对，当新放入HashMap的Entry中key 与集合中原有Entry的key相同，新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变。

2、因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。

---

LinkedHashSet

底层结构：LinkedHashMap

实现原理：与LinkedHashMap类似，添加对象时因为Map键值对的原理，重复的元素不会添加，满足了Set的不重复特性

---

Queue

底层结构：特殊的线性表

实现原理：它只允许在对头进行删除操作，在对尾进行添加操作。采用“先进先出”的原则进行操作

---

 
 

Map体系

 

HashMap

底层结构：哈希表（链表散列），即数组和链表

实现原理：

1、HashMap底层是一个数组结构，数组中每一项又是一个链表结构。链表是为了解决hash冲突。

2、往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

3、HashMap类的属性中定义了Entry类型的数组，每一对key和value是作为Entry类的属性被包装在Entry的类中

4、在jdk1.8中，链表长度大于8时转化为红黑树

---

LinkedHashMap

底层结构：数组 + 双向链表

实现原理：LinkedHashMap是HashMap的子类，实现结构和HashMap类似，将链表换为双向链表，增加了排序实现

---

TreeMap

底层结构：红黑树节点

实现原理：

1、关于红黑树的节点插入操作，首先是改变新节点，新节点的父节点，祖父节点，和新节点的颜色，能在当前分支通过节点的旋转改变的，则通过此种操作，来满足红黑书的特点。

2、如果当前相关节点的旋转解决不了红黑树的冲突，则通过将红色的节点移动到根节点解决，最后在将根节点设置为黑色

---

Ps. 红黑树特点

红黑树是一个更高效的检索二叉树，有如下特点：

1. 每个节点只能是红色或者黑色
2. 根节点永远是黑色的
3. 所有的叶子的子节点都是空节点，并且都是黑色的
4. 每个红色节点的两个子节点都是黑色的（不会有两个连续的红色节点）
5. 从任一个节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点（叶子节点到根节点的黑色节点数量每条路径都相同）

红黑树自平衡：

红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单

 
 

参考：
https://blog.csdn.net/zglwy/article/details/79111322
https://blog.csdn.net/hjw1991324/article/details/52204859
https://my.oschina.net/90888/blog/1624758
红黑树：
https://www.sohu.com/a/201923614_466939
https://blog.csdn.net/sun_tttt/article/details/65445754