java容器详细解析

　　

前言:在java开发中我们肯定会大量的使用集合,在这里我将总结常见的集合类,每个集合类的优点和缺点,以便我们能更好的使用集合。下面我用一幅图来表示

　　

　　

其中淡绿色的表示接口,红色的表示我们经常使用的类。

　　

<强> 1:基本概念

　　

Java容器类类库的用途是保存对象,可以将其分为2个概念。

　　

　　

一个独立元素的序列,这些元素都服从一条或多条规则。其列表中必须按照插入的顺序保存元素,不设置能有重复的元素,队列按照排队规则来确定对象的产生顺序(通常也是和插入顺序相同)

　　

　　

一组成对的值键对对象,允许用键来查找值.ArrayList允许我们用数字来查找值,它是将数字和对象联系在一起。而地图允许我们使用一个对象来查找某个对象,它也被称为关联数组。或者叫做字典。

　　

<强> 2:列表

　　

列表承诺可以将元素维护在特定的序列中.List接口在集合的基础上加入了大量的方法,使得可以在列表中间可以插入和移除元素。下面主要介绍2种列表

　　

　　

它的优点在于随机访问元素快,但是在中间插入和移除比较慢

　　

那么现在我们就一起来看看为什么ArrayList随机访问快,而插入移除比较慢。先说关于ArrayList的初始化。

　　

ArrayList有三种方式进行初始化如下

　　 　　 　　私人瞬时对象[]elementData; 　　公共ArrayList () { 　　(10); 　　} 　　公共ArrayList (int initialCapacity) { 　　超级(); 　　如果(initialCapacity & lt;0) 　　把新的IllegalArgumentException(“非法容量:”+ 　　initialCapacity); 　　这一点。elementData=https://www.yisu.com/zixun/new对象(initialCapacity); 　　} 　　公共ArrayList(收集<?扩展E> c) { 　　elementData=c.toArray (); 　　大?elementData.length;//c。toArray(错误地)可能不会返回Object [] (6260652) 　　如果(elementData.getClass () !=Object [] . class) 　　elementData=数组。copyOf (elementData、大小、对象[]. class); 　　} 　　 　　

我们可以看出ArrayList其实就是采用的是数组(默认是长度为10的数组)。所有ArrayList在读取的时候是具有和数组一样的效率,它的时间复杂度为1 .

　　

插入尾部就是elementData(大小+ +)=e;当然中间会进行扩容。现在主要说插入中间为什么相对来说比较慢源码如下

　　 　　 　　公共空间添加(int指数E元素){ 　　rangeCheckForAdd(指数);//验证(可以不考虑) 　　ensureCapacityInternal(+ 1)大小;//增加modCount ! !(超过当前数组长度进行扩容) 　　系统。arraycopy (elementData elementData、索引,索引+ 1, 　　大小——指数);(核心代码) 　　elementData(指数)=元素; 　　大小+ +; 　　} 　　之前 　　 　　

系统。arraycopy (elementData elementData、索引,索引+ 1)第一个参数是源数组,源数组起始位置,目标数组,目标数组起始位置,复制数组元素数目。那么这个意思就是索从索引性处每个元素向后移动一位,最后把索引为指数空出来,并将元素赋值给它。这样一来我们并不知道要插入哪个位置,所以会进行匹配那么它的时间赋值度就为n。

　　

　　

它是通过代价较低在列表中间进行插入和移除,提供了优化的顺序访问,但是在随机访问方面相对较慢。但是他的特性功能要比ArrayList强大的多。支持队列和栈

　　

ListedList采用的是链式存储。链式存储就会定一个节点节点。包括三部分前驱节点,后继节点以及数据值,所以存储存储的时候他的物理地址不一定是连续的。

　　

我们看下它的中间插入实现

　　

　　

　　

从代码我们可以看出先获取插入索引元素的前驱节点,然后把这个元素作为后继节点,然后在创建新的节点,而新的节点前驱节点和获取前驱节点相同,而后继节点则等于要移动的这个元素,所以这里是不需要循环的,从而在插入和删除的时候效率比较高。

　　

我们在来看看查询(我们可以分析出它的效率要比ArrayList低了不少)

　　

java容器详细解析