浅谈Java集合体系及底层实现原理_java集合中的底成结构

2019-3-10补充：一个对java集合体系及结构讲的非常好的帖子
但是需要注意 这个帖子里有一点是不明的可能是各个Jdk版本不一致 ：在sum公司提供的Jdk1.8中ArrayList扩容的时候并不会+1 源码是 ：原长度+元长度>>1 

其他的讲的都很不错  包括加载因子

https://blog.csdn.net/qq_34627002/article/details/79769261

底层原理：

https://blog.csdn.net/qq_25868207/article/details/55259978

 

 

 上午 无事画了一张集合体系图

注意:深色带背景的是线程安全的

关于有序无序:

有序、无序是指在进行插入操作时，插入位置的顺序性

先插的位置在前，后插的位置在后，则为有序，反之无序

而大家容易混淆的就是排序，排序是指集合内的元素是否按照升序或降序来排序

 2019-03-04补充:

这里发现这张图画的很笼统 再进一步说一下他们的底层实现原理吧

 

List接口:

 特性:有序,可重复

 

 

1.ArrayList 

特性:增删慢,查询快 

ArrayList的底层是是用数组进行实现的 而这个数组就是一块连续存储的空间 线性表, 所以我们对他查询就会非常快,增删慢的原因是 因为他的底层是数组,大家都知道在创建数组的时候必须要声明数组的长度(不声明直接赋值那也是声明了长度的),并且数组的长度一旦声明了就无法改变,所以我们不停地对ArrayList对象添加或者删除 达到他的界限(界限可以看我的另外一篇文章 ArrayList是如何实现长度可变的)之后他就会重新创建一个数组然后把原数组的数据再复制过来 这就是他慢的原因,而查询快是因为也是因为他是线性表 一块连续存储的空间 可以直接通过指针就可以拿到元素的存储地址

2.LinkedList

 特性:增删快,查询慢

LinkedList的底层数据存储方式是双向链表 注意是双向链表不是单向链表(他俩的区别可以看一下这一位大神的分析 浅谈单向链表和双向链表的区别)

双向链表存储删除速度快是因为 链表结构的的特性 当增加一个元素的时候他就会在上一个元素的尾部保存下一个元素的内存地址并且也会在当前元素的头部添加上个元素的内存地址(双向链表才会头尾部 都保存内存地址 ,单向链表只会保存下一个元素的内存地址)  当在头尾部都添加了地址之后 一个元素的添加就已经完成,  而删除同样 只要在元素的头尾部替换成被删除元素的下一个元素的内存地址就行

查询慢的原因 也会因为他的链表结构 要获取某一个的元素时候他要从头开始一个一个的去取它下一个元素的内存地址直到拿到我们要去的那个元素的地址 所以这导致了他的查询速度慢 

3.Vector

他的实现和ArrayList差不多  只不过他的底层都使用了同步锁来修饰 是线程安全的  每次扩容是原长度的2倍 ArrayList每次扩容是1.5倍

 

Set接口:

特性:无序(存储顺序 不是排序)  不可重复

 1.HashSet:

特点:允许一个null值 

其底层是通过HashMap来实现的 而HashMap是允许有一个null值的 所以HashSet也是允许有一个null值存在

2.TreeSet 

特点:不允许有null值

 底层通过红黑二叉树来实现 红黑二叉树的原理: 左小右大 运行的步骤 想象一个倒立的树 根部在上 当一个数据加入到集合中他会和集合的根元素去对比如果比根部元素小则放在左边 如果比根部元素大则放在右边 当下一次再进来一个元素的时候还是同样的去对比  ,如果在树的分叉中有连续三个比其所在的根部元素大的分支,则会把分支中的根部元素左移一下 右边第一个元素会做为分支的元素 这样来保持树的平衡(一个分支连续出现三个小的元素也是同样的原理) 描述可能比较抽象 个人的画图能力不怎么好 可以百度看一下 网上有一些大神画的图  就一目了然了

 

 

Map接口:

k v 形的存储,注意它并不继承Collection接口

关于Map接口这里简单说一下吧

1.HashMap

允许有一个null值做为k, 还有就是在开发过程中需要注意 尽量避免创建过多的HashMap对象 因为HashMap对象里边存储其他对象时 会造成对象的持续引用 使得Gc垃圾回收器无法及时回收,造成oom异常(堆内存溢出异常) 关于垃圾回收器可以看一下我的这篇文章https://blog.csdn.net/weixin_42059737/article/details/87817351  关于HashMap的问题可以百度一下  

2.TreeMap 

TreeMap不允许有null值, 有排序,底层树红黑二叉树 红黑二叉树的原理上边已经说了 就不再重复了

3.HashTable

HashTable 的两个特点:线程安全的 不允许有null值