java connection_Java Connection集合分析之List

柔光的暖阳◎ 2022-10-23 14:29 125阅读 0赞

Java Connection集合家庭分析

Java集合大致可以分为Set、List、Queue和Map四种体系，其中Set代表无序、不可重复的集合；List代表有序、重复的集合；而Map则代表具有映射关系的集合，Java 5 又增加了Queue体系集合，代表一种队列集合实现。

Java集合类之间的继承关系

Java的集合类主要由两个接口派生而出：Collection和Map,Collection和Map是Java集合框架的根接口。

Collection家族：

![8443059e520f6a0612e6d233aecc1403.png][]

List集合

List集合是有序、可重复的集合

本篇文章将集中介绍List集合的两个重要子类ArrayList(并且同时对比Vector)和LinkedList。

1.List集合中，判断元素是否相等需要集合元素类重写equals()方法。

2.List集合中，我们可以使用ListIterator来提供更加厉害的表里操作，ListIterator相比Iterator，可以对集合元素在遍历期间进行修改、插入、删除操作，并且还可以向前遍历。这些在Iterator中是无法做到的，其原因是因为List的底层采用数组结构实现，用数组意味着就有标记来记录各个元素的位置，因此针对List集合可以通过ListIterator在遍历期间进行集合元素的修改操作。

3.ArrayList与Vector的相同点在于底层都为数组实现，并且的默认初始长度为10。不同地方在于，进行扩容时，ArrayList每次扩容增加当前容量的50%，Vector则增加一倍。ArrayList为线程不安全，Vector为线程安全。ArrayList遍历方式有Iterator、ListIterator、for循环、增强for循环，Vector遍历方式有Iterator、ListIterator、for循环、增强for循环、枚举Enumeration。

我们分别看下Vector与ArrayList的初始化构造函数：

![ed3a993da7f8eac7500d88fa24010888.png][]

![802a023c028f6bcf5110f430769608e8.png][]

再看下Vector与ArrayList的add方法，观察其扩容策略：

Vector

![decda160fa8760296c6d88f7f26c2619.png][]

Vector进行扩容操作的逻辑为

如果此向量的当前容量小于minCapacity，则通过将其内部数组替换为一个较大的数组俩增加其容量。

新数据数组的大小姜维原来的大小 + capacityIncrement，

除非 capacityIncrement 的值小于等于零，在后一种情况下，新的容量将为原来容量的两倍，不过，如果此大小仍然小于 minCapacity，则新容量将为 minCapacity。

capacityIncrement为容量增量，就是每次Vector进行扩容的长度，在Vector进行初始化的时候可以指定capacityIncrement，否则默认为0。也就是扩容一倍。

ArrayList

![6e5f56f0242078474bf3a03a8deaa259.png][]

ArrayList的扩容逻辑除了标红处之外，其余和Vector相同。

4.如果开始就知道ArrayList或Vector集合需要保存多少个元素，则可以在创建它们时就指定initalCapacity初始长度的大小，这样可以提高性能。

此外，ArrayList还提供了两个额外的方法来调整其容量大小：

void ensureCapacity(int minCapacity) //如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。

void trimToSize() //将此 ArrayList 实例的容量调整为列表的当前大小。

5.Stack是Vector的子类，用于模拟“栈”这种数据结构，“栈”通常是指“后进先出”(LIFO)的容器。最后“push”进栈的元素，将被最先“pop”出栈。Stack与Vector一样，是线程安全的，性能较差，尽量少用Stack类。如果要实现栈”这种数据结构，可以考虑使用LinkedList。

6.LinkedList类是List接口的实现类——这意味着它是一个List集合，可以根据索引来随机访问集合中的元素。除此之外，LinkedList还实现了Deque接口(继承了Queue接口的双端队列)，可以被当作成双端队列来使用，因此既可以被当成“栈"来使用，也可以当成队列来使用。

LinkedList的实现机制与ArrayList完全不同。ArrayList内部是以数组的形式来保存集合中的元素的，因此随机访问集合元素时有较好的性能；而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色。

7.LinkedList调用默认构造函数，创建一个链表。由于维护了一个表头，表尾的Node对象的变量。可以进行后续的添加元素到链表中的操作，以及其他删除，插入等操作。也因此实现了双向队列的功能，即可向表头加入元素，也可以向表尾加入元素。

![42a662bf450c353e2383647e3b0407e8.png][]

下面来了解Node类的具体情况

![d95f69442354a90a09a1b372b737f566.png][]

由此可以具体了解链表是如何串联起来并且每个节点包含了传入集合的元素。

下面以增加操作，具体了解LinkedList的工作原理。

![5b551ec844f686d195fef946728e5aad.png][]

调用linkLast(e);方法，默认向表尾节点加入新的元素

![1d58cfd92e341f71d7834f16ca63629a.png][]

更新表尾节点，建立连接。其他操作类似，维护了整个链表。

