转载

Java集合类的数据结构

本文源自参考《Think inJava》，多篇博文以及阅读源码的总结

前言

Java的集合其实就是各种基本的数据结构（栈，队列，hash表等），基于业务需求进而演变出的Java特有的数据结构（因为不仅仅是基本数据结构）。现在，我们以数据结构的视角来看看Java的集合到底是什么样子。并分析他们的性能。

一 JAVA集合体系

JAVA的集合体系分为两类，Collection接口和Map接口

主要分为三种：

Set。无插入顺序的不重复数据集接口( 集合演变而来 )
List。有插入顺序的数据集接口( 队列演变而来 )
Map。Key-Value的键值对数据集接口( Hash表演变而来 )

其中Set和List继承自Collection接口，Map则就是Map接口。

接口中都定义了一些基本增删改查的方法。

具体继承体系如下图：

Java集合类的数据结构

基本可以从名字知道集合的内部数据结构。

看后缀，有Set，List，Map后缀的集合，代表着该集合的基本结构，所以会具有以上所说的特性。
看前缀，前缀往往代表着该数据结构的具体实现方式。一般有这几种：
1. Hash或者Array,代表着以哈希（基本）数组实现的数据结构。
2. Linked，代表着集合内各个数据之间存在链表关系。
3. Tree或者Sorted，代表着内部使用红黑树实现了排序。（需要提供Comparator或者实现Comparable）

下面大略说下每个集合的数据结构，懒得贴源码了。

1.1 List

最常用的List就是ArrayList和LinkedList了，在此不讨论并发的List集合。

讨论下底层源码对它们的具体实现。

1.1.1 ArrayList

使用JAVA的基本数组实现的动态数组集合，源码底层 维护着List的容量与实际长度 。

因为使用的基本数组，不像哈希数组一样需要考虑哈希碰撞问题，因此负载因子默认为1。当List数组容量不够时才进行扩容， 扩容的倍数为1.5倍 。

通过Arrays.copyOf方法，返回复制的新数组。Arrays.copyOf底层调用的System.arraycopy方法。而在ArrayList初始化时，如果不指定初始数组长度， 在JDK1.6之后默认初始长度为0 ，在 JDK1.6之前则默认为10 。在JDK1.6后，ArrayList在第一次扩容时，如果扩容长度不足10，则会直接扩容到10。

具体集合怎么使用就不废话了。

1.1.2 LinkedList

这是一个 双向链表 ，其中节点用的是LinkedList的内部类。和数据结构中的链表差不多。可以用它实现栈和队列。

1.1.3 ArrayList与LinkedList比较

很明显，ArrayList是某种程度上的哈希表，适合随机读，但是不适合在集合中间插入和删除（会造成后续数据的位移）。

而LinkedList适合在头尾部插入删除，不适合随机读。

值得一提的是ArrayList随机读的时间复杂度是O(1)，LinkedList是O(n)。而ArrayList在中间插入和删除的时间复杂度是O(n)，LinekdList在中间插入删除时间复杂度也是O(n)

可以明显看出来ArrayList在插入删除上和LinkedList理论上所用的时间是一个级别的，但是ArrayList慢于LinkedList是因为在修改集合后需要进行其他数组数据的移动，而LinkedList则是查找节点花费了O(n)，不需要额外移动数据，所以在同样数据量时，LinkedList进行数据修改优于ArrayList。