下面具体来看，如何将“双向链表和索引值联系起来的”？并且为什么说LinkedList通过下标访问效率低？

![f7fc53bbdc57cb6726afdd81bac5cdc0.png][]

调用了node(index)方法返回了一个Node对象，其中node(index)方法具体如下

![b47608a74515339c6d63eda1cff726fc.png][]

首先会比较“index”和“双向链表长度的1/2”；若前者小，则从链表头开始往后查找，直到index位置；否则，从链表末尾开始先前查找，直到index位置。这就是“双线链表和索引值联系起来”的方法。

到此我们便会明白，LinkedList在插入、删除元素时性能比较出色，随机访问集合元素时性能较差。

8.LinkedList遍历方式

LinkedList支持多种遍历方式。

.通过迭代器遍历LinkedList

.通过快速随机访问遍历LinkedList(低效)

.通过for循环遍历LinkedList

.通过pollFirst()遍历LinkedList

.通过pollLast()遍历LinkedList

.通过removeFirst()遍历LinkedList

.通过removeLast()遍历LinkedList

实现都比较简单，就不贴代码了。

其中采用逐个遍历的方式，效率比较高。采用随机访问的方式去遍历LinkedList的方式效率最低。

LinkedList也是非线程安全的。

9.ArrayList与LinkedList性能对比

ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。ArrayList应使用随机访问(即，通过索引序号访问)遍历集合元素。

LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。LinkedList应使用采用逐个遍历的方式遍历集合元素。

如果涉及到“动态数组”、“栈”、“队列”、“链表”等结构，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍。

(01) 对于需要快速插入，删除元素，应该使用LinkedList。

(02) 对于需要快速随机访问元素，应该使用ArrayList。

(03) 针对迭代的效率问题

LinkedList：高级for循环与Iterator迭代(效率相似)>下标访问迭代。

ArrayList：下标访问迭代>高级for循环与Iterator迭代(效率相似)。

测试数据如下： 基于JDK1.8

LinkedList，ArrayList分别通过上面三种方式，遍历10w次String对象的效率

![fecfeb24ae95dbb72f6f9abd746ff187.png][]

遍历100w次

![c0c4dee786442ee183af51e2c9e4f0ee.png][]

遍历300w次

![c2a7a1a6c547b511edcd6bb520a4d7f5.png][]

Iterator遍历会被JVM编译为

![89e5667156ac107ae223df44517ea91e.png][]

而高级for循环会被编译为

![4486ec31e0b18d93461e6512badf4527.png][]

(04) 数组和链表的遍历效率问题(后续讨论。。。)

[8443059e520f6a0612e6d233aecc1403.png]: /images/20221023/8f03f2aa859f48d29e0d80e06d052176.png
[ed3a993da7f8eac7500d88fa24010888.png]: /images/20221023/088bcdb1bcbc4fde98b5f9280db90e60.png
[802a023c028f6bcf5110f430769608e8.png]: /images/20221023/4a665a65c06d4da48776c96880dece0e.png
[decda160fa8760296c6d88f7f26c2619.png]: /images/20221023/41b2d780774c4a539a3cd71d113e50ec.png
[6e5f56f0242078474bf3a03a8deaa259.png]: /images/20221023/eda8ab3da1eb4fad8840de6a28aacb62.png
[42a662bf450c353e2383647e3b0407e8.png]: /images/20221023/0c2d201a0e4347f6bb376979545312e0.png
[d95f69442354a90a09a1b372b737f566.png]: /images/20221023/aa6b00fcf1654146b744be7e85e4195d.png
[5b551ec844f686d195fef946728e5aad.png]: /images/20221023/766fd77f059e44839f1fab66ece109ab.png
[1d58cfd92e341f71d7834f16ca63629a.png]: /images/20221023/98a4d515a6f341489fa761651d6c4976.png
[f7fc53bbdc57cb6726afdd81bac5cdc0.png]: /images/20221023/4b337df7234548d5b68f8f4dcfeb36f7.png
[b47608a74515339c6d63eda1cff726fc.png]: /images/20221023/abd2fc932dd944568ee0ff199155c3e9.png
[fecfeb24ae95dbb72f6f9abd746ff187.png]: /images/20221023/423d1bbb04c64be99c71acf13eef5fd2.png
[c0c4dee786442ee183af51e2c9e4f0ee.png]: /images/20221023/918e5ff0897f46cbbea279baee6c3ff4.png
[c2a7a1a6c547b511edcd6bb520a4d7f5.png]: /images/20221023/736bca330e1a48ca8e86a46ce0c04e3d.png
[89e5667156ac107ae223df44517ea91e.png]: /images/20221023/39c90c07163447ca8efb438306b1dd03.png
[4486ec31e0b18d93461e6512badf4527.png]: /images/20221023/06536f293e8e481dadcce8a20338b3f2.png